Tag Archives: combinations

Poisoned Dish

3 Replies

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

4 Replies

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

Permutations of Selections

2 Replies

<< Previous Article

In the previous article on permutations, the special case of arrangements of all the “n” distinct items, was dealt with. Now, with that and the logic of combinations (different ways of selecting “k” items from “n” distinct items), we are all set for the general permutations of first selecting “k” items from “n” distinct items, and then arranging those “k” items (in different permutations or possible ways). In mathematical terms, it is denoted by nPk (read n P k), permutations of “k” items from “n” (distinct) items.

As mentioned in the previous article, the total number of such different permutations or arrangements possible can be readily computed using the following recursive relation and the terminating condition:
nPk = k * n-1Pk-1 + n-1Pk, n > k > 0 (recursive relation)
nPk = k * n-1Pk-1, n = k > 0 (recursive relation)
nPk = 1, for k = 0 (terminating condition)
Note that, the implicit condition on which nPk is defined is n >= k >= 0.

A straight away functional recursive implementation would look like this:

permutations(n, k)
{
	if (k == 0)
		return 1;
	else if (k == n)
		return k * permutations(n - 1, k - 1);
	else
		return k * permutations(n - 1, k - 1) + permutations(n - 1, k);
}

And now with the earlier two logics of printing (different possible selections of “k” items from “n” (distinct) items, and all different possible arrangements of “n” (distinct) items), it is just a matter of few tweaks to be able to invoke the above two logics to solve the general permutations printing logic.

Note that the general permutations is a two step process of first selecting “k” items from “n” distinct items, and then arranging those “k” items (in different permutations or possible ways). Hence, it can be implemented recursively, using a recursive logic similar to that of the selection logic, and then applying the arrangement logic, once selected.

Assuming the print_arrangements(n, basket[]) available from the previous article, and invoking & renaming the selections() logic from its previous article, we have the following:

selections_arrangements(n, k, basket[], plen, prefix[])
{
	if (k == 0)
	{
		print_arrangements(plen, prefix);
	}
	else if (k == n)
	{
		for (i = 1; i < k; i++)
		{
			prefix[plen + i] = basket[i];
		}
		print_arrangements(plen + k, prefix);
	}
	else
	{
		// Following two recursive calls of selections_arrangements
		// have been swapped, compared to the original recursive calls
		// of selections, to print them from left to right
		prefix[plen] = basket[0];
		selections_arrangements(n - 1, k - 1, basket + 1, plen+1, prefix);
		selections_arrangements(n - 1, k, basket + 1, plen, prefix);
	}
}

Note the change to the invocation of print_arrangements() logic, instead of just the print() logic, in the cases of k == 0 and k == n, where the selecting of “k” items from “n” distinct items is already complete and now their arrangements need to be printed.

Moreover, as the cases k == 0 and k == n, take similar action, they can be further merged as follows:

selections_arrangements(n, k, basket[], plen, prefix[])
{
	if ((k == 0) || (k == n))
	{
		for (i = 1; i < k; i++)
		{
			prefix[plen + i] = basket[i];
		}
		print_arrangements(plen + k, prefix);
	}
	else
	{
		prefix[plen] = basket[0];
		selections_arrangements(n - 1, k - 1, basket + 1, plen+1, prefix);
		selections_arrangements(n - 1, k, basket + 1, plen, prefix);
	}
}

And again, as in the previous articles, to make the toplevel call look beautiful, a wrapper print_selections_arrangements() can be provided as follows:

print_selections_arrangements(n, k, basket[])
{
	plen = 0;
	prefix[] = {}; // prefix being capable of supporting max "k" items

	selections_arrangements(n, k, basket, plen, prefix);
}

Next Article >>

   Send article as PDF