Free Essay

Discrete Maths

In: Computers and Technology

Submitted By bearli19
Words 4161
Pages 17
21-110: Problem Solving in Recreational Mathematics
Homework assignment 7 solutions
Problem 1. An urn contains five red balls and three yellow balls. Two balls are drawn from the urn at random, without replacement.
(a) In this scenario, what is the experiment? What is the sample space?
(b) What is the probability that the first ball drawn is red?
(c) What is the probability that at least one of the two balls drawn is red?
(d) What is the (conditional) probability that the second ball drawn is red, given that the first ball drawn is red?
Solution.
(a) The experiment is the drawing of two balls from the urn without replacement. The sample space is the set of possible outcomes, of which there are four: drawing two red balls; drawing two yellow balls; drawing a red ball first, and then a yellow ball; and drawing a yellow ball first, and then a red ball. One way to denote the sample space is in set notation, abbreviating the colors red and yellow: sample space = {RR, YY, RY, YR}.
Note that these four outcomes are not equally likely.
We can also represent the experiment and the possible outcomes in a probability tree diagram, as shown below. Note in particular the probabilities given for the second ball. For example, if the first ball is red, then four out of the remaining seven balls are red, so the probability that the second ball is red is 4/7 (and the probability that it is yellow is 3/7). On the other hand, if the first ball is yellow, then five out of the remaining seven balls are red, so the probability that the second ball is red is 5/7 (and the probability that it is yellow is 2/7). The probabilities of each of the four outcomes can be computed by multiplying the probabilities along the branches leading to the outcomes.
First ball

R
5
8

3
8

Second ball
4
7

3
7

Y

5
7

2
7

R

Y

R

Y

Outcome

Probability

RR

5
8

×

4
7

=

5
14

RY

5
8

×

3
7

=

15
56

YR

3
8

×

5
7

=

15
56

YY

3
8

×

2
7

=

3
28

(b) Before the first draw, five out of the eight balls in the urn are red. Each ball is equally likely to be drawn. So the probability that the first ball drawn is red is 5/8.
(c) The event that at least one of the two balls is red contains three outcomes: RR, RY, and YR.
Since we know the probabilities of all of these outcomes, we can find the probability of this event by adding the probabilities of the individual outcomes. So the probability that at least one of the two balls is red is 5/14 + 15/56 + 15/56 = 25/28.
Alternatively, we can observe that the event that at least one of the two balls is red is the complement of the event that both balls are yellow. The probability that both balls are yellow is 3/28, so the probability that it is not the case that both balls are yellow (i.e., the probability that at least one ball is red) is 1 − 3/28 = 25/28.
Page 1

(d) Suppose the first ball drawn is red. Then there are seven remaining balls, and four of them are red. So the conditional probability that the second ball is red, given that the first ball is red, is 4/7.
Problem 2. Suppose you and a friend play a game. Two standard, fair, six-sided dice are thrown, and the numbers appearing on the dice are multiplied together. If this product is even, your friend gives you a quarter, but if this product is odd, you must give your friend one dollar.
(a) What is the expected value of this game for you? Round to the nearest cent.
(b) What is the expected value of this game for your friend? Round to the nearest cent.
(c) Is this game fair? Why or why not?
Solution. We begin by drawing a table of the possible dice throws. The 36 outcomes represented by the squares of the grid below are all equally likely. The shaded squares represent outcomes in which the product of the numbers on the dice is even, and the unshaded squares represent outcomes in which this product is odd.
5 6
1 2 3 4
1

1

2

3

4

5

2

2

4

6

8

10 12

3

3

6

9

12 15 18

4

4

8

12

16 20 24

5

5

10 15

20 25 30

6

6

12 18

24 30 36

6

(a) From the table above, we see that 27 of the 36 equally likely outcomes yield an even product, so the probability that the product is even is 27/36, or 3/4. Similarly, the probability that the product is odd is 9/36, or 1/4. You will win 25/ if the product of the numbers on the dice is even, but c you will lose $1 if the product is odd. So there is a 3/4 probability that you will gain 25/ and a c 1/4 probability that you will lose 100/ (that is, gain −100/). So the expected value of the game for c c you is
3
1 c c c 4 (25/) + 4 (−100/) = −6.25/.
Rounded to the nearest cent, this is −6/. This means that you should expect to lose about 6/, on c c average, each time you play this game.
(b) Any money that you win in this game is money that your friend loses, and any money that your friend wins is money that you lose. (Mathematicians call this a zero-sum game.) Therefore, if the expected value of the game for you is −6/, the expected value of the game for your friend is 6/. c c
Your friend should expect to win about 6/, on average, each time the game is played. c (c) This game is not fair, because the expected value of the game is not exactly zero.
Problem 3. Suppose you roll a fair six-sided die six times and record the results of the rolls in order. What is the probability that you roll a “3” at least five times in a row?
Solution. There are essentially two ways in which this event can occur: either the first five rolls are all “3,” or the last five rolls are all “3.” Let’s give names to these events; let A be the event that the first five rolls are all “3,” and let B be the event that the last five rolls are all “3.” The question asks for the probability that either of these events occur, which is the probability of the event A ∪ B.
How many outcomes are there in all? In other words, what is the cardinality of the sample space? Each roll of the die has six possible outcomes, so, by the multiplication principle, in six rolls
Page 2

of the die there are 66 , or 46,656, possible outcomes (because the order of the rolls is important).
These outcomes are all equally likely.
How many outcomes are in the event A? The outcomes in the event A are those that look like
“3, 3, 3, 3, 3, ?,” where the question mark can be replaced by any number from 1 through 6. So the cardinality of A is 6.
Likewise, the outcomes in the event B are those that look like “?, 3, 3, 3, 3, 3,” where the question mark can be replaced with any number from 1 through 6. So the cardinality of B is also 6.
How many outcomes are in both A and B? In other words, what is the cardinality of A ∩ B?
There is only one such outcome, namely, “3, 3, 3, 3, 3, 3.” So |A ∩ B| = 1.
By the principle of inclusion–exclusion, we have
|A ∪ B| = |A| + |B| − |A ∩ B| = 6 + 6 − 1 = 11.
Alternatively, we could have found |A ∪ B| by listing all of the elements of A ∪ B explicitly:
A ∪ B = { 1,3,3,3,3,3; 2,3,3,3,3,3; 3,3,3,3,3,1; 3,3,3,3,3,2; 3,3,3,3,3,3; 3,3,3,3,3,4;
3,3,3,3,3,5; 3,3,3,3,3,6; 4,3,3,3,3,3; 5,3,3,3,3,3; 6,3,3,3,3,3 }.
So, using S to denote the sample space, we have
Pr(A ∪ B) =

11
|A ∪ B|
=
.
|S|
46,656

Therefore, the probability that a “3” is rolled at least five times in a row is 11/46,656, or about two hundredths of one percent.
Problem 4. (From The Colossal Book of Short Puzzles and Problems by Martin Gardner.) A secretary types four letters to four people and addresses the four envelopes. If she inserts the letters at random, each in a different envelope, what is the probability that exactly three letters will go into the right envelopes?
Solution. If three letters go into the right envelopes, then the fourth letter must go into the fourth envelope, which must be the right one! So the event that exactly three letters go into the right envelopes contains zero outcomes, which means that the probability of this event is zero.
Problem 5. (From The Colossal Book of Short Puzzles and Problems by Martin Gardner.) Bill, a student in mathematics, and his friend John, an English major, usually spun a coin on the bar to see who would pay for each round of beer. One evening Bill said: “Since I’ve won the last three spins, let me give you a break on the next one. You spin two pennies and I’ll spin one. If you have more heads than I have, you win. If you don’t, I win.”
“Gee, thanks,” said John.
On previous rounds, when one coin was spun, John’s probability of winning was, of course, 1/2.
What are his chances under the new arrangement?
Solution. Let’s make a table of the possible outcomes. Remember, John wins if he gets more heads than Bill. If there is a tie, Bill wins.
Bill
H
H
H
H
T
T
T
T

John
H
H
T
T
H
H
T
T

H
T
H
T
H
T
H
T

Page 3

Winner
John
Bill
Bill
Bill
John
John
John
Bill

The eight outcomes in the table above are equally likely. John wins in four of the eight cases.
So the probability that John wins under the new arrangement is 4/8, or 1/2, the same as it was before. [Gardner points out that John’s probability of winning remains 1/2 whenever he has one more coin than Bill. For example, if John has 51 coins and Bill has 50, John’s probability of winning is still 1/2.]
Problem 6. Alice has three fair six-sided dice, colored green, red, and blue, but these dice are not numbered in the standard way. Instead, they are numbered like this:
Green: 5 5 5 2 2 2
Red: 4 4 4 4 4 1
Blue: 3 3 3 3 3 6
In other words, the green die has three faces labeled “5” and three labeled “2”; the red die has five faces labeled “4” and one labeled “1”; and the blue die has five faces labeled “3” and one labeled “6.”
Alice proposes to Bob that they play a little game. “Here’s how it will work,” explains Alice.
“In each round, we will each choose one die and discard the third one. Then we will simultaneously roll our chosen dice. Whoever rolls the higher number will win a dollar from the other player. (Note that there can never be a tie.) And since I’m such a nice person, I will let you choose your die first, before I choose mine.”
(a) Suppose Bob chooses the red die and Alice chooses the green die. Show that the probability that Alice wins is greater than 1/2.
(b) After using the red die for a while and losing more often than not to Alice’s green die, Bob begins to suspect that the odds are not in his favor. So he chooses the blue die instead, and
Alice chooses the red die. Show that the probability that Alice wins is still greater than 1/2.
(c) Bob continues to lose when he plays the blue die against Alice’s red die. He reasons, “The green die is better than the red die, and the red die is better than the blue die. So, clearly, I should choose the green die, because it must be the best of all.” He takes the green die, and Alice takes the blue die. Show that the probability that Alice wins is still greater than 1/2.
(d) Alice’s dice are an example of nontransitive dice. How is this dice game similar to the game of
Rock, Paper, Scissors?
Solution.
(a) We draw a probability tree diagram showing Bob’s and Alice’s rolls when Bob has the red die and Alice has the green die.
Bob

4
5
6

1
6

Alice
1
2

1
2

1

1
2

1
2

5

2

5

2

Winner

Probability

Alice

5
6

×

1
2

=

5
12

Bob

5
6

×

1
2

=

5
12

Alice

1
6

×

1
2

=

1
12

Alice

1
6

×

1
2

=

1
12

To find the overall probability that Alice wins, we add the probabilities of each outcome in which
Alice wins. So the probability that Alice wins is 5/12+1/12+1/12 = 7/12, which is greater than 1/2
(it is about 58%).
Page 4

(b) When Bob has the blue die and Alice has the red die, the probability tree diagram looks like the following.
Bob
Alice
Winner
Probability

3
5
6

1
6

5
6

1
6

6

5
6

1
6

4

1

4

1

Alice

5
6

×

5
6

=

25
36

Bob

5
6

×

1
6

=

5
36

Bob

1
6

×

5
6

=

5
36

Bob

1
6

×

1
6

=

1
36

Alice wins with probability 25/36, which is greater than 1/2 (it is about 69%).
(c) When Bob has the green die and Alice has the blue die, the probability tree diagram looks like the following.
Bob
Alice
Winner
Probability

5
1
2

1
2

5
6

1
6

2

5
6

1
6

3

6

3

6

Bob

1
2

×

5
6

=

5
12

Alice

1
2

×

1
6

=

1
12

Alice

1
2

×

5
6

=

5
12

Alice

1
2

×

1
6

=

1
12

Alice wins with probability 1/12 + 5/12 + 1/12 = 7/12, which is greater than 1/2 (it is about 58%).
(d) In the game of Rock, Paper, Scissors, each object wins over one of the other two objects but loses to the other one: rock beats scissors but loses to paper, paper beats rock but loses to scissors, and scissors beats paper but loses to rock. In Alice’s dice game, each die “wins” over one of the other two dice (with probability greater than 1/2) but “loses” to the other one (with probability greater than 1/2): green wins over red but loses to blue, red wins over blue but loses to green, and blue wins over green but loses to red.
[True story: Warren Buffett once challenged Bill Gates to play this game, offering to let Gates choose his die first. Gates was intrigued, examined the dice, figured out the trick, and then demanded that
Buffett choose first.]
Problem 7. Ten mathematicians are captured by pirates. The pirate captain tells them, “I have an unusual custom for dealing with prisoners on my ship. Tomorrow at dawn I will put all ten of you in a line, blindfolded and facing the same direction. I will assign each of you either a black hat or a white hat, depending on the outcome of the flip of a fair coin. (Since there are ten of you, I will flip the coin ten times, once for each of you.)
“After you have each been given a hat, I will remove your blindfolds. Each of you will then be able to see the colors of the hats of all the people standing in front of you in the line, but you will not be able to see your own hat, nor will you be able to see the hats of the people behind you.
Page 5

“Then I will begin my questioning. I will start with the person at the back of the line (who can see all nine of the other hats). I will ask him what color his hat is. He must announce his guess, either black or white, in a flat, monotone voice, but loudly enough for all the rest of you to hear. If his guess is correct, I will allow him to go free. If his guess is incorrect, however, he will be killed.
“Next, I will move to the second-to-last person in line (who can see eight other hats), and I will repeat the procedure, moving up the line, until I have dealt with each of you in turn. By the way, once the hats have been distributed, you will not be allowed to pass any information among yourselves except your guesses.
“Well, I suppose it’s getting pretty late, and we have a big day tomorrow. Sleep well, and I’ll see you in the morning!”
That night the mathematicians get together and decide that they must devise a strategy to maximize the expected number of them who will go free. What strategy should they adopt?
Solution. The surprising answer is that nine of the ten mathematicians can be saved with certainty!
Let’s number the mathematicians 1 through 10, where mathematician 1 is at the front of the line (and can therefore see no hats) and mathematician 10 is at the back of the line (and can see all nine of the other hats).
The key to the best strategy is the following: Mathematician 10, who is the first to guess, counts the number of white hats he sees in front of him. If he sees an even number of white hats, he guesses “white”; if he sees an odd number of white hats, he guesses “black.” Since all of the remaining mathematicians can hear his guess, they will know whether there is an even number or an odd number of white hats among them.
When it is time for mathematician 9 to guess, he can see the number of white hats in front of him, and he knows (from mathematician 10’s guess) whether there is an even number or an odd number of white hats among mathematicians 1 through 9. This information is enough to allow mathematician 9 to deduce the color of his hat with certainty. For instance, if he sees an even number of white hats in front of him and he knows that mathematician 10 also saw an even number of white hats, then his own hat must be black. On the other hand, if he sees an even number of white hats in front of him and mathematician 10 saw an odd number of white hats, then his own hat must be white. So mathematician 9 can be assured of guessing his own hat color correctly.
Mathematician 8 can use similar reasoning to deduce the color of his hat. When it is his turn to guess, he can see the seven hats in front of him, he knows whether mathematician 10 saw an even number or an odd number of white hats, and he also knows the color of mathematician 9’s hat (from mathematician 9’s guess, which was correct). This is enough information to allow him to determine his own hat color, so he is also assured of guessing his own hat color correctly.
In general, when it is time for mathematician in the middle of the line to guess, the information available to him includes the colors of all the hats in front of him (which he can see directly); whether mathematician 10 saw an even number or an odd number of white hats (from mathematician 10’s guess); and the colors of all the hats behind him, except the hat of mathematician 10 (from the guesses of the other mathematicians). From this information he can work out what color his own hat must be, and so he will be able to guess correctly (simultaneously passing the information about the color of his own hat to the people in front of him, who will need it to determine the colors of their hats).
Therefore, if the mathematicians follow this strategy, mathematicians 1 through 9 will be saved with certainty. Unfortunately, mathematician 10 will only guess correctly half the time (by sheer luck), but, as he has no possible source of information about the color of his own hat, this is the best that can be done. In other words, with probability 1/2 it will be the case that nine mathematicians go free, and with probability 1/2 it will be the case that all ten mathematicians go free. The expected number of survivors is therefore
1
1
2 (9) + 2 (10) = 9.5, which is really quite impressive.

Page 6

Problem 8. Suppose the disease diauropunctosis afflicts 1 out of every 5,000 people in the United
States. (Assume that the occurrence of the disease is completely random, so that each person has a 1/5,000 probability of having the disease, independently of everyone else.) Fortunately, there is a test for diauropunctosis, which is 99% accurate, meaning that 1% of the people who are tested receive incorrect results. (Assume that the accuracy of the test is independent of the occurrence of diauropunctosis; in other words, assume the test is 99% accurate for people who have the disease and 99% accurate for people who do not have the disease.) The city of Pierce, population 1,000,000, has received a government grant to test all of its citizens for diauropunctosis.
(a) About how many people in Pierce have diauropunctosis?
(b) Out of the people who have diauropunctosis, about how many will test positive for the disease?
About how many will test negative?
(c) Out of the people who do not have diauropunctosis, about how many will test positive? About how many will test negative?
(d) Out of all the people who test positive for diauropunctosis, what percentage actually have the disease? (e) Think about what your answer to part (d) means. Suppose you are tested for diauropunctosis, and the test results come back positive. What is the (conditional) probability that you actually have diauropunctosis, given that you tested positive? Explain why receiving a positive result from a test that is 99% accurate does not mean that you have a 99% probability of having the disease. Solution.
(a) Since the prevalence of diauropunctosis is 1 in 5,000, the number of people in Pierce who have diauropunctosis is about
1
(1,000,000) = 200.
5,000
(b) The test for diauropunctosis is 99% accurate, which means that 99% of the people who are tested will receive the correct result (and the remaining 1% will receive the wrong result). Therefore, out of the 200 people in Pierce who have diauropunctosis, about
0.99(200) = 198 will test positive;
0.01(200) =

2 will test negative.

(c) Out of the 999,800 people in Pierce who do not have diauropunctosis, about
0.99(999,800) = 989,802 will test negative;
0.01(999,800) =

9,998 will test positive.

(d) There will be about 198 people who test positive and actually have diauropunctosis, and about
9,998 people who test positive but do not have the disease. So in all there will be about 10,196 people who test positive. Out of these, the percentage who actually have the disease is about
198
≈ 0.0194 = 1.94%.
10,196
(e) The answer to part (d) means that the conditional probability that a person has diauropunctosis, given that the person tested positive, is about 1.94%. The positive test result significantly increased the probability that the person has the disease (from the original probability of 1/5,000 to about 1/51), and so follow-up tests are appropriate, but because of the rarity of the disease it is far more likely that the positive test result was in error than that the person actually has diauropunctosis. The simple truth is that healthy people vastly outnumber people with the disease, and so false positives (though relatively rare with such an accurate test) will still be much more common than actual occurrences of the disease.
Page 7

Similar Documents

Free Essay

Discrete Math

...Course Design Guide MTH/221 Version 1 1 Course Design Guide College of Information Systems & Technology MTH/221 Version 1 Discrete Math for Information Technology Copyright © 2010 by University of Phoenix. All rights reserved. Course Description Discrete (as opposed to continuous) mathematics is of direct importance to the fields of Computer Science and Information Technology. This branch of mathematics includes studying areas such as set theory, logic, relations, graph theory, and analysis of algorithms. This course is intended to provide students with an understanding of these areas and their use in the field of Information Technology. Policies Faculty and students/learners will be held responsible for understanding and adhering to all policies contained within the following two documents:   University policies: You must be logged into the student website to view this document. Instructor policies: This document is posted in the Course Materials forum. University policies are subject to change. Be sure to read the policies at the beginning of each class. Policies may be slightly different depending on the modality in which you attend class. If you have recently changed modalities, read the policies governing your current class modality. Course Materials Grimaldi, R. P. (2004). Discrete and combinatorial mathematics: An applied introduction. (5th ed.). Boston, MA: Pearson Addison Wesley. Article References Albert, I. Thakar, J., Li, S., Zhang, R., & Albert, R...

Words: 1711 - Pages: 7

Free Essay

Mth/221 Discrete Math for Information Technology Week 4

...* MTH/221 Week Four Individual problems: * * Ch. 11 of Discrete and Combinatorial Mathematics * Exercise 11.1, problems 8, 11 , text-pg:519 Exercise 11.2, problems 1, 6, text-pg:528 Exercise 11.3, problems 5, 20 , text-pg:537 Exercise 11.4, problems 14 , text-pg:553 Exercise 11.5, problems 7 , text-pg:563 * Ch. 12 of Discrete and Combinatorial Mathematics * Exercise 12.1, problems 11 , text-pg:585 Exercise 12.2, problems 6 , text-pg:604 Exercise 12.3, problems 2 , text-pg:609 Exercise 12.5, problems 3 , text-pg:621 Chapter 11 Exercise 11.1 Problem 8: Figure 11.10 shows an undirected graph representing a section of a department store. The vertices indicate where cashiers are located; the edges denote unblocked aisles between cashiers. The department store wants to set up a security system where (plainclothes) guards are placed at certain cashier locations so that each cashier either has a guard at his or her location or is only one aisle away from a cashier who has a guard. What is the smallest number of guards needed? Figure 11.10 Problem 11: Let G be a graph that satisfies the condition in Exercise 10. (a) Must G be loop-free? (b) Could G be a multigraph? (c) If G has n vertices, can we determine how many edges it has? Exercise 11.2 Problem 1: Let G be the undirected graph in Fig. 11.27(a). a) How many connected subgraphs ofGhave four vertices and include a cycle? b) Describe the...

Words: 1159 - Pages: 5

Premium Essay

Discrete Math

...Coal is a fossil fuel like oil and gas. Fossil fuels are all formed out of organic matter deposited, decomposed and compressed, storing all the carbon involved under the earth's surface for millions of years.  Some of the advantages of coal are -  * Easily combustible, and burns at low temperatures, making coal-fired boilers cheaper and simpler than many others * Widely and easily distributed all over the world; * Comparatively inexpensive to buy on the open market due to large reserves and easy accessibility * Good availability for much of the world (i.e. coal is found many more places than other fossil fuels) * Most coal is rather simple to mine, making it by far the least expensive fossil fuel to actually obtain * Coal-powered generation scales well, making it economically possible to build a wide variety of sizes of generation plants. * A fossil-fuelled power station can be built almost anywhere, so long as you can get large quantities of fuel to it. Most coal fired power stations have dedicated rail links to supply the coal. However, the important issue as of now is whether there are more advantages than disadvantages of fossil fuels like coal!  Some disadvantages of coal are that -  * it is Non-renewable and fast depleting; * Coal has the lowest energy density of any fossil fuel - that is, it produces the least energy per ton of fuel * It also has the lowest energy density per unit volume, meaning that the amount of energy...

Words: 1142 - Pages: 5

Premium Essay

Discrete Math

...Lecture 1. Logic. Propositions. The rules of logic specify the precise meaning of mathematical statements. For instance, the rules give us the meaning of such statements as, “There exists an integer that is greater than 100 that is a power of 2”, and “For every integer n the sum of the positive integers not exceeding n is ”. Logic is the basis of all mathematical reasoning, and it has practical applications to the design of computing machines, to artificial intelligence, to computer programming, to programming languages, and to other areas of computer science. A proposition is a statement that is either true or false, but not both. Letters are used to denote propositions, just as letters are used to denote variables. The conventional letters used for this purpose are p, q, r, s, … The truth value of a proposition is true, denoted by T, if it is a true proposition and false, denoted by F, if it is a false proposition. We now turn our attention to methods for producing new propositions from those that we already have. Many mathematical statements are constructed by combining one or more propositions. New propositions, called compound propositions, are formed from existing propositions using logical operators. Let p be a proposition. The statement “It is not the case that p” is another proposition, called the negation of p. The negation of p is denoted by p. The proposition p is read “not p”. A truth table displays the relationships between the truth values of propositions. Table...

Words: 1725 - Pages: 7

Free Essay

Discrete Math

...Phase 2 IP Matt Peterson MATH203-1403A-03 Part 1 Consider the following 2 sets of data that list football teams and quarterbacks: D = {Jets, Giants, Cowboys, 49’ers, Patriots, Rams, Chiefs} Q = {Tom Brady, Joe Namath, Troy Aikman, Joe Montana, Eli Manning} 1. Using D as the domain and Q as the range, show the relation between the 2 sets, with the correspondences based on which players are (or were) a member of which team(s). (You can usehttp://www.pro-football-reference.com to find out this information). Show the relation in the following forms: * Set of ordered pairs (Jets, Namath) (Giants, Manning) (Cowboys, Aikman) (49ers, Montana) (Chiefs, Montana) (Patriots, Brady) 2. The relation is a function, no one element of the domain matches no more than one element of the range. * Directional graph Jets Namath Giants Manning Cowboys Aiken 49er’s Montana Chiefs Montana Patriot’s Brady 3. Now, use set Q as the domain, and set D as the range. Show the relation in the following forms: * Set of ordered pairs (Namath, Jets), (Manning, Giants), (Aiken, Cowboys), (Montana, 49er’s), (Montana, Chiefs), (Brady, Patriots) 4. The relation is not a function, one element of the domain matches with two elements of the range. ( Montana, Chief’s & 49er’s) * Directional graph Namath Jet’s Manning Giant’s Aiken Cowboy’s Montana 49er’s Montana Chief’s Brady Patriot’s Part 2 Mathematical sequences...

Words: 475 - Pages: 2

Premium Essay

Discrete Maths

...Exercise 4.1: 4. A wheel of fortune has the integers from 1 to 25 placed on it in a random manner. Show that regardless of how the numbers are positioned on the wheel, there are three adjacent numbers whose sum is at least 39. Work: Let suppose that there are not three adjacent numbers whose sum is at least 39 then for every set of 3 adjacent numbers their sum is less than 39 Since all the numbers are integers for every set of 3 adjacent numbers their sum is less than or equal to 38 Let select the 24 numbers around the “1”, from these 24 numbers we can create 8 sets of 3 consecutive adjacent numbers , then the total sum is less than or equal to 8(38)+1 = 305 So we have that the sum of 1+2+3+……+25 305 (but this is false) because 1+2+….25 = 25(26)/2 = 325 > 305 Then we proved that regardless of how the numbers are positioned on the wheel, there are three adjacent numbers whose sum is at least 39. 7. A lumberjack has 4n + 110 logs in a pile consisting of n layers. Each layer has two more logs than the layer directly above it. If the top layer has six logs, how many layers are there? Work: The 1st layer (the top one) has 6 logs The 2nd layer has 6+1(2) logs The 3rd layer has 6+2(2) The 4th layer has 6+3(2) ……………. The nth layer 6 +(n-1)(2) Total number of layers is: 6n +2(1+2+3+….+n-1) = 6n + 2(n-1)n/2 = 6n+n(n-1) = (n+5)n ...

Words: 545 - Pages: 3

Premium Essay

Discrete Math

...Phase One Individual Project: BeT Proposal Natalie Braggs IT106-1401A-03: Introduction to Programming Logic Colorado Technical University 01/12/2014 Table of Contents Introduction 3 Problem Solving Techniques (Week 1) 4 Data Dictionary 5 Equations 6 Expressions 7 8 Sequential Logic Structures (Week 2) 9 PAC (Problem Analysis Chart)-Transfers 10 IPO (Input, Processing, Output)-Viewing Balances 11 Structure Chart (Hierarchical Chart)-Remote Deposit 12 12 Problem Solving with Decisions (Week 3) 14 Problem Solving with Loops (Week 4) 15 Case Logic Structure (Week 5) 16 Introduction This Design Proposal (BET-Banking e-Teller) is going to show a banking application that allows customers to perform many of the needed transactions from the mobile phones. The Banking e-Teller will allow customers to check balances, make remote capture deposits, and perform transfers to their checking and/or savings accounts. Problem Solving Techniques (Week 1) Data Dictionary ------------------------------------------------- Problem Solving Techniques A data dictionary allows you see what data (items) you are going to use in your program, and lets you see what type of data type you will be using. Providing these important details allows the programmers to collectively get together and brainstorm on what is needed and not needed. Data Item | Data Item Name | Data Type | First name of account owner | firstName | String | Last name of account owner...

Words: 609 - Pages: 3

Premium Essay

Discrete Math

...Most people think that computer programming just recently had been created but far from that, it started for over a century. Starting from Charles Babbage’s steam driven machine named the Analytical Engine back in 1834. This idea caught the attention of a mathematician Ada Lovelace, she wrote a program to make the Analytical Engine calculate and print a sequence of numbers known as Bernoulli numbers. Because of her work with the Analytical Engine, she is considered as the first ever computer programmer. The first true computer appeared in 1943 when the U.S. Army created a computer called ENIAC that was able to calculate artillery trajectories. To give it instructions, you had to physically flip its different switches and rearrange its cables. However, physically rearranging cables and switches to reprogram a computer proved to be very tasking and clumsy. So instead of physically rearranging the computer’s wiring, computer scientists decided it would be easier to give the computer different instructions. In the old days, computers were taking up entire rooms and cost millions of dollars. Today, computers have shrunk that they are essentially nothing more than a piece of granular bar which are called the central processing unit (CPU), or processor. However in order to tell the processor what to do, you have to give it instructions written in a language that it can understand. That is where programming languages comes in. There many different computer languages and each one of them...

Words: 1364 - Pages: 6

Premium Essay

Discrete Math

...L1.1 Lecture Notes: Logic Justification: Precise and structured reasoning is needed in all sciences including computer science. Logic is the basis of all reasoning. Computer programs are similar to logical proofs. Just as positive whole numbers are the fundamental units for arithmetic, propsitions are the fundamental units of logic. Proposition: A statement that is either true or false. E.g. Today is Monday Today is Tuesday The square root of 4 is 2 The square root of 4 is 1 2 is even, and the square of two is even, and 3 is odd and the square of 3 is odd. The Panthers can clinch a playoff berth with a win, plus a loss by the Rams, a loss or tie by the Saints and Bears, a win by the Seahawks and a tie between the Redskins and Cowboys. (Copied verbatim from the sports page 12/26/2004.) Propositions may be true or false and no preference is given one way or the other. This is sometimes difficult to grasp as we have a “natural” preference for true statements. But “snow is chartreuse” and “snow is white” are both propositions of equal standing though one is true and the other false. Non-propositions: What is today? Is today Monday? Questions are not propositions. You can’t judge whether the question itself is true or false, even though the answer to the question may be true or false. Show me some ID! Similarly, imperative statements lack a truth value. 2x=4 x=y Statements with undetermined variables do not have truth...

Words: 2247 - Pages: 9

Premium Essay

Discrete Math Summary

...Closed path = 1st Vertex = Last Vertex Simple path = different edges (Vertex can be used twice) Closed simple path: different edges + 1st vertex = last vertex (vertices can be used twice) Cycle = closed simple path (1st vertex = last vertex + different edges) + different vertices Distinct vertices ==> different edges Cycle= closed path e1…en of length at least 3 + distant vertices = path e1…en with n >= 3 + 1st vertex = last vertex + distinct vertices A path has all vertices distinct ==> different edges + no cycles G and H are isomorphic if there exists an isomorphism and γ = V(G) ---> V(H) such that if {u,v} edge in G then {γ(u), γ (v)} edge in H each vertex goes to another vertex degrees are the same shapes are mapped too to prove two graphs are isomorphic check the degree lists….if they match find a mapping between the two graphs Euler path = simple path which goes through each edge exactly once Euler...

Words: 384 - Pages: 2

Free Essay

Discrete Math for Computer Science Students

...Discrete Math for Computer Science Students Ken Bogart Dept. of Mathematics Dartmouth College Scot Drysdale Dept. of Computer Science Dartmouth College Cliff Stein Dept. of Industrial Engineering and Operations Research Columbia University ii c Kenneth P. Bogart, Scot Drysdale, and Cliff Stein, 2004 Contents 1 Counting 1.1 Basic Counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . The Sum Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Abstraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Summing Consecutive Integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . The Product Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Two element subsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Important Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Counting Lists, Permutations, and Subsets. . . . . . . . . . . . . . . . . . . . . . Using the Sum and Product Principles . . . . . . . . . . . . . . . . . . . . . . . . Lists and functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . The Bijection Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . k-element permutations of a set . . . . . . . . . . . . . . . . . . . . . . . . . . . . Counting subsets...

Words: 71201 - Pages: 285

Free Essay

Discrete Math Phase 1 Individ.

...Robert Gibbins MATH203-1401A-05 Application of Discrete Mathematics Phase 1 Individual Project January 12, 2014 Part I Demonstrate DeMorgan’s Laws using a Venn diagram: The portions below define 2 sets, and a universal set that exists within the 2 sets.. They state the union and intersection of the 2 sets and the complements of each set. The Venn Diagram gives a visual to give a demonstration of DeMorgan’s law of sets. Union The Union is the combined elements of both sets A and B: A U B = {Addison, Mabel, Leslie, Matt, Rick, Joel}               or U = {Addison, Mabel, Leslie, Matt, Rick, Joel}               Set A is expressed below in the shaded area of the Venn Diagram: A = {Addison, Leslie, Rick}   Set B is expressed below n the shaded area of the Venn Diagram: B = {Mabel, Matt, Joel}   Intersection The intersection are the elements both A and B have in common, in this case both softball and volleyball players.  The intersection is expressed below and is represented in the shaded section of the Venn Diagram. A ∩ B = {Matt, Rick} Matt Rick Matt Rick    Complements The Complement of a set contains everything in the universe minus what is in the set itself.  The complement of Set A and Set B are expressed: A’ = {Mabel, Matt, Joel}   B’ = {Addison, Leslie, Rick}   De Morgan’s Law                  1.     The first portion of DeMorgan’s law says the complement of the union of sets A and B are the intersection of the...

Words: 399 - Pages: 2

Free Essay

Discrete Math Unit 5 Quiz

...1. Write the first four terms of the sequence whose general term is an = 2( 4n - 1) (Points : 3) |        6, 14, 22, 30        -2, 6, 14, 22        3, 7, 11, 15        6, 12, 18, 24 | 2. Write the first four terms of the sequence an = 3 an-1+1 for n ≥2, where a1=5 (Points : 3) |        5, 15, 45, 135        5, 16, 49, 148        5, 16, 46, 136        5, 14, 41, 122 | 3. Write a formula for the general term (the nth term) of the arithmetic sequence 13, 6, -1, -8, . . .. Then find the 20th term. (Points : 3) |        an = -7n+20; a20 = -120        an = -6n+20; a20 = -100        an = -7n+20; a20 = -140        an = -6n+20; a20 = -100 | 4. Construct a series using the following notation: (Points : 3) |        6 + 10 + 14 + 18        -3 + 0 + 3 + 6        1 + 5 + 9 + 13        9 + 13 + 17 + 21 | 5. Evaluate the sum: (Points : 3) |        7        16        23        40 | 6. Find the 16th term of the arithmetic sequence 4, 8, 12, .... (Points : 3) |        -48        56        60        64 | 7. Identify the expression for the following summation:(Points : 3) |        6        3        k        4k - 3 | 8. A man earned $2500 the first year he worked. If he received a raise of $600 at the end of each year, what was his salary during the 10th year? (Points : 3) |        $7900        $7300        $8500        $6700 | 9. Find the common ratio for the geometric sequence.: 8, 4, 2, 1, 1/2 (Points...

Words: 273 - Pages: 2

Premium Essay

Discrete Math Week 2 Assignment

...Relations, Functions, Sequences, and Graphs Part I: Suppose you are developing a statistical database in which information about professional football teams and records are stored. Consider the following 2 sets of data that list football teams and quarterbacks: D = {Jets, Giants, Cowboys, 49ers, Patriots, Rams, Chiefs} Q = {Tom Brady, Joe Namath, Troy Aikman, Joe Montana, Eli Manning} 1. Using D as the domain and Q as the range, show the relation between the 2 sets, with the correspondences based on which players are (or were) a member of which team(s). (You can use http://www.pro-football-reference.com to find out this information). Show the relation in the following forms: Set of ordered pairs {(Jets, Joe Namath), (Giants, Eli Manning), (Cowboys, Troy Aikman), (49ers, Joe Montana), (Patriots, Tom Brady), (Rams, Joe Namath), (Chiefs, Joe Montana)} Jets Jets Directional graph Tom Brady Tom Brady Giants Giants Joe Namath Joe Namath Cowboys Cowboys Troy Aikman Troy Aikman 49ers 49ers Joe Montana Joe Montana Patriots Patriots Rams Rams Eli Manning Eli Manning Chiefs Chiefs 2. Is the relation a function? Explain. Yes, this relation is a function since for every element on the domain side there is one and only one element on the range side. 3. Now, use set Q as the domain, and set D as the range. Show the relation in the following forms: Set of ordered pairs {(Joe Namath, Jets), (Eli Manning, Giants), (Troy Aikman, Cowboys)...

Words: 678 - Pages: 3

Free Essay

Signal and System

...Signal may be either continuous-time or discrete-time, with either analog or digital values [1]. The signals which are represented by a continuous function are called continuous signals and those which are described by number sequences are called discrete signals [2]. We have seen about a signal in brief. The second component in signal processing is a system which is a process whose input and output are signals. Signal processing is a vast area comprising the concepts of electrical engineering, systems engineering and applied mathematics that deals with both the analog and discrete time signals, represented by variation in time or spatial physical quantities. Precise statistical depiction is required for the development of improved signal processing algorithms of natural signals [3]. The major operations of Signal processing includes 1) signal acquisition and reconstruction, 2) Quality improvement including filtering, smoothing and digitization, 3) feature extraction 4) signal compression and 5) prediction [4] [5]. Analog signal processing, Discrete-time signal processing, Non-linear signal processing and Digital signal processing are the four major categories of signal processing. The signal processing performed over analog signals for the purpose of any of the major operations of signal processing is known to be analog signal processing and the same concept is applied for discrete-time signal processing, where the only difference is discrete signal is employed. An analog signal...

Words: 280 - Pages: 2