Two children, perhaps similar to ones you know, enjoy cake and mathematics. For this reason, Marie and Jeremy decide to play the following game on their two identical rectangular cakes.
Jeremy will cut the first cake into two pieces, perhaps evenly, perhaps not (in which case the first piece will be larger). After seeing the cut, Marie will decide whether she will choose the first piece or the second. 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 the second smaller piece can be vanishingly small if he so chooses). If Marie chose to take the first piece of the first cake, then Jeremy gets to take the first piece of the second cake. If Marie chose to take the second piece of the first cake, then she gets to take the first piece of the second cake.
Assuming each child will strive to get the most total cake possible, what is an optimal strategy for Jeremy?
A 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 effectively the entire second cake (he'll cut the smallest crumb from the second cake and then 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 second 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.
Because Jeremy also follows this reasoning, he 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 then 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/4of 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.
End of Warm-up Solution
I have discussed the warm-up at length because a week later a harder challenge arises. Martine, the chef, makes 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. The same for the third cake. The only caveat is that Marie must allow Jeremy to choose first at least once.
Questions for you:
1. How does Jeremy maximize the amount of cake he gets, given these rules? How much will he get?
2. Suppose there were 7 cakes and Marie got the first choice for six of the seven cakes (she could choose which ones). Can Jeremy still guarantee an advantage? If so, by how much?
3. Is there any way to ensure that each child receives the same amount of cake?