King Cake

A king wants to hold a festival, for which he is inviting 1000 guests. As a tradition, each guest will bring the king one mini cake. However, news reaches the king that one of the guests has given the king a poisoned cake. Unfortunately, the king has no idea which cake is the poisoned one.

The king has 10 prisoners he plans to execute and decides to use them to taste test which cake contains the poison. The poison, when consumed, has no effect on the prisoner until 24 hours later when the infected prisoner suddenly dies. The king needs to determine which cake is poisonous by tomorrow, and has time for one round of testing. How can the king administer the cakes so that in 24 hours he is guaranteed to know which cake is poisoned?

My attempt:

If he just simply wants to avoid eating the poisonous cake, he could just assign each of them 100 cakes to eat and whoever dies, you know to avoid those 100 cakes. However, the question states he wants to guarantee which cake is poisoned. My initial reaction to this problem is to consider some sort of overlap such that multiple prisoners will die after eating the same cake. Perhaps some sort of binary search could work. Take two prisoners that eat $cakes_i$ where \(i=1,..,500\) and \(i = 501, ..., 1000\) respectively. Then take 4 more prisoners and divide those cakes up into fourths. Hmmm, but this approach does not work with only 10 prisoners.

Solution found online:

Since \(2^{10} = 1024 > 1000\), we have enough combinations of prisoners eating different combinations of cake to uniquely identify which cake is poisonous. Assign each cake a unique binary code of 10 digits, so say for cake 3: its code is 01100010110, then B, C, and so forth would eat the cake.

Takeaway:

Think about power sets, cardinality, combinations, and binary encoding.