<< Previous Article

There are very many puzzles around, involving binary choices, or so called yes-no, true-false, … situations. Here is one such.

Puzzle #3: There was a king who got 1001 identical dishes prepared for his 1000 guests and himself. But one hour before the guests were to arrive, he was informed that out of the 1001 dishes, one has got poisoned. And whoever even tastes it would die in an hour. Moreover, which dish is poisoned was not known. Now, the king has few taster slaves, who could be made to taste the dishes, and figure out which dish is poisoned. But the problem is they were only few, not 1001. So, the question is what is the minimum number of taster slaves required to figure out the poisoned dish?

As usual, think through before you peek into the solution.

Here are some hints, if you have tried for some time.

Note that the outcome of tasting a dish is binary – the taster either dies or doesn’t die.

Work on some pattern in deciding who should taste which dish.

Number the dishes from say 0, 1, …, 1000.

Think. Think.

Ok. Got it. Good. Not yet. What if there are only 10 taster slaves? Can it be solved?

That’s more than enough hints.

By now, you might have at least tried various combinations, say like arranging 1000 dishes in an 10 x 10 square, and making n’th slave taste all dishes in n’th row and n’th column etc. If not, go ahead and try it.

And here’s finally one way of doing it.

Number the 1001 dishes from 0 to 1000, but in binary using 10 bits, as 10 bit can represent numbers from 0 to 1023. So, the numbering would be like 0000000000, 0000000001, …, 1111101000. Then, label the 10 taster slaves from 0 to 9. Now, let the i’th slave taste all the dishes, the binary representation of which has a 1 in its i’th bit position. After one hour, note down the labels of all the taster slaves which die. Create a 10-bit binary number with all its bit positions corresponding to those labels, set to 1. Now, whichever dish has the number matching with this created number, is the poisoned one.

Does it make sense? If not, please ping in the comments.

If you have got any other interesting way of solving it, then also please share it in the comments.

Anil Kumar Pugalia (123 Posts)

The author is a hobbyist in open source hardware and software, with a passion for mathematics, and philosopher in thoughts. A gold medallist from the Indian Institute of Science, Linux, mathematics and knowledge sharing are few of his passions. He experiments with Linux and embedded systems to share his learnings through his weekend workshops. Learn more about him and his experiments at https://sysplay.in.

   Send article as PDF