Answer to Riddle #61: Finding the Poisoned Bottle of Wine

61. A bad king has a cellar of 1000 bottles of delightful and very expensive wine. A neighbouring queen plots to kill the bad king and sends a servant to poison the wine. Fortunately (or say unfortunately) the bad king's guards catch the servant after he has only poisoned one bottle. Alas, the guards don't know which bottle but know that the poison is so strong that even if diluted 100,000 times it would still kill the king. Furthermore, it takes around a month to have an effect. The bad king decides he will buy some slaves to drink the wine. Being a clever bad king he knows he need only buy 10 slaves and will still be able to drink the rest of the wine (999 bottles) at his anniversary party in 5 weeks time. Explain what is in the mind of the king, how will he be able to do so ?

If you understand binary numbers you're probably pretty confident about this. If not I'm sure it's quite foreboding in the sense that you would have to do a lot of the work for yourself.

a bottle of wineBefore reading the answer can I interest you in a clue?

We are going to have to find a scheme where by we use only 10 prisoners and by feeding them some of the wine in some way, from who dies, we'll be able to identify which exactly is the poised wine. That's what we extract from the verbiage of the puzzle. We're going to use binary numbers, so lets take a look at them, how they work, what they're for. I'll write it assuming you know nothing, if you know lots then feel free to skip it, if you think you could use refresh then read on.

Binary

Binary is a system for storing numbers in a way that can be managed by computers. Conventional computers store information on a series of switches that are on or off, up or down or more usually described as 1's or 0's. The memory on the computer I'm writing this on consists of 137,438,953,472 switches or 16GB of memory.

Each switch is known as a bit. Because of the restriction that computers can only store 1's or 0's computer science has found ways of converting everything you tweet, every game, every photo in to 1's or 0's. The basis of that is encoding numbers...

In fact binary is just a base 2 counting system along the same lines of our more familiar base 10 system. In base 10 you have 10 digits available to you, (0-9) in base 2 you have 2, (0&1.)

Consider a regular number in base 10 lets say 56,132, each digit represent a value that we can tell by it's position or how far from the right it is. The 5 represents 5 lots of 10,000, the 6 represents 6 lots of 1000, the 1 represents 1 lot of 100, the 3 represents 3 lots of 10, and the 2 represents 2 lots of 1.

Binary works much the same. On the right hand side the last digit represents the units and as we move one place left, where as in base 10 we multiplied by 10 for each digit, in this case we multiply by 2, so the next digit left has a value of 2, the one left of that 4, left of that 8, 16, 32, 64, 128 and so on. In school I was taught to think about the Thousands, Hundreds, Tens and Units, in Binary it would be the 8's 4's 2's and units.

Traditionally we work in groups of 8 bits, called a byte. There's nothing special about this. It's just convention. The significance of the bits from the left is 128, 64, 32, 16, 8, 4, 2, 1. In binary we write out all the digits so the number 9 say, that has 1 in the 8 column and 1 in 1 column is written 00001001 rather than 1001. There's a good reason for this, it's to do with preallocation of the memory resources.

The maximum value for an 8bit binary number is 11111111 or 255 in decimal. That means there are 256 combinations (0-255)

Binary to Decimal

128 64 32 16 8 4 2 1
0 1 0 1 1 1 0 1
Pause
01011101 = 93 = 64 + 16 + 8 + 4 + 1

Converting from Binary to decimal is easy enough, we just add the values of the decimal numbers where there's a 1 in place, if you javascripting enabled there should be examples ticking away above to make the point.

Decimal to Binary

This way is a little harder. You need to have in mind the binary number 128, 64 , 32, 16, 8, 4, 2, 1 in mind. It's difficult to explain so let just work an example. Consider for example '93.' We ask
Is 93 bigger than or equal to 128, No, so that is a 0
Is 93 bigger than or equal to 64, Yes so that is a 1 we now 93 - 64 = 29 to account for
Is 29 bigger than or equal to 32, No, so that is a 0
Is 29 bigger than or equal to 16, Yes so that is a 1 we now have to account for 29 - 16 = 13
Is 13 bigger than or equal to 8, Yes so that is a 1 we now have to account for 13 - 8 = 5
Is 5 bigger than or equal to 4, Yes so that is a 1 we now have 5 - 4 = 1 to account for
Is 1 bigger than or equal to 2, No, so that is a 0
Is 1 bigger than or equal to 1, Yes so that is a 1 and everything is accounted for.
01011101 = 64 + 16 + 8 + 4 + 1 = 93

I hope that's clear. If not the tool below will enable you to try different numbers.

Back to the Wine and the Slaves

If there are 256 combinations of 8 bits then by adding another bit at the front there are necessarily 512. That is all the 8bit combinations with a zero in front and all the same with a 1 in front.

Do the same again and clearly 10bit numbers have 1024 possible combinations. Which brings us nicely back to our problem, all the pieces are there we just need to state it explicitly.

We will number the bottles 1 - 1000. We will number the 10 slaves, 1, 2, 4, 8, 16, 32, 64, 128, 256 & 512. For each bottle of wine we will open it, convert it's number to binary and give a drop to the corresponding slave. 4 weeks later when some of the slaves have died we will decode the binary sequence back to the bottle of wine. The tool below should help demonstrate how this works, (you can toggle the ✓'s and ✗'s.)

Binary is in base 10

512 256 128 64 32 16 8 4 2 1

Assumptions

This is an unusual case in that the question is so long it sort of deliberately covers all the angles, for example the strength of the poison means you can't mix all the bottles together. The delay means you can't have one person sip all the bottles. There is very little to assume. Notwithstanding that I have to thank Nicolas Larreteguy and Jaisal for pointing out a couple of problems with the original wording of this question (below:)
61. A bad king has a cellar of 1000 bottles of delightful and very expensive wine. A neighbouring queen plots to kill the bad king and sends a servant to poison the wine. Fortunately (or say unfortunately) the bad king's guards catch the servant after he has only poisoned one bottle. Alas, the guards don't know which bottle but know that the poison is so strong that even if diluted 100,000 times it would still kill the king. Furthermore, it takes one month to have an effect. The bad king decides he will get some of the prisoners in his vast dungeons to drink the wine. Being a clever bad king he knows he needs to murder no more than 10 prisoners - believing he can fob off such a low death rate - and will still be able to drink the rest of the wine (999 bottles) at his anniversary party in 5 weeks time. Explain what is in the mind of the king, how will he be able to do so ?
I have highlighted the two key changes, respectively in order, it might be worth seeing if you can work out the problem. I don't normally like to change the questions once I have written them but I have a feeling this was a translation error as it always included the line about 10 prisoners and I don't think it necessarily fair to have the ambiguity.





© Nigel Coldwell 2004 -  – The questions on this site may be reproduced without further permission, I do not claim copyright over them. The answers are mine and may not be reproduced without my expressed prior consent. Please enquire using the link at the top of the page.
 


PayPal
I always think it's arrogant to add a donate button, but it has been requested. If I help you get a job though, you could buy me a pint! - nigel




This Website Uses Cookies

Mostly, but not entirely to remember if you have dismissed this very box. Also to increase the functionality of the site. The cookies I apply do not uniquely identify you, by continuing to use this site you agree to let me place a cookie. I also have advert and analytics providers, for more information click here here.x