Tue Jun 28, 2011 1:30 pm by sriramadesikan 


The Emperor(1000 wine bottle puzzle)
The Emperor puzzle description:
You are the ruler of a medieval empire and you are about to have a celebration tomorrow. The celebration is the most important party you have ever hosted. You've got 1000 bottles of wine you were planning to open for the celebration, but you find out that one of them is poisoned. The poison exhibits no symptoms until death. Death occurs within twenty four hours after consuming even the minutest amount of poison. You have over a thousand slaves at your disposal and just under 24 hours to determine which single bottle is poisoned. You have a handful of prisoners about to be executed, and it would mar your celebration to have anyone else killed. What is the smallest number of prisoners you must have to drink from the bottles to be absolutely sure to find the poisoned bottle within 24 hours?
Solution:
Assumption:
Even a drop of wine is so powerful that it doesnt get diluted when added to a bottle full of wine and the whole wine in that bottle becomes as powerful as that of the poison. The casualty, on drinking even a drop of poison occurs in second precision.
Overview:
10 Prisoners are put to test. First, they have to drink from 100 wine bottles each. For example, first Prisoner takes a mixture from 1100 bottles. Then, he takes a mixture from bottles of corresponding 10s in each of the 10 groups of 100 bottles (10 groups are: 1100, 101200, 201300,...). That is, he takes a mixture of 110, 101110,201210 and so on. Finally, he takes a mixture from corresponding unit digit bottles. That is, as he is numbered 1, he takes a mixture of 1, 11, 21
101,111,121
201,211,221 and so on. Similarly all the other Prisoners also drink the respective mixtures.
By the way, each prisoner takes wine from 271 bottles.
In detail:
Out of 1000 Prisoners, select 10 agile but unfortunate Prisoners for this lethal test. Number them 1 through 10. Now ask each of them to pick any 100 wine bottles out of the 1000. First Prisoner operates 1100; second Prisoner operates 101200 and so on. Then, tenth Prisoner operates 9011000.
Now, instruct all the 10 Prisoners to arrange their respective 100 bottles in the following fashion (10X10) and to prepare the mixtures of bottles of each rows and columns as illustrated below.
GROUP 1 FIRST PRISONER WINE BOTTLES 1100
C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 RM
R1 1 2 3 4 5 6 7 8 9 10 RM1
R2 11 12 13 14 15 16 17 18 19 20 RM2
R3 21 22 23 24 25 26 27 28 29 30 RM3
R4 31 32 33 34 35 36 37 38 39 40 RM4
R5 41 42 43 44 45 46 47 48 49 50 RM5
R6 51 52 53 54 55 56 57 58 59 60 RM6
R7 61 62 63 64 65 66 67 68 69 70 RM7
R8 71 72 73 74 75 76 77 78 79 80 RM8
R9 81 82 83 84 85 86 87 88 89 90 RM9
R10 91 92 93 94 95 96 97 98 99 100 RM10
CM CM1 CM2 CM3 CM4 CM5 CM6 CM7 CM8 CM9 CM10
RRow, RMRow Mixture, CColumn and CMColumn Mixture
GROUP 2 SECOND PRISONER WINE BOTTLES 101200
C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 RM
R1 1 2 3 4 5 6 7 8 9 10 RM1
R2 11 12 13 14 15 16 17 18 19 20 RM2
R3 21 22 23 24 25 26 27 28 29 30 RM3
R4 31 32 33 34 35 36 37 38 39 40 RM4
R5 41 42 43 44 45 46 47 48 49 50 RM5
R6 51 52 53 54 55 56 57 58 59 60 RM6
R7 61 62 63 64 65 66 67 68 69 70 RM7
R8 71 72 73 74 75 76 77 78 79 80 RM8
R9 81 82 83 84 85 86 87 88 89 90 RM9
R10 91 92 93 94 95 96 97 98 99 100 RM10
CM CM1 CM2 CM3 CM4 CM5 CM6 CM7 CM8 CM9 CM10
.
.
.
GROUP 10 TENTH PRISONER WINE BOTTLES 9011000
C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 RM
R1 1 2 3 4 5 6 7 8 9 10 RM1
R2 11 12 13 14 15 16 17 18 19 20 RM2
R3 21 22 23 24 25 26 27 28 29 30 RM3
R4 31 32 33 34 35 36 37 38 39 40 RM4
R5 41 42 43 44 45 46 47 48 49 50 RM5
R6 51 52 53 54 55 56 57 58 59 60 RM6
R7 61 62 63 64 65 66 67 68 69 70 RM7
R8 71 72 73 74 75 76 77 78 79 80 RM8
R9 81 82 83 84 85 86 87 88 89 90 RM9
R10 91 92 93 94 95 96 97 98 99 100 RM10
CM CM1 CM2 CM3 CM4 CM5 CM6 CM7 CM8 CM9 CM10
Preparation of Row Mixtures (RM) and Column Mixtures (CM): The first Prisoner prepares the mixtures of 1st , 2nd, 3rd,
9th and 10th rows.
For e.g. RM2= 11+12+
19+20
Then he prepares the mixtures of 1st, 2nd
..9th and 10th columns.
For e.g. CM7= 7+17+
+87+97
All the other 9 Prisoners have performed the similar activities with their respective group of bottles at the same time.
Now, all the 10 Prisoners are asked to prepare a mixture of their respective column mixtures. (i.e., Mixture of CMs within the group). While preparing this, the first Prisoner is instructed to leave aside CM1 (The corresponding cell is highlighted in yellow); second Prisoner is instructed to leave aside CM2 so on.
Upon order to drink, all the Prisoners drink their mixture in hand at the same time.
The time of this drink is noted; exactly after 24 hrs (second precision), fall may occur.
Now, all the Prisoners are advised to prepare a mixture of row mixtures by walking through the other 9 groups. Accordingly, the first Prisoner has to prepare a mixture of RM1s available in all other groups. The second Prisoner has to prepare a mixture of RM2s present in all the other groups. Likewise all the 10 Prisoners prepare their respective mixture of row mixtures at the same time and are ready.
Upon order to drink, all the Prisoners drink their mixture in hand at the same time.
The time of this drink is noted; exactly after 24 hrs (second precision), fall may occur.
Now, all the Prisoners are instructed to prepare the mixture of similar column mixtures by going through all the groups from 1 to 10. Accordingly, the first Prisoner prepares a mixture of CM1s from all the 10 groups; second Prisoner prepares a mixture of CM2s and so on.
Now all the 10 Prisoners prepared the mixtures and are ready.
Upon order to drink, all the Prisoners drink their mixture in hand at the same time.
The time of this drink is noted; exactly after 24 hrs (second precision), fall may occur.
The time taken to prepare the mixtures is optimum and is sufficient to distinguish the time of falls and the corresponding round of drinks.
There are only 3 rounds of drinks and so there may be a maximum of 3 falls occurring in 3 slots and not more than that.
Analysis: Exactly 24 hrs after the first round drink, if suppose the first Prisoner falls, then we ascertain that the poison bottle is in the first group. That is, among 1100. Then exactly 24hrs after the second round drink, if suppose the second Prisoner falls, then the poison bottle lies between 1120. Again exactly 24hrs after the third drink, if suppose the third Prisoner falls, then the poison bottle is the 13th one! In the above scenario, if the fall of second and third Prisoners is interchanged, then the poison bottle is the 22nd one.
For any set of 3 Prisoners out of 10, we have 10C3 = 120 combinations. Each combination covers 6 bottles.
So, totally 120X6=720 bottles are covered.
If only 2 Prisoners fall, the first Prisoner in the first round and the second Prisoner in the second round, then the poison bottle is the 12th one.
If the second Prisoner falls in the third round, then the poison bottle is the 2nd one. If the second Prisoner falls in the second round and the first Prisoner falls in the third round, then the poison bottle is the 11th one.
For a given set of 2 Prisoners and 3 falling time slots, 6 bottles are covered. We have totally 10C2 Combinations.
10C2=45 combinations.
So, 45X6=270 bottles are covered.
Now if only one Prisoner falls (one Prisoner falls in the third round and no one falls in the first 2 slots. This is the only possible scenario for the way the mixtures are prepared and rounds of drink administered).
Suppose the first Prisoner falls in the third slot and no falls in the first 2 slots.
Then the first bottle is the poisonous one! (Highlighted in green). No other Prisoner had it in their 3 drinks.
Similarly, if the second Prisoner alone falls, then the poison bottle is the 112th one.
So ten numbers are covered in the case of only one fall as there are 10 different possibilities.
The 10 bottles are 1, 112, 223, 334, 445, 556, 667, 778, 889, 1000(forms a series with a difference of 111. Any significance of this series?)
111=100+101+102.
For 3 falls, we have 720 bottles covered
For 2 falls, we have 270 bottles covered
For one fall, we have 10 bottles covered.
Totally, 720+270+10=1000 Bottles.
PS: For any given positive integer N, N3 objects can be tested to find an odd one by employing N test objects.
We also get the above series for any positive integer N with a common difference of N2+N+1.
Geometrically, the terms in the above series represent the unit cubes in the cube N3. They are the intersections of the respective 3 planes of unit height. They form a pattern diagonally.
The tabular colums are not displayed as desired. Please get the original word version of the solution by sending an email to [b]sriramadesikan@gmail.spam [/b]
Thank You!
Last edited by sriramadesikan on Thu Aug 18, 2011 12:40 pm; edited 1 time in total 

