Competition-We Cant All Be Winners.


Sweet Tooth

Two children, perhaps similar to ones you know, love cake and mathematics. For this reason, Jeremy convinces Marie to play the following game on two identical rectangular cakes chef Martine has prepared for them.

Jeremy will cut the first cake into two pieces, perhaps evenly, perhaps not. After seeing the cut, Marie will decide whether she will choose first or allow Jeremy to do so. If she goes first, she will take the larger piece. If she goes second, she can assume that Jeremy will take the larger piece.

Next, Jeremy will cut the second cake into two pieces (remember that one of the pieces can be vanishingly small if he so chooses). If Marie had chosen first for the first cake, then Jeremy gets to take the larger piece of the second cake. If Marie had chosen second for the first cake, then she gets to take the larger piece of the second cake.

Warm-Up

Assuming each child will strive to get the most total cake possible, what is an optimal strategy for Jeremy?

Hint: 

Before you look at the solution: Assume that Jeremy divides the first cake into fractions f and 1-f where f is at least 1/2. Then explore the consequences if Marie chooses to take the piece of fraction f or if she goes second, so gets the piece having fraction 1-f.

Solution to Warm-Up

Following the hint, Marie reasons as follows: If she takes the fraction f piece, then Jeremy will take the entire second cake (he’ll cut the smallest crumb from the second cake and then will take the large first piece, leaving Marie only the crumb). So, Marie will get exactly f and Jeremy will get (1-f) + 1. If Marie takes the smaller piece of the first cake (fraction 1-f), Jeremy will do best if he divides the second cake in half. This gives Marie (1-f) + 1/2. Jeremy follows this reasoning, so realizes that the best he can do is to make f = (1-f) + 1/2. That is 2f = 1 1/2 or f = 3/4. If Marie takes the first piece of the first cake, then Jeremy will get 1/4 of the first cake and all of the second cake. If Marie takes the second piece of the first cake, then Jeremy will get 3/4 of the first cake and 1/2 of the second cake. In both cases, Marie gets a total of 3/4 of a cake and Jeremy 1 1/4. Note that if Jeremy cuts the first cake such that the larger fraction is less than 3/4, Marie will get more than 1/4 of the first cake by going second and will still get 1/2 of the second cake, thus increasing her cake amount beyond 3/4. By contrast, if Jeremy cuts the first cake such that the larger fraction is more than 3/4, Marie will just take that larger piece, again increasing her cake amount beyond 3/4.

I have discussed the warm-up at great length, because a week later a harder challenge has arisen. Chef Martine has made three new identical rectangular cakes. Jeremy and Marie both eye them greedily.

They decide on the following rules. Again, Jeremy will cut. But this time, Marie gets the first choice twice and Jeremy only once. That is, Jeremy cuts the first cake. Marie decides whether she wants to choose first or second for that cake. Next, Jeremy cuts the second cake; again Marie decides whether she wants to choose first or second. Same for the third cake. The only caveat is that Marie must allow Jeremy to choose first at least once.

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

  2. Suppose there are seven cakes and Marie gets the first choice for six of the seven cakes. Who has the advantage? By how much?

  3. Is there any way to ensure that each child receives the same amount of cake, assuming Jeremy always cuts?




Puzzles for Programmers and Pros
Puzzles for Programmers and Pros
ISBN: 0470121688
EAN: 2147483647
Year: 2007
Pages: 81
Authors: Dennis Shasha

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net