Solution
One can easily say that in the worst-case king will need 1000 prisoners, make every prisoner drink the wine, and whosoever dies will help him find the bottle with poison. So 1000 prisoners and 1 dies, but we have a condition that the king wants to minimize the number of prisoners.
So how to minimize prisoners?
Okay, you must have heard of the binary representation of numbers. So, we will use binary representation here to solve this problem.
First, let's discuss how we represent numbers in binary,
1 in binary 01,
2 in binary 10
3 in binary 11
4 in binary 100
5 in binary 101
6 in binary 110
7 in binary 111
8 in binary 1000
16 in binary 10000
32 in binary 100000
If we closely observe the pattern to represent all numbers that are less than 2n we need n bits. To represent numbers less than 4(22), we need 2 bits, to represent numbers less than 8(23) we need 3 bits. And all other numbers less than that power of 2 can be represented with the help of stated bits
To represent all numbers less than 512, we will need 9 bits, and for all numbers less than 1024, we will need 10 bits( and with 10, we can represent all numbers less than or equal to 1023). We will make all combinations of 0's and 1's in that 10 places to represent all numbers less than 1024.
Now think of these bits as prisoners' positions. If we make 10 prisoners stand in a row and we have all combinations of binary for each number less than equal to 1000, then it's easy to solve the problem.
Serve the very little amount of wine from each bottle, and make the prisoner drink the wine standing at a particular position for which the set bit at that position is 1(for that particular representation of bottle number).
For example, for bottle 1 we have representation 0000000001 so make one prisoner standing in the right position to drink the wine. For bottle 7, 0000000111, prisoners at position 1,2,3 will have the wine. In this way, all combinations can be made to 1000( since we have 1000 bottles only).
Wine will take 1 month to have an effect, and after that, some prisoners will die, and we can check from our combinations which combination has come into effect. Again the corresponding bottle number can be calculated, which will be the bottle with poisoned wine.
So we will need 10 prisoners, but it has been asked that maximum how many will die.
Let us now consider the number of prisoners who will perish in the worst-case scenario. That's the maximum number of 1 bits in a number ranging from 0 to 999. The number 511 is made up of 9 1 bits. 2^10 - 1 = 1023 is the first number with ten set bits. Because that is out of our range, a maximum of 9 prisoners, the king will sacrifice or kill for the experiment.
Check out this problem - 8 Queens Problem
Frequently Asked Questions
Can we solve the puzzle for 1022 bottles? Will the answer change?
No, the answer will not change since all numbers less than 1023 will require the same number of bits for their representation.
What will be the best-case scenario( how many minimum prisoners will die)?
The minimum number is 1 prisoner. Only one prisoner drinks the poisoned wine out of 10. It can be any binary permutation in which we have only one set bit.
Why should I practice puzzles?
Puzzles help you to improve your logical and problem-solving skills. Moreover, they are also asked in company interviews.
Do MNCs ask puzzles in the interview of IT companies?
Many tech giants like Google, Microsoft, etc., ask the puzzles in the interview process as they want to check your logical thinking.
From where can I practice more such puzzles?
You can refer to the conclusion section for links to puzzle sections.
Conclusion
In this article, we discussed a famous puzzle, 'prisoners and poison.' We hope that you enjoyed the puzzle, and this blog helped you to understand the puzzle well. If you liked it and want to solve some more, you can check out Top 150 Interview Puzzles.
Logical Puzzles:
Pattern Based Puzzles:
Recommended Readings:
Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, etc. on Coding Ninjas Studio.
Also check out some of the Guided Paths on topics such as Interview Puzzles, Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.
Happy Learning!
84+ registered 