Serving the Quantitative Finance Community

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

Another Box problem

January 4th, 2005, 10:30 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.
 
User avatar
alexandreC
Posts: 678
Joined: June 9th, 2004, 11:35 pm

Another Box problem

January 4th, 2005, 10:55 pm

Last edited by alexandreC on January 4th, 2005, 11:00 pm, edited 1 time in total.
 
User avatar
alexandreC
Posts: 678
Joined: June 9th, 2004, 11:35 pm

Another Box problem

January 4th, 2005, 11:37 pm

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.
 
User avatar
jiantao
Topic Author
Posts: 26
Joined: November 23rd, 2004, 10:11 pm

Another Box problem

January 5th, 2005, 12:07 am

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.
 
User avatar
bertstein
Posts: 116
Joined: December 22nd, 2003, 4:54 pm

Another Box problem

January 5th, 2005, 3:21 am

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..
 
User avatar
rblaser
Posts: 61
Joined: July 14th, 2002, 3:00 am

Another Box problem

January 5th, 2005, 5:37 am

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.
 
User avatar
jiantao
Topic Author
Posts: 26
Joined: November 23rd, 2004, 10:11 pm

Another Box problem

January 5th, 2005, 6:58 am

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.
 
User avatar
alexandreC
Posts: 678
Joined: June 9th, 2004, 11:35 pm

Another Box problem

January 5th, 2005, 8:03 pm

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.
 
User avatar
jiantao
Topic Author
Posts: 26
Joined: November 23rd, 2004, 10:11 pm

Another Box problem

January 6th, 2005, 8:55 pm

Hint: The assigments in the box should be the sequence1, 1, 2, 3, 4, 6, 9, 14,...
 
User avatar
karakfa
Posts: 139
Joined: May 25th, 2002, 5:05 pm

Another Box problem

January 7th, 2005, 10:22 pm

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
 
User avatar
avartan
Posts: 12
Joined: January 15th, 2003, 12:51 am

Another Box problem

January 8th, 2005, 9:43 pm

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.
 
User avatar
bluehonour
Posts: 44
Joined: April 8th, 2006, 8:26 pm

Another Box problem

October 2nd, 2006, 12:56 am

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.
 
User avatar
Traden4Alpha
Posts: 23951
Joined: September 20th, 2002, 8:30 pm

Another Box problem

October 2nd, 2006, 10:01 pm

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.
 
User avatar
whtieoaks
Posts: 2
Joined: August 30th, 2006, 11:43 pm

Another Box problem

October 2nd, 2006, 11:20 pm

Deleted
Last edited by whtieoaks on October 2nd, 2006, 10:00 pm, edited 1 time in total.
 
User avatar
cuinuc
Posts: 1
Joined: November 30th, 2006, 5:15 am

Another Box problem

December 5th, 2006, 8:55 am

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.