Sam has 143 diamonds. They are to be arranged into different boxes such that if Adi asks for any number of diamonds from 1 to 143, then Sam must be able to give them without opening any box (directly giving specific boxes). What is the minimum number of boxes Sam will need so that any number of diamonds can be given?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
By simple logic we can say that the first box must have 1 diamond and the second should have 2. now in such a way Aditya can give 1 or 2 or 3 diamonds to Sam.therefore the third box should have 4 diamonds.the fourth box should have 8 diamonds and so on.. The total number of boxes required is 8. So the number of diamonds in the boxes will be 1 , 2 , 4 , 8 , 1 6 , 3 2 , 6 4 , 1 6 ... note that 128 won't be there because then the sum of numbers exceeds 143.
Thus , the answer is number of boxes and it is 8 .
How can you represent 140?
Log in to reply
Hello @Nanayaranaraknas Vahdam , note that because 1 4 0 > 1 2 7 , you have to use the last box which has 16 diamonds. So use it first, so your problem reduces to representing 124, and that is possible by 6 4 , 3 2 , 1 6 , 8 , 4 Thus you use all boxes e x c e p t the 1st and 2nd for representing 140. That's how the method works, a better explanation is given in my solution that will use Binary representation.
The general solution for N number of diamonds is
x such that 2 x -1 >=N
Explanation pls
Log in to reply
@Udit Murthy , see my solution up there for the explanation, it is explaining the concept...
Problem Loading...
Note Loading...
Set Loading...
We know that every number has a specific representation in Binary form.
For example, 1 4 in base 10 is 1 1 1 0 in base 2.
Thus we can write 1 4 as 2 3 + 2 2 + 2 1 . Like this , because each number has it's S p e c i f i c R e p r e s e n t a t i o n and thus each number can be written as sum of powers of two.
Thus if you want all the numbers till 1 4 3 to be written as sum of boxes' numbers, then you must get the boxes as 2 0 , 2 1 , 2 3 , 2 4 , . . . until the sum doesn't exceed 143, i.e. you will have to take the powers of 2 till 2 6 = 6 4 .
Here we use the result k = 0 ∑ n = 2 n + 1 − 1
Thus the sum of diamonds in the boxes till 64 is 1 2 7 .
Hence there are 1 4 3 − 1 2 7 = 1 6
Thus the boxes will have 1 , 2 , 4 , 8 , 1 6 , 3 2 , 6 4 and 1 6 diamonds hence there will be 8 boxes needed if you are to minimize the number of boxes.