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.