Of Kings and prisoners !

A king is gifted thousand barrels of wine by his sadistic arch rival. The rival attaches a note saying that exactly one of them is poisoned. Our king, a connoisseur of fine wines, would hate to throw them all away since there are 999 good barrels of wine.

The king has 10 prisoners to 'experiment' with. So he comes up with a mix of wine from different barrels for each one of them, and simultaneously has all the prisioners drink from their respective glasses. The poison takes effect in 10 minutes. Once that time has passed, the king notes who is alive and who isn't and deduces the barrel that must be poisoned ! Note that there is no second round of experimenting the with prisoners who survive the first round ordeal. So what scheme did he employ ?

Discussion - A simple first thought would be this - Take a small bit of wine from each of the first 100 barrels, mix them, and feed it to the first prisoner. Take a little from the each of the next 100 and feed it to the next prisoner, and so on. Depending on which prisoner dies, we can narrow down to 100 barrels, one of which we know is poisoned. But this is not a very good solution, since those 100 barrels must be thrown away. But our king, a demanding boss, wants the exact barrel to be narrowed down to in one shot. So how can we improve this ?

Actually, I got to know of this question a long time ago through word-of mouth, and I haven't seen a solution. I did come up with a solution that is more likely to be arrived at by electronics or computer science engineers ( Now that's a hint :-) , but I'm curious to see if people have other different schemes .

Solution - We need a solution that can uniquely identify one barrel from 1000, and we have 10 prisoners to experiment with. We note that two raised to the power of 10 is 1024. That is, we can represent 1024 different states using 10 bits ( binary digits ), much like we can represent 100 states using two digits. The motivation for using binary numbers comes from the fact that each bit can take only two values - 0 or 1, which  we can use to neatly encode the states 'alive' or 'dead' respectively.

To do this, write down the binary equivalent for all numbers from 1 to 1000. I have shown this in the table below for a few numbers. The 10 bit-positions correspond to the 10 prisoners. Look at any one column, say for prisoner p2 ( in blue ). We note all the entries in that column which contain a '1'. We note all the corresponding barrel numbers, mix up their contents and feed it to prisoner p2. This includes barrels 2, 3 and 991 besides many others that are not shown in the figure. Do this separately for each prisoner. You should find that all prisoners drink from roughly 500 barrels ( though the combination is unique for each prisoner). I say roughly because, it would be exactly 512 if there were 1024 prisoners. Here, since we have only 1000 barrels, we are operating in the truncated part of the set, and we'll see some artifacts.

Now, we will construct the binary number whose decimal equivalent will reveal the poisoned barrel. To do this , note the state of each of the prisoners. If they are alive, set the bit position to '0' , else set it to '1'. For example , we construct the binary number 1111100000 if prisoner p1 to p5 are alive, and the rest aren't. Now, just find the decimal equivalent of this - for this example, it would be 992. Essentially, we are using each prisoner's state to extract one bit of information that will point us to the right barrel. Do let me know if somebody has a different solution.