## Friday, February 25, 2011

### BBoxes & N Dollers

“You have b boxes and n dollars. If I want any amount of money from 0 to n dollars, you must be able to hand me 0 to b boxes so that I get exactly what I request.” The two questions were “What are the restrictions on b and n, and how is money distributed among the boxes?”

The trick is of Binary Numbers
2^0=1
2^1=2
2^2=4
2^3=8
2^4=16
….

2^7=128

..

The formula is [log n to base 2] + 1 = b e.g b=logn+1 with base 2
where [] denote integral part of the log base 2 of n

Example
So if we want 0 to 15 dollars
[log of 15 to base 2] + 1 = [3.90] + 1 = 3 + 1 = 4 boxes
we need to have 4 boxes each having 1,2,4,8, dollars respectively.Now we know from binary numbers that any amount from 0 to 15 can be formed with this boxes.

For 0 to 6 dollars
[log of 7 to base 2] + 1 = [2.58] + 1 = 2 + 1 = 3 boxes
we need to have 3 boxes each having 1,2,4, dollars respectively

For 0 to 100 dollars
[log of 100 to base 2] + 1 = [6.64] + 1 = 6 + 1 = 7 boxes
we need to have 7 boxes each having 1,2,4,8,16,32,64 dollars respectively

Correct me if Anything wrong