Saturday, November 20, 2010

[Puzzle] Poisoned wine: Fun with bases

Puzzle: Poisoned Wine
You have 240 barrels of wine, one of which has been poisoned. After drinking the poisoned wine, one dies within 24 hours. You have 5 slaves whom you are willing to sacrifice in order to determine which barrel contains the poisoned wine. How do you achieve this in 48 hours?

(Please try the puzzle before you skip to the solution mentioned at the bottom of this page.)

We are gonna play with number bases this time. Hope you are familiar with them, or else you will not understand a bit after this sentence (Apologies. Thanks.).

So, we have 5 slaves. Lets just forget about number of barrels and also assume that we have only 1 day. One day and five slaves, thats it. Can we determine how many barrels can we solve with our new constraints? Yes, we can. Lets see how:
Five slaves and one chance. They must drink in a fashion that covers all the barrels and drink in a unique way i.e each barrel must be drank by a unique set of slaves, so that when some slaves die, we can determine which barrel went down their bloods.
Now, any slave either drinks a barrel or doesn't. Only two options. This reminds of binary systems, and we treat each slave as a binary bit. 5 slaves (read bits) means a total of 2^5=32 numbers. Thats our answer, 5 slaves can only drink 32 barrels in a completely unique way (just like 5 bits can represent 32 numbers uniquely). So here's how we would have solved the problem with 32 barrels:
Represent the barrels index number in binary (zero-indexed). So,
Barrel-0: 00000
Barrel-1: 00001
Barrel-2: 00010
Barrel-31: 11111

Also, lets assume five slaves namely a,b,c,d, and e. Lets say e is the least significant bit slave. So slave-e will drink whenever the LSB is set to 1. Similarly slave-d drinks whenever 2nd bit from right is set to 1 and so on.
So, no one drinks Barrel-0.
Barrel-1 is drank by Slave-1
Barrel-2 is drank by Slave-2
Barrel-31 is drank by all.

Now, just let everyone drink according to the logic decided above. At end of day, we can determine the corrupted barrel by seeing who all died and since the drinking-sets were unique we know the answer pretty easily. We bring back the 5-bit number terminology we used for numbering the barrels and set the bits with value as 0, if the slave did not died and 1, if died. For eg. if slave-c and slave-e dies, then we have:
a b c d e -Slaves
0 0 1 0 1 - Died or not
which is the number 5 (00101b)
Hence, barrel-5 is the corrupt barrel.

So far, if you have understood the solution to our sliced-puzzle, you are good to go.

Ok, so now, 5 slaves, 2 days/chances and 240 barrels. Thats huge numbers.

We stick to our approach and try to scale it up.
We still have 5 slaves, so the number of bits cant scale up definitely.
We have 2 chances, one more than we had in our sliced-puzzle. So, now either a slave doesn't drink the wine at all, drinks it the first day OR, OR... drinks it the next day (if he is lucky enough to see the next day).

Time to scale up the base now. So we have base-3 now. Slaves have states 0,1 or 2 (0: Never drinks, 1: drink on day-1, 2: drink on day-2). And we can solve 3^5=243 barrels with this!!! Lets just number up the barrels again in the new base now:
Barrel-0: 00000
Barrel-1: 00001
Barrel-2: 00002
Barrel-3: 00021
Barrel-243: 22222 (We wont be needing the last 3 barrel numbers as we have just 240 barrels in hand)

Now let all slaves drink the wines as per the new logic.
So, no one drinks Barrel-0.
Barrel-1 is drank by Slave-1
Barrel-2 is drank by Slave-1 on second day
Barrel-243 is drank by all on second day. (This does not exist as per puzzle, meant just for illustration)

Also if anyone dies on day-1, and was supposed to drink some barrel the next day but has died already, you can ignore them (for eg. everyone must drink barrel-243 next day, but it is quite possible that some slaves already died.)
So, all slaves drinks two days and then we fill up our table with who died when (0: Did not died; 1: Died on day-1; 2: Died on day-2)
So if slave-a died on 2nd day and no one dies on day 1 either, we have:
a b c d e - Slaves
0 0 0 0 2 - Day when died
which is number-3 and hence the Barrel-3 is corrupted.

The solution was presented in such a level of detail, so that the readers can appreciate the beauty of the solution and extend/scale it further to various other puzzles/daily-problems!

No comments:

Post a Comment