Wiley Puzzles for Programmers and Pros 978-0-470-12168-9 ユーザーズマニュアル
製品コード
978-0-470-12168-9
Sweet Tooth
Two children, perhaps similar to ones you know, love cake and mathematics. For this rea-
son, Jeremy convinces Marie to play the following game on two identical rectangular cakes
chef Martine has prepared for them.
son, 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.
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.
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?
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.
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.
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.
arisen. Chef Martine has made three new identical rectangular cakes. Jeremy and Marie
both eye them greedily.
P
3
4
Part I: Mind Games
04_121689 ch01.qxp 3/30/07 5:54 PM Page 4