Skip Site Navigation
HomeNews & FeaturesNews & StoriesArticle View

May 2017 Puzzle Periodical - A Plate of 1,000 Cookies

By David B., NSA Mathematician

PRINT  |  E-MAIL

Problem:



Steve, Tony, and Bruce have a plate of 1,000 cookies to share. They decide to share them in the following way: beginning with Steve, each of them in turn takes as many cookies as he likes (they must take an integer amount, greater than or equal to 1), and then passes the plate clockwise (with Tony sitting to Steve's left, and Bruce sitting to Tony's left). Nobody wants to feel like he hogged too many cookies, so they all want to avoid being the player at the end who has taken the most cookies. Additionally, nobody wants to feel cheated by finishing with the fewest cookies. Finally, given that the previous two conditions are definitely met, or definitely cannot be met, each player would like to maximize the number of cookies he eats. The players' objectives can be summarized as follows:



Objectives:




  1. Have one player who has eaten more cookies than you, and one player who has eaten fewer cookies than you.


  2. Eat as many cookies as possible.



Objective #1 takes infinite priority over Objective #2. Assuming that all players are perfectly rational, that they are all aware of each other’s rationality and objectives, and that they cannot communicate with each other in any way, how many cookies should Steve take to ensure he meets both objectives and how many cookies will Tony and Bruce take if Steve takes the winning amount?








Click to see the answer!




Solution:


First, suppose Steve takes 335 cookies. We will argue that Tony can then win by taking 334 cookies. If Tony does take 334, Bruce will be left with a plate of 331 cookies to take from. No matter how Bruce plays from here, he cannot meet objective #1, because he will need at least 335 cookies to do so, and has only 331 to take from. Therefore, Bruce will maximize the number of cookies he eats, and take the remaining 331. Tony finishes with 334, the middle amount, so he meets objective #1, justifying his decision to take 334 cookies. (Note that if Tony had taken more than 334, Bruce would still have taken all the remaining cookies, but Tony would not have met objective #1, so taking 334 is in fact Tony's best play.)



Therefore, Steve will fail objective #1 if he takes 335 cookies. Furthermore, we can repeat the argument above if Steve takes more than 335 cookies, by always having Tony take 1 fewer cookie than Steve (or all remaining cookies, if this amount is less than the number Steve took).



Now suppose instead that Steve takes 334 cookies. We will show that Tony cannot take any amount of cookies resulting in him (Tony) meeting objective #1. First, note that if Tony takes 333 or more cookies, Bruce will be unable to meet objective #1 (he will need at least 334, but there are at most 333 remaining), and so will take all remaining cookies, resulting in a "loss" for Tony.



Now suppose instead that Tony takes x cookies, where x≤332. Then there will be 666-x cookies remaining. Suppose Bruce takes 333 cookies. This leaves 333-x cookies on the plate. Even if Steve takes only 1 cookie each turn from now on, Bruce can ensure that he will have fewer cookies than Steve by also taking 1. Suppose Steve takes s cookies. Then on Tony's next turn, he has 333-x-s cookies to take from. Even if Tony takes all remaining cookies, total over his two turns, he will have taken 333-x-s+x=333-s, which is at most 332 (since s≥1), so Tony will definitely finish with fewer cookies than Bruce. Thus, if Tony takes 332 or fewer cookies, Bruce can win by taking 333 cookies, since this guarantees he will finish with less than Steve and more than Tony.



Therefore, if Steve takes 334 cookies, Tony cannot meet objective #1, and so will take as many cookies as possible, leaving none for Bruce. This leaves Steve with the middle amount of cookies, so taking 334 cookies is in fact a winning strategy for Steve. As shown above, Steve cannot do any better than this.



Steve: 334

Tony: 666

Bruce: 0