# 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.

-