Poisoned Cookies

Here’s an interesting puzzle which was part of the application for SPARC 2016. (Applications are now closed)

Suppose you have 240 cookie jars, one of which has been poisoned, so all the cookies in it are poisonous.

You also have 5 grey pigeons, each of which is immune to the poison, but has an interesting property: if it eats even a tiny crumb from a poison cookie, it will turn white at exactly 9am the following day, and stay white forever. The pigeons also have hearty appetites, and will immediately eat anything you put in front of them (which could include mixtures from multiple jars).

It is currently 8am, and you’re hosting a huge party at 10am the day after tomorrow (50 hours from now). You’d like to serve out as many cookie jars as possible while knowing, with certainty, that they are non-poisonous.

How many cookie jars is that, and how do you know? To get full credit, you should state the maximum, explain a strategy that achieves the maximum, and then explain why the strategy is optimal. (Partial solutions that establish a large number of safe cookie jars but not the maximum will also be considered. Solutions that make erroneous arguments will be penalized, so it is better to submit a correct partial solution than an incorrect full solution.)

Think about it before you read on. This post will contain:

My Kinda Elementary but Long-winded Solution
Samyak’s Streamlined Solution
Multinomial Digression

My Solution

We shall use a binary encoding. Suppose we had only jars. Then we could use five birds to find the poisoned jar in one go.

Like this: Number the jars in binary.

So

…

…
all the way to .

Now we shall name our birds One, Two, Four, Eight and Sixteen. If a jar has a one in the units place, we feed it to One. If it has a one in the two’s place, we feed it to Two. And so on. So jar number 18 = 10010 will be fed to Sixteen and Two because it has ones in ones place and the sixteens place. Jar no. 32 won’t be fed to any pigeon, because it’s got no ones in places One to Sixteen.

Then we wait and see which pigeons turn white.

We add up the numbers of the pigeons and that tells us the number of the jar. Say pigeons Two and Sixteen turn white. Then the poisoned jar must be 18 because that was the only jar fed to Two and Sixteen and nobody else. Of course, if no pigeons turn white, it must have been jar 32.

Clearly, with pigeons, this method can differentiate jars.

We shall divide our 240 jars into 32 batches. These batches will have different numbers of jars in them so that even though some pigeons will have become white, the number of jars in the batch will be small enough that we can use the remaining pigeons and the second day to identify the single poison jar.

Batch number 31 is binary 11111, so if it’s poisoned all our pigeons are white and we can’t do anything more. So batch 31 can have only one jar.
The five batches with one zero in binary (15, 23,27,29,30) leave one pigeon still grey, so we can have ( ) two jars in each of those batches.
The ten () batches with two zeros can have four jars each.
The ten () with three zeros can have eight jars each.
The five () with four zeros can have sixteen jars each.
Batch number 32 wasn’t fed to any pigeons, so all of them will stay grey if it’s the one, so we can have 32 jars in it.

, so that’s all the batches we can test. Have we managed to put 240 jars in them?

.

More than enough! (We can simply put 29 jars in batch 32 instead of 32)

Now take your 239 safe jars and party!

Samyak’s Streamlined Solution

Each bird will do one of three things: Stay grey, turn white after the first day, or turn white after the second day. Write numbers from 1 to 240 on the jars in ternary (base-3) All numbers less than (243=3^5) have five digits or less in base three. Ternary uses only the digits 0,1, and 2. If a jar has a one in the first place value, feed it to the first bird on day one. If it has a two written, feed it to the first bird on the second day. If a zero, don’t feed it to the first bird. Similarly for the other place values and the other pigeons. Using the birds’ ternary place values, add one in the correct place for each bird that turns white on the first day and two for each bird that turns white on the second day. The number you finally get is the number of the poisoned jar.

Multinomial digression

Consider .

Expanding the multinomial gives

Now substitute .

We get , identical to the expression for number of jars in the first solution. I have a feeling that there is some way to translate from ternary to the trinomial to products of binomial coefficients, to the technique I used in the first solution, but I don’t know how, so I leave it up to you.