# Find the poisoned pie

You are a pie maker and you are holding a fair to display your pies. You have 1000 pies. You have 10 workers to help you. The fair is in two hours. Unfortunately you discover that a rival pie maker has poisoned one of your pies with a form of norovirus that makes people violently ill one and a half hours after even consuming a tiny bit of it. You know if any single person who visits your fair gets ill, your business will collapse but you need all the non poisoned pies for the fair. You can take small samples from the pies without spoiling them and your workers are prepared to do anything to help you. How do you find the poisoned pie?

-
Well, poise is one part of beauty contests. – Will Jagy Apr 4 '13 at 20:53
Not a duplicate, but the generalization where two pies are poisoned is here: math.stackexchange.com/questions/639/… – Qiaochu Yuan Apr 4 '13 at 20:59
@Alan Here's a hint: $1000 < 1024 = 2^{10}$. – Zhen Lin Apr 4 '13 at 21:08
Tell people there's a $1$ in $1000$ chance they get sick. What's life without danger? – Asaf Karagila Apr 4 '13 at 21:21

Given the time available, simultaneous testing is required.

Assign each pie a number from $1$ to $1000$, written in binary.

Assign each of your $10$ guinea pi... employees a column number from $1$ to $10$

Each employee is to go down the row of pies, taking and eating a small sample, if and only if the pie number has a $1$ in that employee's column. Each pie will lose $10$ samples.

Take the column of each sick employee, write a $1$ in that column of a $10$-digit binary number, and you have the pie number of the bad pie.

-

Take the hint above that $1000 < 1024 = 2^{10}$ and decrease the numbers.

The first case (1 servant, $2^1 = 2$ pies) is trivial.

2 servants and $2^2=4$ pies is slightly more problematic - 2 servants allow for 4 outcomes (both dead, both alive, A alive + B dead, B alive + A dead). How do you arrange the outcomes to tell you exactly which bottle is poisoned?

Once you can do 2, try 10 servants and $2^{10}$ pies.

-

As many as three loyal workers are about to be violently ill, but the pie can be found through a process of elimination.

Have each of the 10 workers stand in front of 10 long tables. On each table, place 10 stacks of 10 pies each. Have each worker taste each pie on his corresponding table. Rotate the room 90 degrees (or just move the servants). If the stacks of pies were evenly spaced and far enough apart, each worker should be standing in front of another 100 pies.

Once the workers have (again) tasted 100 pies each, now have k worker taste k pie in each stack; i.e. the first worker tastes the first pie in each stack, the 2nd tastes the 2nd, etc.

Hopefully you can complete this grueling task in under 30 minutes. Wait 90 minutes more, and the numbers of the sick workers will act as coordinates on a 3D grid.

-