Divide $2005 into a number of boxes so you can give any TWO AMOUNTS $X and $Y with X+Y <2005, when asked. The amount of Dollars is written on each box so you do not have to open them. What is the minimum number of boxes required? Prove it and extend this result to N.Added: you should be able to give amount $X to person A, and then give amount $Y to person B without rebalance your box. You give out $X+$Y amount in total.

Last edited by jiantao on January 4th, 2005, 11:00 pm, edited 1 time in total.

- alexandreC
**Posts:**678**Joined:**

Last edited by alexandreC on January 4th, 2005, 11:00 pm, edited 1 time in total.

- alexandreC
**Posts:**678**Joined:**

by any chance, is it(with some modifications in case the result is a non integer)(but am so tired at this time, so this might be nonsense.)

Last edited by alexandreC on January 4th, 2005, 11:00 pm, edited 1 time in total.

QuoteOriginally posted by: alexandreCby any chance, is it(with some modifications in case the result is a non integer)(but am so tired at this time, so this might be nonsense.)I am afraid that this is not a right answer!It is specified that: " give any TWO AMOUNTS $X and $Y". This means that you should be able to give amount $X to person A, and then give amount $Y to person B without rebalance your box. You give out $X+$Y amount in total.

QuoteOriginally posted by: alexandreCby any chance, is it(with some modifications in case the result is a non integer)(but am so tired at this time, so this might be nonsense.)That's what I thought too, at first glance.Jiantao's brainteasers are too hard for me. sigh..

16 boxes would do it. This generalizes to 2*ceiling[log_3[N]+1]. [Update: You can safely ignore this -- I made some bad assumptions]

Last edited by rblaser on January 4th, 2005, 11:00 pm, edited 1 time in total.

QuoteOriginally posted by: rblaser16 boxes would do it. This generalizes to 2*ceiling[log_3[N]+1].I am afraid that 16 is not enough. If you post the box assignment, I can check it for you.

- alexandreC
**Posts:**678**Joined:**

well, with a number of boxes given by mine and Hongyi's formula,we can distribute the money such that the problem is solved. So we should be waiting for someone who trades at a lower price than ours...

Last edited by alexandreC on January 6th, 2005, 11:00 pm, edited 1 time in total.

Hint: The assigments in the box should be the sequence1, 1, 2, 3, 4, 6, 9, 14,...

curious. this is the same as integer part of the average of Fibonacci series with delayed start1 1 2 3 5 8 13 21...1 1 4/3 7/4 12/5 20/6 33/7 54/8...1 1 1 1 2 3 4 6...Integer sequence A078620

19?One full set of the powers of 2 for $x (10 for $2005)Then only a set for y<2005/2 because of x+y<2005 so thats 9i dont know nuthin about no integer parts of the average of delayed starting fibb.

Last edited by avartan on January 7th, 2005, 11:00 pm, edited 1 time in total.

- bluehonour
**Posts:**44**Joined:**

This problem is very interesting. Does anyone know the solution to it? I could solve it for the case where we need to come up with any ONE amount X<2005, which is easy. But I could not solve the original problem.

- Traden4Alpha
**Posts:**23951**Joined:**

One answer is C_1 = 1, C_n = FLOOR[SUM[C_i,i = 1 to n-1]/2]+1. This recursively defined series yields:1, 1, 2, 3, 4, 6, 9, 14, 21, 31, 47, 70, 105, 158, 237, 355, 533, 408 -- NOTE: the last number in the sequence should be 799, but is clipped so that the series sums to 2005.Which is 18 boxes. The key is that one needs to construct the series progressively to handle the worst case in which the the two people both ask for N dollars each.

Last edited by Traden4Alpha on October 2nd, 2006, 10:00 pm, edited 1 time in total.

Deleted

Last edited by whtieoaks on October 2nd, 2006, 10:00 pm, edited 1 time in total.

In general, the amount of dollars on the kth box satisfya(k) = floor( sum_1_to_k-1( a(i) ) / 2 ) + 1This gives the sequence 1,1,2,3,4,6,9,14... Suppose m box can give out any two amounts summing to at most f(m), then we havef(m) = f(m-1) + floor( f(m-1)/2 ) + 1and f(2)=2, f(3)=4, f(4)=7, f(5)=11, f(6)=17, f(7)=26, f(8)=40,...A good estimate for f(m) would be f(m) ~= 1.5^(m+1), and 1.5^(m+1)=2005 gives us m=17.75. So we'd expect to use something like 18 boxes.

Last edited by cuinuc on December 4th, 2006, 11:00 pm, edited 1 time in total.