Interview Question
A great solution indeed! What I would like to clarify here to others is why he has chosen amounts like 16 for each individual,8 for each pair and so on.
The reason being if only a single slave ,say s2, dies after the first day, the remaining 4 slaves can be used to decide which barrel did he exactly die from in the second day(16 barrels = 4 bits). Similarly if only a pair of them dies, 1 among the 8 barrels can be decided by remaining 3 slaves and so on.
Thanks Vishesh for both the appreciation (for me) and the clarification (for others)... I always felt the way I had expressed my solution wasn't so self-explanatory...
in the above solution say you have given the 16 barrels to slave s1 and let us assume it has poison so your solution states that we could check those 16 barrels with the remaining slaves and determine the poison but once you have given the 16 barrels to the slave s1 then ow could you give it again to the other four slaves to check for poison please clarify this doubt
How would you defend your strategy against the following arguement:
in general, you don't have enough information to determine which barrel is poisoned:
In worst case(all die), the information you can get from the result of you experiments on 5 slaves is at most 5 bits, but you need log_2(240) bits information in total to clear the uncertainty.
How would you defend your strategy against the following arguement:
in general, you don't have enough information to determine which barrel is poisoned:
In worst case(all die), the information you can get from the result of you experiments on 5 slaves is at most 5 bits, but you need log_2(240) bits information in total to clear the uncertainty.
@geniusxsy: 1. d first part of ur analysis is not true... d information i can get frm 5 slaves in 24 hrs is 5 bits but the information i can get frm 5 slaves in 48 hrs is far more than 5 bits... think about dat!!!
2. d 2nd part of ur analysis is true, i need log_2(240) = 8 bits of information to clear the uncertainty in THE WORST CASE... But in that particular case my strategy makes sure that all the slaves will not die after the first dose (of course, under the assumption that exactly one barrel has poison)... If u read the strategy carefully u wil find that in the first dose only one barrel is shared among all five of them, so if all five die, i can clearly pinpoint the only barrel shared between them to be the one that has poison... There is a set of 2 barrels that is shared among each combination of 4 slaves, (say for eg. s1, s2, s3 and s4 all hav b201 and b202 common) so if those 4 die (thus i hav one slave alive) i can pinpoint the poisoned barrel to be among the set of 2 barrels that those 4 had commonly shared. I stil hav 1 slave alive and 24 hrs left, i can feed that slave, one barrel among the two nd if he dies, it is the one i fed him that has poison but if he doesn't the other one that i did not feed him has poison... Similarly there is a set of 4 barrels for each combination of 3 slaves, a set of 8 barrels for each combination of 2 slaves, a set of 16 for each slave individually and at most i can have 5 bits (32 barrels) unused so that they can be determined in d last 24 hrs... thus i can determine this for atmost 16 x 5 + 8 x 10 + 4 x 10 + 2 x 5 + 1 + 32 = 243 barrels... i question asks for only 240 barrels so i can easily determine that...
in short the information here is not binary any more... its in ternary terms... say i hav 5 elements (slaves) where each element could be {0,1,2}... 0 if the slave does not die after 2 days, 1 if the slave dies after the 1st dose, nd 2 if d slave dies after the 2nd dose... thus i hav 3^5 = 243 possible combinations as my strategy correctly predicts...
Follow Bhavik idea:
1. With 3 bits (or slaves), we can represent 8 possible events( or barrels).
With 4 bits, 16
With 5 bits, ....... 32
2. -index 240 barrels from 1..240, 5 slaves from A,B,C,D,E
First pass:
00000(no one dead): represent 1 ..32 (32 barrels) since 5 slaves go to 2nd pass
00001(A dead) : 33..48 (16 ) 4 slaves 2nd
00010 (B dead) : 49..64 (16 )
00011(A and B dead) 65..72 (8 )
...
11110(BCDE dead) :
lol
it's not exactly binary, because we need 8 slaves for that. we need to play with the times. so lets try trinary
the first slave will drink from a 1rd of the barrels, after 24 hours he'll drink from another third.
the 2nd slave will drink from a third of each part the former has drank...we go on till the very last slave.
and so on, so we have 3^5 = 243
after 48 hours we could figure out exactly which barrel is poisoned
Bhavik's solution is correct but its best understood if its explained starting from all 5 slaves sharing 1/5 of same barrel.
1.Lets share 20% barrel1 to S1,S2,S3,S4,S5. [This is to achieve this:If all of them die at the end of 24th hour, its barrel1 which is poisoned]
2.Lets share (barrel2+barrel3) equally among S1,S2,S3,S4. If we continue like this, we have spent 2*10=20 barrels.
3.Lets share (barrel12+barrel13+barrel14+barrel15) equally among S1,S2,S3. If we continue like this, we have spent 4*10=40barrels.
4.Lets share (barrel62+....+barrel68) equally among S1,S2. If we continue like this, we have spent 8*10=80barrels.
5.Lets share (barrel143+...+barrel159) to S1. If we continue like this, we will have spent 16*5=80 barrels.
That leaves us with 240-1-20-40-80-80 = 29barrels for next 24 hours.
If all the slaves die, Barrel1 is poisonous.
If (S1+S2+S3+S4) die, then (Barrel2+barrel3) is poisonous. With S5, we can easily find out whether Barrel2 or Barrel3 is poisonous!
Like this, we can move ahead!
I am thinking of something else. Since it wasn't told how much of poisonous wine is needed to kill a person in 24 hrs, I take the liberty of assuming just a sip of it would kill the slave. I will also assume the slave to sip a wine from a barrel for one minute. I will note the start time when he starts with barrel 1 and end time when he dies. When he finally dies, I will subtract 24 hrs from that time. The remaining minutes from the total duration would point me to the barrel.
Number the barrels 1 to 240 . Mix 1 & 2, 3 & 4, 5 & 6 and so on. Now there are 120 drinks (mixtures) formed. Then again number them 1 to 120. Mix 1 & 2, 3 & 4, 5 & 6 and so on. There will now be 60 mixtures (each mixture is derived from 4 top level barrels) . Another such step and we will have 30 mixtures ( derived from 8 top level barrels). So administer these 30 drinks to 5 slaves. Once you know which of these is poisoned, you will then need to find out which of the top level 8 barrels are poisoned. This leaves us with 8 barrels and 4 slaves. This can nowbe solved with 3 slaves ( one slave is extra !)
Step 1: Number the barrels from 1 to 240.
Step 2: Mix small quantity (which can kill a person) of wine from first 15 barrels, then next 15 and so on.
1-15, 16-30, 31-45, 46-60, .............196-210, 211-225, 226-240.
Doing so we will have 16 different sets of mixtures.
Step 3: Number the first (mixture of first 15 barrels) mixture as1, second as 2, and so on the last one as 16.
Step 4: Feed the slaves according to the binary number system, like the first mixture is feed to the first ,2nd to the 2nd , 3rd mixture to both the slaves 1st & 2nd and so on the last (16th mixture) to fifth slave only.
Step 5: Now after 24 hours we will come to know which mixture is poisoned and are left with only 4 slave alive to be tested on.
Step 6: Now number those 16 barrels from 0 to 15 and feed them from each barrel according to the binary number like 0 is fed to none, 1 one is fed to the first slave, 2nd to the second slave, and so on the 15 to all the four slaves.
Step 7: After next 24 hours we will come to know exactly which barrel is poisoned.
Do tell me if you find any error in the solution as this is my first ever comment to any problem, any suggestion is highly appreciated.
Split the total number (240) of bottles into groups of 16 each. This will yield
15 groups total (15*16). Number each group of bottles from 0-14, number the slaves from
0-3. On each group of 16 bottles write its corresponding binary number
0 - 0000
1 - 0001
2 - 0010
...
14 - 1110
Now make the slaves have wine from each group of 16 bottles if that group number
contains binary bits in the same positions as the slave's number (0-3). E.g. if
the salve number is 3 (B0011), he shall have wine from groups numbered 3, 7 and 11.
After 24 hours, we shall get the exact number of the group of bottles that contained
poison. Now we have 4 slaves left. Use them to find out the exact bottles among
the 16 bottles. I hope the idea is clear.
Binary codes have only 2 states (something or nothing) and since a binary representation requires (1/log 2) times the number of decimal digits to represent it, our problem could have been solved just by 24 hours if we had 10 testers instead of only 5.
Under ternary we have 3 states (nothing, something, another thing) and the highest number requiring 5 digits is 3⁵ - 1 = 242. Thus all 240 barrels can be uniquely coded up to 5 digits using the 3 states 0, 1, 2 which are going to mean respectively take nothing, take during 1st day, take during next day. The testers are thus aligned right to left and coded (made to take nothing, made to take on 1st day only, made to take on 2nd day only) as the digit position of the ternary representation of the number of the barrel. Thus after 2 days are over, a unique combination of death states (didn't die, died after 1st day only, died after 2nd day only) of the 5 testers will be recorded that will unfailingly identify the ternary number coding for the poisoned barrel in question.
its easy to solve but difficult to explain... before i start with the actual solution lets look at one specific sub-problem which wil make it easier to understand...
- Bhavik December 27, 2009if i had 8 barrels nd 3 slaves... i wud b able to determine it in 24 hrs... lets label d barrels b1 to b8 nd d slaves s1 to s3... i wud giv b1 to s1, b2 to s2, b3 to s3, b4 to both s1 and s2 (half-half), b5 to s2 and s3, b6 to s1 and s3, b7 to s1, s2 and s3 (one third each)... now in 24 hrs if only s1 dies, b1 had poison; if only s2 dies b2 had poison; if s1 and s2 both die but s3 is alive, b4 had poison; if all three die, b7 had poison nd if no one dies b8 had poison...
imp to note: we make 3 assumptions... 1. even 1/5th of d barrel of poison kills a slave... 2. all 5 of d slaves may die... 3. exactly one barrel has poison...
now extending this to 5 slaves, 240 barrels and 48 hrs...
i wil giv d slaves 2 doses of wine... one at d beginning nd 1 after 24 hrs...
at d beginning, i wil giv 16 barrels to each slave (total 5 slaves) i.e. total 80 barrels, i wil give half of 8 barrels to each combination of 2 slaves (total 10 combinations like s1 and s2, s2 and s3, s1 and s5 etc etc) i.e. 80 barrels {i wil divide say each of b101 to b 108 in halfs nd give half frm each to s1 and half frm each to s2; similarly i wil divide b109 to b116 in halfs nd give half frm each to s2 and half frm each to s3}, i wil giv one third of 4 barrels to each combination of 3 slaves (total 10 combinations) i.e. 40 barrels... i wil giv one fourth of 2 barrels to each combination of 4 slaves (total 5 combinations) i.e. 10 barrels ... nd i wil give 1/5th of 1 barrel to each combination of 5 slaves (only 1 combination) i.e. 1 barrel... nd i wil keep d rest 29 barrels as it is for d 2nd dose... (i.e. if none of the slaves die) d poison is in d rest 29 barrels nd not in d first 211 barrels... for d second dose i wil find exactly the set of barrels that might have poison nd distribute them among d remaining slaves alive...
Further information: i surmise that if the assumptions we made hold true, we can predict the poisoned barrel for {(d+1)^s} no of barrels... where d is the no of possible doses (24 hrs = 1 dose; 48 hrs = 2 doses) nd s is the no of slaves...
i understand that the above solution is difficult to understand, so if u need any further clarification feel free to post a comment here...