Tag Archives: computer science approach

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);
			break;
		}
	}
	brought++;
}

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