Puzzles for Programmers and Pros

5.5. Solutions

5.5.1. Solution to Sweet Tooth

1. How does Jeremy maximize the amount of cake he gets, given these rules? How much will he get?

Jeremy cuts the first cake in the fractions f and 1-f, where f is at least ½. Then if Marie chooses first, Jeremy will get 11/4 cakes from the last two by the argument of the warm-up. If Marie chooses second, Jeremy will get f and then will divide the last two cakes in half. So, f + ½ + ½ = (1 - f) + 1 ¼. That is, f + 1 = 2 ¼ - f. 2f = 1 ¼. That is f = 5/8. Therefore, Jeremy will receive 1 5/8 cakes and Marie will receive 1 3/8 cakes.

1. Suppose there were seven cakes and Marie got the first choice for six of the seven cakes. Who has the advantage? By how much?

There is an inductive pattern. If for k cakes where Marie gets the first choice in all but one, Jeremy still has an advantage A (that is, Jeremy would receive A more cake than Marie among those k), then Jeremy will still have an advantage for k+1 cakes. Here is why: Jeremy, knowing that he will have an advantage of A if Marie chooses first for the first cake, cuts the first piece into two pieces ½ + A/4 and ½ - A/4. If Marie chooses the piece having ½ + A/4, then Jeremy will suffer a disadvantage of A/2 for that first cake, but will gain an advantage of A for the remaining k cakes, so have a net advantage of A/2. By contrast, if Marie chooses to go second for the first cake, then Jeremy will cut the remaining cakes in half. Again he will have an overall advantage of A/2. Thus, Jeremy's ...