Puzzle of the Week for 22 February 1999: Solution

The pirates baked 79 cookies (at least). Other solutions are 160, 241, 322, ... or any number of the form 79 + 81N, where N is an integer.

If, for example, there were 79 cookies, then Arrgh snitched 26, gave 1 to Squawwk, and left 52 for his shipmates. Bluster swiped 17 of these, and gave another to Squawwk, leaving 34. Cruft took 11, gave another to Squawwk, and left 22. At the final division, each pirate received 7 cookies and Squawwk took the last one.

The Greek mathematician Diophantus was the first to describe methods, now known as Diophantine arithmetic, for finding solutions in integers (whole numbers) to problems such as this one.

There are (at least) two ways to solve the problem of the pirates' cookies. Let's look at the standard method first.

Let A be the number of cookies each pirate receives after lunch, when the remainder are shared out. Let B be the number of cookies on the plate before this division. The relationship between A and B is simply

(the extra 1 is Squawwk's last cookie). If we go back one step further, remember that B represents 2 shares of the 3 resulting from Cruft's division of the cookies; so that C, the number of cookies on the plate before Cruft snitched his share, must have been: We can continue in this way to get D, the number of cookies before Bluster's visit to the galley: Finally, E, the number of cookies before Arrgh's bit of cookie piracy, is the original number of cookies, the number we are looking for:

By successive substitutions, we can see that:

We can distribute and rearrange the terms in the last equation to get: Since both A and E must be integers, the left side of this equation must be an integer. Thus the right side must also be an integer (the same one!). This can only be true if A+1 is evenly divisible by 8; and this is only true if A is a number of the form 8N - 1, such as 7, 15, 23, .... If we take A = 7, then E (the number of cookies baked by the pirates) is 81*7/8 + 65/8 = 79.

It's not too hard to see why solutions occur at intervals of 81. At each of the four divisions, a pirate removes 1 cookie and 1/3 of the remainder. If we increase the remainder by adding more cookies to the initial pile, we need to add a number that contains four factors of 3. The smallest such number is 81 (34).

Given this insight (that solutions occur at intervals of 81), here is the second (rather bizarre) way to solve the problem. Imagine that the pirates baked -2 (yes, negative two!) cookies. Arrgh would sneak into the galley to grab his share. It doesn't matter if Squawwk gets a cookie before or after the division, so let's suppose Arrgh gives Squawwk the cookie first. Arrgh now finds -3 cookies on the plate (just keep using your imagination, here). He divides them into three shares of -1 cookie each, takes his share, and leaves -2 cookies on the plate. Each of the other pirates follows suit (as you can see, only Squawwk comes out ahead in this case), and at the end they give another cookie to Squawwk and share the remaining -3 cookies equally.

So now we know that (in some very strange way) -2 is a solution, and we know that solutions are spaced at intervals of 81. It's easy to see that the smallest positive solution must be -2 + 81, or 79. If the idea of negative cookies sounds weird for you, think how Diophantus would have felt, more than two thousand years before the "invention" of negative numbers!

Can you generalize the solution for N pirates?

Links