Optimizing on the number of days to find a poisoned cookie

Question

A friend of mine was asked this question for an interview and couldn't solve it at that moment. Thought I would share the same.

There are a thousand choco-chip cookies with one of them poisoned. You have access to 10 lab rats per day. Each rat can nibble on any number of cookies and each cookie can be nibbled by any number of rats. After a rat nibbles on a poisoned cookie, it takes a day to see the after effects on the rat if it were poisoned.

Optimize on the number of days. I was able to come up with an algorithm to find the poisoned cookie in 2 days, although I believe there exists a way to do this in 1 day

Answer 1

This is the "easy" solution in three days:

• First, allow each rat to nibble 100 cookies.
• After one day, allow each rat to nibble 10 of the cookies eaten by the dead rat.
• After two days, allow each rat to nibble one of the cookies eaten by the second dead rat.
• After three days, you will know which cookie is poisoned.

Now for the "hard" solution in one day:

• Number all of the cookies in binary.
• Each rat is to nibble on those cookies whose binary representation has a set bit at the rat's index. So for instance rat 1 will nibble all the odd-numbered cookies.
• Put another way, cookie 37 will be nibbled by rats 1, 3 and 6. So if those exactly three rats die the next day, you know that cookie 37 was the poisoned one.

Answer 2

I think I got it.

Imagine a binary tree with the 1024 cookies as the root (This number just comes out cleaner, but this will work for any number less than 1024). Break that 1024 cookies into two groups of 512, each of those groups is the child of the root. Then break each of those groups of 512 into groups of 256 and let those be the children of each of them and so on. You should end up with 11 levels of the tree.

Assign each rat to a level of the tree except the root. Each rat will eat only the cookies on the left branches of their level. The next day, iterate through the tree and for each rat that died, follow the left branch, for each rat that lived, follow the right branch. The resulting cookie should be the poisoned one.