Homework 5

Written assignment (assigned November 1, due November 7)

This homework covers the material in chapters 9 and 10 of the textbook.

Please note: your solutions should be readable, and justifications should be given for steps in the proofs. Elegance counts!

1. Do exercise 9.1-4 on page 175. (10 points)

2. Do exercise 9.2-2 on page 177. (10 points)

3. Do exercise 9.2-3 on page 177. (10 points)

4. Do exercise 9.3-3 on page 180. (10 points)

5. Do exercise 10.2-3 on page 189. (10 points)

6. Suppose that we are given 12 golf balls, one of which is heavier than the rest, and a balancing scale. Our task is to find the heavier ball, using as few weighings as possible.
   We can find the heavier golf ball using exactly three weighings as follows:
   1. Place 6 golf balls on each side of the scale.
      The heavier golf ball is among the 6 balls on the heavier side of the scale, so we have reduced the problem to one with 6 balls.
   2. Place 3 golf balls on each side of the scale.
      The heavier golf ball is among the 3 balls on the heavier side of the scale, so we have reduced the problem to one with 3 balls.
   3. Choose two golf balls from the remaining 3 and place one on each side of the scale.
      If one side is heavier, we have found the heavy ball. If both sides are of equal weight, the ball not on the scale is the heavy ball.

   Problem (10 points): Find an alternative method to determine which is the heavy ball that never uses more than three weighings but when "lucky" uses less than three weighings. By "lucky" we mean that the heavy ball is one of the balls weighed in the first step. Explain why the expected number of weighings for your procedure is less than 3.

Challenge Problem (optional)

• Do problem 10.1-2 on page 187. (10 points)

Gerry Brady
Thu Nov 1 16:02:10 CST 2001