Three needles are fixed on a flat plate. On one of these needles are placed sixty-four discs, the largest disc resting on the plate and the others getting smaller and smaller up to the top one. The objective is to move all the discs from one needle to another subject to the following rules. You must only move one disk at a time, and there must never be a smaller disc below a larger one during the transfer. What is the minimum number of moves required to complete the transfer of all the sixty-four discs? (Hint: Start with two discs and then three and so on. Do you see a pattern?)
This puzzle is popularly known as the Tower of Brahma (Tower of Hanoi). Instead of providing a solution, it is interesting to look at another related puzzle which has a lot of similar elements. In fact, it is not much of a puzzle as it is a hint to the previous question.
There was a king who was so pleased with his minister for teaching him the game of chess that he offered him a reward of his choice. The minister asked the king to give him one grain of wheat to put on the first square of the chessboard, two on the second square, four on the third square and so on doubling the number of grains for each square all the way up to the 64th square. The king agreed to his request while silently enjoying the thought that his minister has turned down a golden opportunity to ask for a part of his kingdom or treasury. But he soon realized his folly and had to behead the minister to avoid the shame of being indebted to him.
Well, it turns out that the number of grains of wheat the king had to give the minister equals the number of moves required to transfer the discs from one needle to another and it is such an astronomically huge number1 that the king was left with no other choice. It is said that Lord Brahma placed sixty-four golden discs on diamond needles in a temple in Benares at the moment of Creation. And when all the discs are transferred to another needle, the world along with all his creations will come to an end.
While these two puzzles are relatively simpler, there is another problem which a shopkeeper near my house once asked me. Though I figured out the solution after much effort, I still don’t have any kind of a proof which would take me to the answer. Any help in this regard would be much appreciated. Here’s the question:
He had a weight of mass 40kg which fell down one day and split neatly into four pieces2. On later inspection he realized that he could now weigh any mass from one through forty using these four new pieces. How much do each of the new pieces weigh3?
1. 264 – 1
2. Of course it didn’t happen to him. That’s the way he told me the puzzle.
3. 1kg, 3kg, 9kg and 27kg.
Nair's Tea Stall 
Why powers of 3? What's up with that?
It somehow works. You can keep going up in geometric progression and the question still remains valid. Given that we need w1=1kg we can get the other weights. The second weight should be such that w2-1=2, giving w2=3. We have 1+3=4, hence the third weight w3 should be such that w3-4=5 (we can't weigh 5 using 1 and 3) which gives w3=9. Now we can weigh till 13. Hence, the next weight w4 should be given by w4-13=14 which gives w4=27 and so on. But this is hand-waving. The weights accidentally sum to 40. What if we had a weight of 50kg?
How is that possible? How eg do you weigh a 5 kg mass using that?
Put 9kg on one arm and 4kg(=3+1) on the other. Anyway, I guess the geometric progression in 3 represents the most economic split of weights.
(0/1/-1)w1+(0/1/-1)w2+… +(0/1/-1)wn = k must have a solution for any k smaller than a number. Starting off from n=1 and following the heuristic above as yours, proceeding for n=2,3… we get the solution. Just like any natural number, x, can be represented as x = (0/1/../9)*10^0 + (0/1/../9)*10^1 + … (decimal notation), the sum above can give all possible combinations for weights equal to powers of 3. (For a clearer analogy add 1*w1+1*w2+.. to equation above and not that negative numbers are duplicated in the sum above)PS: Phew! Nice problem. I had to delete two previous comments to come up with this.
Proof that any no. below 40 can be summed up using the weights 3^0, 3^1, 3^2, 3^3.Express the number in base 3 format( eg. 5 becomes 12. 17 becomes 122 and so on.)Express the number as sum / difference of powers of 3. (eg 111 = 1*3^2 + 1*3^1 + 1*3^0.12 = 1*3^1 + (3-1)*3^0 = 3^1 + 3^1 – 3^0 = 3^2 – 3^1 – 3^0. ) Such a conversion is possible for every number <= 1111(BASE 3) = 40.As an extension, the same problem would exist if a 7 kg block breaks into 3 pieces or a 341 kg block breaks into 5 pieces and so on.
@Anant >>>the sum above can give all possible combinations for weights equal to powers of 3<<<Yes. Nice observation. But that still demands an explanation as to why we must choose powers of 3 for weights.@BinuWonderful way of extension into ternary arithmetic. But I don't see how it would apply to base4 (341kg; eg, how do you measure 2 kg with 1, 4, 16 etc.) It seems Base3 is the most economical way. Base2 overcompensates (you can measure 3kg in two ways, 1+2, 4-1) whereas Base4 fails to meet the necessary condition (you can't measure many weights in between).So though the necessary condition (that given weights in powers of 3 or below you can measure any weights till the total sum) can be proved by any of the above methods proposed above, sufficiency (that given the range you need weights of powers 3 or below, with 3 being the most economical choice in terms of range of weights measured) condition seems to just jump out.
Good observation that the problem cant be extended to base 4. Three looks like the optimum solution because of the nature of the problem. Every block has 3 options: not to be included in the sum at all (implying a 0) or put it on the left arm (implying a -1) or put it on the right arm ( implying a +1). Hence any number which has a 2 in its base4 equivalent cannot be represented.So if it were to break into 5 parts, the maximum sum that can be achieved would be 121 (1+3+9+27+81).
The heuristic method given above is basically (3^n-1)/2 {sum of the geometric series} + ((3^n-1)/2 + 1) {the first weight which can't be expressed} = 3^n. For some weight in between say 50 we can choose {1, 3, 9, 27, 10} and so on.
@ Nair, 3 because three possible 'coefficients' (0/1/-1) just like decimal has 10 possible 'coefficients'
For base 4, try with 4 symbols(keeping the physical interpretation aside). For eg. {-1, 0, 1, 2}. This way you can use, say 1, 4, 4^2 to represent all numbers from 1 to 37. I think similarly for base 5 you could use {-2,-1,0,1,2}. Do you think that would work?
Hi. For coefficients in powers of 2 all the weight measurements can de done in a single arm of the balance (0,1) (the pay off being lesser range of weights measured). But for powers of 3 you need to use both arms of the balance (-1,0,1). When we get to powers of 4 and 5, we can as you said start measuring weights with extra scalings of 2, -2 etc. but this would mean tampering with the balance; i.e., adjusting the arm length. But the idea is nice!