The riddle of dictator and of bottles of wine is a famous problem of logic. A dictator must find out which bottle, among the 1000 in his possession, was poisoned by a killer. To do this he is only 24 hours and can use 10 prisoners sentenced to death as tastings. The only certainty it has is that a single drop of poisoned wine is enough to kill an adult. How will you find exactly the contaminated bottle?
This riddle is not just a logic game: it is an example of Group Testinga technique for individuate quickly a defective element within a very large group. Born in the medical field, this procedure is still used today in sectors such as telecommunications and the cybersecurity. In this article we see what the solution used by the dictator was and how this strategy applies to real problems.
The riddle of the dictator and bottles of wine
The situation is this: a cruel dictator he organized a great party in his country and, for the occasion, he got 1000 bottles of wine Precious. It is discovered, however, that a murderer sneaks into the cellars and has poisoned one And only one of the bottles. The poison injected by the murderer is colorless, odorless and without symptoms until death, which arrives among the 10 and 15 hours later Ingestion. There is no way to identify the contaminated bottle if not making it drink to someone and only one drop of poison is enough to kill an adult person.
The dictator has 10 prisoners sentenced to death and decides to use them for test the wine. His first idea is to divide the bottles into 10 groups of 100 and to make each condemned a drop of each bottle of the group drink. So, the first condemned would drink 100 drops taken from 1-100 bottles, the second 100 drops from 101-200 bottles, the third 100 drops with 201-300 bottles and so on. Upon the death of one of the condemned, the dictator will get rid of the 100 bottles from which he drank that condemned and will be able to use the remaining 900.
The dictator, however, would like to save even more bottles. A trusted councilor then intervenes who suggests a solution for Find the poisoned bottle exactly. Let’s see what it is!
The solution: use the binary code
To understand the solution of the director we must think how computers, that is in binary system. Unlike the decimal system, which we use every day and is based on ten digits (from 0 to 9), the binary system uses only on two digits: 0 and 1.
Let’s try to describe our problem using only 0 and 1, starting from the condemned. Each of them can do two actions: drink or Don’t drink from a bottle. So, we can represent their actions with a 1 (drink from the bottle) or one 0 (does not drink from the bottle). Let’s look at the bottles now.
Numerous bottles using the binary system. In the decimal systemwhat we are used to using, each position corresponds to a different power of 10: the right figure corresponds to 100 (i.e. 1, the units), then there is 101 (i.e. the tens), then 102 (i.e. hundreds) and so on, gradually increasing the exponent of one. There figure (from 0 to 9) that we read in every position tells us how many times we have to consider that power. For example, the number 34 is made of 4 times 100 ie 4 · 1 = 4 and 3 times 101 that is 3 · 10 = 30. If we add 30 and 4, we get 34.
To write a number in trackswe think in a similar way, but the Powers of 2not 10. In this case, the most right figure corresponds to 20 (ie 1), on his left we have 21 (ie 2), then 22 (ie 4) and so on. Here too the figure that we read in every position tells us how many times we have to consider that power, but in this case we have only two possibilities, that is 0 (do not use that power) e 1 (use).
Resuming the number 34on track it is made by: 0 times 20that is 0 · 1 = 0; 1 time 21 that is 1 · 2 = 2; 0 times 22that is 0 · 4 = 0; 0 times 23that is 0 · 8 = 0; 0 times 24that is 0 · 16 = 0; 1 time 25that is 1 · 32 = 32. By putting everything together, we have 34 written in track is 100010. In fact, if we add 32 + 2 we get 34.
We label then the bottles in track. On the labels we will therefore see the numbers from 1 (number 1) to 1111101000 (number 1000).
At this point, we take the ten condemned and put them in line. Each condemned will represent one power of 2. The most condemned on the right will be 20 (i.e. 1), the one more left 29 (ie 512).
Now we take each bottle and read the label with the number in binary code written above. Let’s give then a drop To drink to all condemned found in the positions in which There is a “1” (which corresponded to “drink”). For example: the number 4 bottle will have 00000000100 (4 in track) written on the label. So, a drop of that wine to the third condemned from the right will be made to drink, because there is a 1 in third position. For the 295 bottle (0100100111) we will give a drink (starting from the right) to the first three, in the sixth and ninth sentenced.
Done this, it will be enough for us wait up to 20 hours e see which condemned they die. If they died, for example the condemned in position 2 and 6, we would know that the poisoned bottle is the one that wrote 0000100010 on the label, that is the bottle number 34.
Using this strategy, we will be able to get the number exactly from the poisoned bottle And we will therefore be able to save the other 999.
How to find the “errors” in a large group: what is the Group Testing
This type of reasoning is an example of what is called Group Testingor group test, a procedure in which you try to identify “defective” elements (in our case, the poisoned bottle) within a very large whole. Usually, this type of test is done with more than one “defective” element and consequently becomes more complex than the example we have reported here.
The first formulation of the Group Testing dates back to 1943, during the Second World War. He was invented to solve a critical problem during the lever: test tens of thousands of recruit for the syphilis. To reduce the number of tests necessary, the serum samples of many soldiers together were collected and the entire group was analyzed, instead of testing each recruit individually. The Group testing principle also found application in other areas. For example, it is used to manage the sharing of channels between devices of radio communication. Also in the field of information technology and the cybersecurity A similar approach is used to discover errors or vulnerabilities in large complex systems.
The principle at the base is always the same: to minimize the number of tests necessary using the best strategy, as the councilor with the bottles of wine did.
