Serving the Quantitative Finance Community

• 1
• 2

jiantao
Topic Author
Posts: 26
Joined: November 23rd, 2004, 10:11 pm

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: June 9th, 2004, 11:35 pm Another Box problem Last edited by alexandreC on January 4th, 2005, 11:00 pm, edited 1 time in total. alexandreC Posts: 678 Joined: June 9th, 2004, 11:35 pm Another Box problem 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. jiantao Topic Author Posts: 26 Joined: November 23rd, 2004, 10:11 pm Another Box problem 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. bertstein Posts: 116 Joined: December 22nd, 2003, 4:54 pm Another Box problem 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.. rblaser Posts: 61 Joined: July 14th, 2002, 3:00 am Another Box problem 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. jiantao Topic Author Posts: 26 Joined: November 23rd, 2004, 10:11 pm Another Box problem 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: June 9th, 2004, 11:35 pm Another Box problem 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. jiantao Topic Author Posts: 26 Joined: November 23rd, 2004, 10:11 pm Another Box problem Hint: The assigments in the box should be the sequence1, 1, 2, 3, 4, 6, 9, 14,... karakfa Posts: 139 Joined: May 25th, 2002, 5:05 pm Another Box problem 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 avartan Posts: 12 Joined: January 15th, 2003, 12:51 am Another Box problem 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: April 8th, 2006, 8:26 pm

Another Box problem

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.

Posts: 23951
Joined: September 20th, 2002, 8:30 pm

Another Box problem

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.

whtieoaks
Posts: 2
Joined: August 30th, 2006, 11:43 pm

Another Box problem

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

cuinuc
Posts: 1
Joined: November 30th, 2006, 5:15 am

Another Box problem

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.