Tag Archives: analysis

Poisoned Dish

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

   Send article as PDF   

Weighing Stones

<< Previous Article

Puzzle #2: A 40 kg stone was being delivered to a shopkeeper. On the way, it broke into 4 pieces. When he received them, rather than becoming angry, he was happy after analyzing them. Onlookers asked, “How are you happy even after this loss?”. To that, he replied, “Now these four pieces would be useful for me in an another way. I can use them with my beam balance to be able to weigh goods of all integral denominations from 1 to 40 kgs.”

So the question is, what are the individual weights of the four pieces of the 40 kg stone?

Like Puzzle #1, this also could be solved in many ways. Try solving it yourself before proceeding further to see the analysis.

The first attempt typically done to solve any puzzle is basically to understand the puzzle, by trying to observe and register some patterns about it. Same here. Say first piece is 1 kg. Second one is 2 kgs. Then, 3 kgs could be weighed using these two. So, say the third one is 4 kg. Then, 1 + 4 = 5, 2 + 4 = 6, 1 + 2 + 4 = 7. But then, we can’t get 8 etc as the fourth piece would be 33 kgs (= 40 – 1 – 2 – 4). So, seems like 1, 2, 4 must be even more apart. O! Just hold on. In a beam balance, we can weigh not only by placing weights on one side, but on either, and moreover on both sides. For example, placing 1 kg on one side, 4 kgs on the other side would also weigh 3 kgs. Ok. Let’s restart. Say, first piece is 1 kg. Let second be 3 kgs, as 3 – 1 would anyways be able to weigh 2 kgs. Note that, making the second one as 4 kgs may not be okay, as then how do we weigh 2 kgs. Now, 1 + 3 = 4. So, for the third piece, a way could be to get 5, when the first two are subtracted from it. That is, X – (1 + 3) = 5. Then, the third one would be 9. 9 – (1 + 3) = 5, 9 – 3 = 6, 9 – 3 + 1 = 7, 9 – 1 = 8, …, 9 + 3 + 1 = 13. That seems interesting, as just with three pieces, upto 13 kgs have been achieved. But then the fourth piece would be 27 kgs (= 40 – 1 – 3 – 9). Would that serve the purpose? Check it out. Is there any pattern? Post your comments.

Now, the idea of looking into such puzzles, is not to stop after solving them. But how can these be generalized. What is the maximum weight till which all integral denominations could be weighed if there were 5 pieces of any desired individual weights? And why 5? What if it is any “n”? Can we get an answer to it? If there is a pattern, it is highly likely to get a generalized solution for any “n”. Think through it, and you’ll be amazed.

Programmers rather prefer to think in terms of programming, to solve any problem at hand, even if it is a puzzle. So, what do you think? How can it be solved programmatically? Again, don’t jump to “n”. Let’s start with the initial 40 kg stone problem itself. And once we get an idea, it could be generalized.

One approach could be to generate all 4-tuples (a, b, c, d), such that a + b + c + d = 40. We may further restrict that all of a, b, c, d are distinct. And then for each such tuple, we may check, if all integral denominations upto 40 kgs can be weighed using them. How do we check? For that, all the different placement combinations for a given tuple (a, b, c, d) have to be tried. What are the possibilities? 3 possibilities per piece: 1) Do not use it, 2) Put it on the left side of the beam balance, 3) Put it on the right side of the beam balance. Seems like 3 * 3 * 3 * 3 = 3^4 = 81 possibilities for all the 4 pieces. Not bad. It definitely can be tried using a program. Go ahead. Give it a try. You may start with an empty array of 40 elements. And keep marking, which ever weight has been achieved by any of these combinations. At the end of trying all combinations for a particular tuple, if we have been able to mark all 40 elements of the array, then the tuple is definitely one of our possible solutions.

What if we remove the particular case of not selecting any of the 4 pieces, then total combinations are 80 (= 81 – 1). And the remaining 80 are actually duplicated, e.g. putting “a” alone on left side is same as putting it alone on right side of the beam balance, and so on. So, there would be actually only 40 (= 80 / 2) unique combinations. O! That seems to hint towards the possibility of achieving all integers 1 to 40.

This is just one thought. Obviously, other interesting thoughts may be applied. And that’s the intention of this writing. Please put it down in the comments to trigger further discussions. Who knows? You may come up with an optimal algorithm.

Next Article >>

   Send article as PDF   

Magical Pond

<< Previous Article

Decoding and solving puzzles has been there since very early days of mankind. And that has played a crucial role in the evolution of human brain. In the beginning, nature alone used to throw up puzzles for human brain to solve, for its mere existence itself. However, as human brain became more refined in thinking, analysis, and logic, it started creating its own puzzles, as well. So, today we have man-made puzzles and riddles as well, though many a times inspired from real life scenarios. Thus, inspired by the important role of puzzles in human life, and how have they been approached and solved in different ways, here is an attempt to present a semi-formal approach of logic analysis and problem solving in decoding puzzles. It would be attempted by picking up various sets of puzzles.

Puzzle #1: There is a square-shaped magic pond, which doubles the flowers dipped into it. On the four corners of the pond are four temples. A devotee comes with some flowers. She dips them in the pond. Flowers get doubled. Then, she offers some of those flowers in the first temple. She then again dips the remaining flowers in the pond. Flowers again get doubled. She then offers the same number of flowers in the second temple, as she offered in the first temple. Again the remaining flowers are doubled, and the same number of flowers are offered in the third temple, as in the second temple. And finally, the remaining flowers are doubled for the last time, and all of them are offered in the fourth temple. Interestingly, the number of flowers offered in the fourth temple is also same as that in the third temple. So, what is the minimum number of flowers the devotee would have brought, and what is the number of flowers offered in each temple?

Now, there could be many approaches to solve this puzzle. Try solving it yourself before proceeding further to see the analysis.

The first attempt typically done to solve any puzzle is basically to understand the puzzle, by trying to observe and register some patterns about it. Same here. So, one would start trying with some numbers. Say she came with 1 flower, doubled it to 2, then offered 1, and continued so forth till fourth temple. But then, if the fourth temple is also offered with 1 flower, she would have 1 flower remaining with her. So, seems like the number of flowers brought and offered can’t be same. On further delving, there would be a realization that flowers offered need to be more than flowers brought, for it to reduce on consecutive iterations. Moreover, the flowers offered need to be less than twice the flowers brought, for the same reason. Given this understanding, one may try with next set of possible numbers as 2 flowers brought and 3 flowers offered. Not working. Then, with 3 flowers brought, either 4 or 5 flowers could be offered. Interestingly, with 3 flowers brought, and 4 flowers offered, all flowers get over in the second temple itself. And with 1 flower brought, and 2 flowers offered, all flowers were getting over in the first temple itself. Wow! There seems to be some pattern.

Now, one can approach this way, and finally get a solution. But as this is a trial and error kind of approach, computers are better in solving this. And a programmatic flow can be evolved for the same. And in that case, why only for a square pond? Why not an n-sided polygon pond with n temples? Great idea. And here is how the logic for that could be laid out:

solved = false;
brought = 1;
while (!solved)
	for (offered = brought + 1; offered < 2 * brought; offered++)
		if (solved = solve(n, brought, offered))
			printf("Min Brought: %d. Offered: %d\n", brought, offered);

where the solve() function could be the puzzle iterator, as follows:

solve(n, brought, offered)
	rem = brought;
	for (i = 1; i <= n; i++)
		rem = 2 * rem - offered;
	return (rem == 0) ? true : false;

Why is the minimum number of flowers brought, is being discussed? This can be easily seen by replacing the while (!solved) by a while (1). And there would be a continuous listing of infinite solutions to this puzzle.

Furthermore, why does the magic pond only double? What if it makes it k-times? The above problem could be parameterized even for that to observe even more interesting patterns – left as an exercise for the reader.

Now, this was just one approach to solve the puzzle and without any hesitation could be called as the computer science approach.

What if one wants to do it without computer science fundae – computer science is only very recent, right? Yes, as mentioned earlier, there could be many more approaches to the problem. Computer Science is just an ease. Or, rather an approach of making ourselves easier by trying to offload our brain tasks to computers.

Just to demonstrate that there could be other approaches as well, one may take a mathematical approach using algebra to solve the same. Let ‘b’ be the (positive) number of flowers brought, and ‘o’ be the (positive) number of flowers offered. Then, using these two variables, one may form an equation as per the puzzle, and then solve it. It would turn out to be one linear equation in two variables, and hence offering infinite solutions, same as above.

Expecting an answer to the above puzzle. Just try it out and find out for yourself. And may be, using your own approach. And then don’t forget posting it below in the comment box.

Next Article >>

   Send article as PDF