A Plate of 1,000 Cookies

https://commons.wikimedia.org/wiki/File:Chocolate-chip-cookie-crumbs-on-plate.png — Image: Wikimedia Commons

A puzzle by David B., a mathematician at the National Security Agency, from the agency’s May 2017 Puzzle Periodical:

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:

Have one player who has eaten more cookies than you, and one player who has eaten fewer cookies than you.
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?

	Select Click for Answer
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

Click for Answer

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

June 27, 2021June 26, 2021 | Puzzles

Evolution

I just ran across this anecdote by Jason Rosenhouse in Notices of the American Mathematical Society. In a middle-school algebra class Rosenhouse’s brother was given this problem:

There are some horses and chickens in a barn, fifty animals in all. Horses have four legs while chickens have two. If there are 130 legs in the barn, then how many horses and how many chickens are there?

The normal solution is straightforward, but Rosenhouse’s brother found an alternative that’s even easier: “You just tell the horses to stand on their hind legs. Now there are fifty animals each with two legs on the ground, accounting for one hundred legs. That means there are thirty legs in the air. Since every horse has two legs in the air, we find that there are fifteen horses, and therefore thirty-five chickens.”

(Jason Rosenhouse, “Book Review: Bicycle or Unicycle?: A Collection of Intriguing Mathematical Puzzles,” Notices of the American Mathematical Society, 67:9 [October 2020], 1382-1385.)

June 23, 2021 | Puzzles · Science & Math

“Fermat’s Last Theorem”

A puzzle by H.A. Thurston, from the April 1947 issue of Eureka, the journal of recreational mathematics published at Cambridge University:

	Select Click for Answer
The answer appears in the March 1948 issue: “The statements of 2 and 3 are true, those of 1, 4 and 5 are false.” But no full solution is given. (The Eureka archive is published under a Creative Commons license.)

June 23, 2021June 23, 2021 | Puzzles

State House

A quickie from Peter Winkler’s Mathematical Puzzles, 2021: Can West Virginia be inscribed in a square? That is, is it possible to draw some square each of whose four sides is tangent to this shape?

	Select Click for Answer
Yes. Start by drawing an arbitrary rectangle that hugs the state. Now rotate that rectangle, adjusting its dimensions as it turns to keep each side in contact with the shape. If you turn it through 90 degrees, then the “height” and “width” will have traded places: What had been the shorter side of the rectangle is now the longer. So at some point the two must have had the same value. (This is a two-dimensional variation on a classic puzzle.)

Click for Answer

June 15, 2021June 14, 2021 | Puzzles

Black and White

carpenter chess problem

By George E. Carpenter. White to mate in two moves.

	Select Click for Answer
1. Qh8! and the queen will mate. From Carpenter’s Chess Problems, 1886.

June 14, 2021June 12, 2021 | Puzzles

Hooper’s Paradox

https://commons.wikimedia.org/wiki/File:Hooper_paradox.svg — Image: Wikimedia Commons

William Hooper published the oddity in 1774. The rectangle at the top measures 10 units by 3, giving an area of 30. But its dissected pieces seem to produce two other rectangles, with areas 12 and 20. Where did the two extra units come from?

	Select Click for Answer
Image: Wikimedia Commons The pieces don’t quite match. If the pieces in the second figure are arranged carefully back into the first, it will be seen that they overlap. The indicated parallelogram measures exactly 2 square units.

June 12, 2021 | Puzzles

“Imitative Chess”

dudeney imitative chess

A puzzle by Henry Dudeney:

A chessboard was on the table with the pieces all set up for a game. So I asked Dr. Bates to play a game with the Major on these conditions: Whatever move Bates made throughout, with the white pieces, the Major must exactly imitate with the black, and Bates must give checkmate on the fourth move. As an experiment, Bates started off with 1. e4, and Rackford replied with 1. e5. Then Bates played 2. Qh5, and the Major had to reply with 2. Qh4. This gave me a good opportunity to explain that White cannot now play 3. QxQ, because it would be impossible for Black then to imitate the move. Neither could he play 3. Qxf7+, because Black cannot do the same thing, as he would have to get out of check. White must always make a move that Black can copy, until the checkmate is actually given on the fourth move.

“This puzzle caused great interest, and it was some time before somebody (I think it was Strangways) hit on a solution.”

	Select Click for Answer
1. c4 c5 2. Qa4 Qa5 3. Qc6 Qc3 4. Qxc8#: (Henry E. Dudeney, “A Budget of Christmas Puzzles,” Strand 64:12 [December 1922], 619-622.) (If you want to solve the other puzzles, the solutions are here.)

June 8, 2021June 6, 2021 | Puzzles

The Hidden Element

The name of one chemical element appears as an unbroken string in the names of four other elements. What is the element, and what are the four?

	Select Click for Answer
Tin (actinium, astatine, platinum, protactinium). (Dave Morice, “Kickshaws,” Word Ways 28:3 [August 1995], 170-180.) 06/09/2021 UPDATE: In French, the name or (gold) appears as an unbroken string in the names of nine elements: bore (boron), californium, chlore (chlorine), fluor (fluorine), livermorium, phosphore (phosphorus), rutherfordium, seaborgium, and thorium. (Thanks, Jean-Claude.)

Click for Answer

June 7, 2021June 9, 2021 | Puzzles

Stonework

A problem from the Leningrad Mathematical Olympiad: You have 32 stones, each of a different weight. How can you find the two heaviest in 35 weighings with an equal-arm balance?

	Select Click for Answer
Think of the stones as tennis players and put them through a singles tournament. There are no upsets: In each match (weighing), the better (heavier) player always wins and goes on to the next round. With 32 players, this will produce a tournament with five rounds, comprising 16, 8, 4, 2, and 1 matches, successively, enough to produce 31 losers and identify the best (heaviest) stone. Now, the second-heaviest stone must have “lost” to the heaviest at some point in the tournament (since that was the only “player” strong enough to beat it). So take the five players beaten by the heaviest stone and put them through a little tournament of their own. Four matches will be enough to find the strongest of these five, and that must be the second-heaviest stone overall. (Via Ross Honsberger’s Mathematical Delights, 2004.)

Click for Answer