# 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.

Before 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.

Each switch is known as a

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

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)

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.

Is 93 bigger than or equal to 128, No, so that is a

Is 93 bigger than or equal to 64, Yes so that is a

Is 29 bigger than or equal to 32, No, so that is a

Is 29 bigger than or equal to 16, Yes so that is a

Is 13 bigger than or equal to 8, Yes so that is a

Is 5 bigger than or equal to 4, Yes so that is a

Is 1 bigger than or equal to 2, No, so that is a

Is 1 bigger than or equal to 1, Yes so that is a

01011101 = 64 + 16 + 8 + 4 + 1 = 93

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

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.)

Note: no information is sent to me, the calculation is done entirely locally, on your computer.

Binary is in base 10

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 |

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 keep in mind the binary sequence 128, 64 , 32, 16, 8, 4, 2, 1 and the number your trying to convert. It's difficult to explain so let just work an example. Consider for example '93.' We askIs 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 forIs 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 = 13Is 13 bigger than or equal to 8, Yes so that is a

**1**we now have to account for 13 - 8 = 5Is 5 bigger than or equal to 4, Yes so that is a

**1**we now have 5 - 4 = 1 to account forIs 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.)

Note: no information is sent to me, the calculation is done entirely locally, on your computer.

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:)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.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 takesonemonth to have an effect. The bad king decides he willget some of the prisoners in his vast dungeonsto 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 ?

© 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 inquire using the link at the top of the page. Secure version of this 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