Gold Bar Division Problem

The regular readers of this blog have by now figured out, and most correctly so, that this is going to be yet another post on Puzzle. I got this one from a friend of mine in IIT Bombay who shares my passion for brainteasers. This one appeared in one of the interview question dumps that gets circulated.

Problem Statement

So here goes the statement of the puzzle:

Amongst Bengalis Durga Puja is the biggest festival of the year and usually takes place in the month of October. Rajiv is a Bengali man, who needs money for buying gifts for his family during Durga Pujas. He plans to use his inherited 31cm gold bar as a security against taking the money. October has 31 days, Rajiv plans to give 1 cm of gold each day to the money lender and get some money from him.

However, Rajiv wants to make as few gold pieces as possible. So the obvious solution of making 31 x 1cm bars is out of question. He can rely on a scheme like giving 2 x 1cm bar on days one and two, then giving 3cm bar on day three and taking back the previous bars.

Find out the minimum number of gold bars, their individual sizes and how does Rajiv manage to use them.

Solution

The solution is rather simple. Rajiv needs to divide the gold bars into sizes 1, 2, 4, 8, 16, which adds up to 31. The scheme is very simple and best explained by a diagram of how each number from 1 to 31 will be made.

16	8	4	2	1	Value
0	0	0	0	1	1
0	0	0	1	0	2
0	0	0	1	1	3
0	0	1	0	0	4
0	0	1	0	1	5
0	0	1	1	0	6
0	0	1	1	1	7

 

Along similar lines the table will be extended till 31. The point to note here is that the numbers have a binary representation. So in problems of this nature (i.e. divide in minimum parts) where the weights of each part are non negative, the trick is to use the binary notation. The division have to be done using the binary positional numbers whose general representation is of the form 2^n for n = ( 0, 1, 2, … }.

Generally when the individual parts have two states we can safely assume binary representation. In this case the two states are: “with Rajiv”, “with money-lender”. Similarly for three states we will have to use ternary representation. I have an excellent example of usage of ternary number system, which I will be posting soon, so check back this space soon.