Homework 9 (assigned August 17, due August 23)

Reading: Rosen chapter 5, sections 5.2, 5.4; chapter 6, sections 6.1–6.3.

Written assignment : Solve the following "Do" exercises and assigned problems. Only solutions to the assigned problems should be turned in. Note: You are responsible for the material covered in both "Do" exercises and assigned problems.

"Do" Exercises (not to be handed in):

1. • Let S be a subset of {1, 2, …, 2n} having size n + 1. Prove that S must contain two numbers such that one divides the other. Show that this result is best possible by exhibiting a set of size n for which the conclusion is false.
   • Let S be a subset of {1, 2, …, 3n} having size 2n + 1. Prove that S must contain three consecutive numbers. Show that this result is best possible by exhibiting a set of size 2n for which the conclusion is false.

2. • Use the Binomial Theorem to find the coefficient of a⁵b³ in the expansion of (2a − b)⁸.
   • Use the Binomial Theorem to prove that {1, 2, …, n} has exactly as many subsets with even size as subsets with odd size. Does the conclusion remain true when n = 0?

3. In the Pennsylvania lottery, 11 numbers are selected at random from the first 80 positive integers. A player chooses 7 numbers; if these 7 numbers are a subset of the chosen 11, then the player wins. What is the probability of winning?

4. Alice throws 1 die 4 times and wins if she scores at least one six. Bob throws 2 dice 24 times and wins if he scores at least one double-six. Who has the greater probability to win?

5. In a famous game show on television, a prize is placed behind one of three doors, with probability 1/3 for each door. The contestant chooses a door. The host then opens one of the other doors and says "As you can see, the prize is not behind this door. Do you want to stay with your original choice or switch to the remaining door?" When the contestant has chosen a wrong door, the host opens the other wrong door. When the contestant has chosen the right door, the host opens one of the two wrong doors, each with probability 1/2. Prove that the contestant should switch.

6. The "random walk" theory of securities prices holds that price movements in disjoint time periods are independent of each other. Suppose we record only whether the price is up or down each year, and suppose further that the probability that our portfolio rises in price in any one year is 0.65.
   • What is the probability that our portfolio goes up for 3 consecutive years?
   • If you know that the portfolio has risen in price 2 years in a row, what probability do you assign to the event that it will go down next year?
   • What is the probability that the portfolio's value moves in the same direction in both of the next two years?

7. Half the women and one-third of the men in a class are smokers. Two-thirds of the students in the class are men. What fraction of the smokers are women?

8. The probability of hitting a target is 1/5 and 10 shots are fired independently.
   • What is the probability of the target being hit at least twice?
   • What is the probability of the target being hit at most twice?
   • Find the conditional probability that the target is hit at least twice, assuming that at least one hit is scored.

Assigned problems (to be handed in):

1. The numbers 1 through 12 have fallen off the face of a clock and have been replaced in some random order.
   1. Prove that some set of 3 consecutive numbers has sum at least 20. (5 points)
   2. Prove that some set of 5 consecutive numbers has sum at least 33. (5 points)

2. Consider a track meet with kⁿ contestants. In each round, the remaining contestants are placed in groups of size k; the winner in each group advances to the next round.
   1. Use these facts to give a combinatorial proof that k − 1 divides kⁿ − 1. (5 points)
   2. How many races are run in the entire competition? Justify your answer. (5 points)

3. Many games involve rolling 2 dice with sides numbered 1 through 6. Explain simply why x and 14 − x are equally likely to be the sum of the numbers facing up on the 2 dice. (5 points)

4. Solve each of the following lottery problems.
   1. What is the probability of winning a lottery that consists of choosing 6 numbers from the set {1, 2, …, 49}? (2 points)
   2. Suppose that a lottery consists of choosing a set of 5 numbers from the set {1, 2, …, 49}. Suppose further that smaller prizes are given to players with 4 of the 5 winning numbers. What is the probability of winning a smaller prize? (4 points)
   3. Find a formula for the probability of winning a smaller prize that goes with choosing k of the winning m numbers from the set {1, …, n}, where k < m < n. (4 points)

5. There are 3 coins in a bag: one coin that is heads on both sides, one coin that is tails on both sides, and one coin that is heads on one side and tails on the other side. You draw out a coin at random and observe only one side.
   1. If the side of the coin that is showing is heads, what is the probability that the opposite side is also heads? Justify your answer with a precise calculation. (5 points)
   2. What is the probability that the opposite side is the same as the side that you observe? Justify your answer with a precise calculation. (5 points)

6. Consider a probability space S of your choice.
   1. Define two events A and B in S such that A and B are not independent. (3 points)
   2. Define two events A and B in S such that A and B are independent. (3 points)
   3. Define three events A, B, and C in S such that all three pairwise combinations of the events, i.e., (A, B), (B, C), and (A, C) are independent but (A, B, C) is not independent. (4 points)

7. A commuter crosses one of 3 bridges, A, B, or C, to go home from work, crossing A with probability 1/3, B with probability 1/6, and C with probability 1/2. The commuter arrives home by 6 p.m. 75%, 60%, and 80% of the time by crossing bridges A, B, and C, respectively. If the commuter arrives home by 6 p.m., find the probability that bridge A was used. Also find the probabilities for bridges B and C. Justify your answers with precise calculations. (5 points)

8. A group of 5 people play the game of "odd man out" to determine who will buy lunch. The 5 people each flip a fair coin simultaneously. If all the coins but one come up the same, the person whose coin comes up different has to buy lunch. Otherwise, the 5 people flip the coins again and continue until just one coin comes up different from all the others. What is the probability that there is an odd person out after the coins are flipped once? (5 points)