|
#1
|
|||
|
|||
Math puzzle: Breaking the camel\'s back.
Here is a problem and two generalizations. Part 1 is a well-known problem which is nontrivial, but solvable by several techniques. I solved it over dinner as a kid. Part 2 is less well-known. The solution I've seen published is overly complicated, but a simple solution is possible, and generalizes to Part 3.
Part 1: Your camel's back can hold 1 unit. Straws have weights which are uniformly distributed from 0 to 1 unit, and independent of each other. You add one straw at a time. If the weights are 0.7, 0.1, 0.8..., then your camel's back breaks on the 3rd straw. On average, how many straws does it take to break your camel's back? Part 2: Let f(x) be the average number of straws it takes to break a camel's back if it can hold x units. Determine the asymptotics of f up to o(1), i.e., produce a simple function g so that the limit of f(x)-g(x) as x->infinity is 0. Part 3: Produce a method for determining the asymptotics for some more general continuous weight distributions, such as the square of a uniformly distributed random variable, or the sum of two. If you have a nice solution to only 1 part, it is worth posting it, but please put solutions in white. |
#2
|
|||
|
|||
Re: Math puzzle: Breaking the camel\'s back.
1) is pretty straightforward and it evaluates to a number that has been discussed a lot recently.
I think i might have an approach for 2. is the answer <font color="white">2x+2/3+o(1)</font>? if so i used <font color="white">laplace transforms</font>. |
#3
|
|||
|
|||
Re: Math puzzle: Breaking the camel\'s back.
I'd like to see your solutions. It sounds like your approach is good (and fast...), although it is at least superficially different from what I used.
|
#4
|
|||
|
|||
Re: Math puzzle: Breaking the camel\'s back.
I have a solution for problem 1 although I couldn't get the text in white .
Solution : Re-formulate the problem and select random numbers from the interval [0,1] . With probability 0 the camels back will be broken on the first straw . With probability 1/2 , the camels back will be broken first on the second straw . You may argue that the probability x2 <x1 is 1/2 and so the probability 1< x1+x2 <1+x1 is 1/2 . With probability 1/2*2/3 the camel's back will be broken first on the third straw . This is only possible if the camel's back is not broken by the first two straws(1/2) multiplied by the probability it is broken on the third straw . The probability the camel's back is broken on the third straw given that it's not broken by the first two straws is 2/3 since x3 is equally likely to be in the interval [0,x1] , [x1,x1+x2] or [x1+x2,1] . So x3 belongs in the interval [0,x1+x2] with probability 2/3 . Hence 1 < x1+x2+x3 <1+x1+x2 with probability 2/3 . The camel's back will be broken by the ith straw with probability 1/(i-1)!*(i-1)/i So if we compute the expectation , we should get 1*0 + 2*1/2 + 3*1/2*2/3 + 4*1/2*1/3*3/4 + 5*1/2*1/3*1/4*4/5 + .... + i*1/(i-1)!*(i-1)/i As i approaches infinity , the above expression is equivalent to: e= 1/0! +1/1! + 1/2! + 1/3! + 1/4! +.... |
#5
|
|||
|
|||
Re: Math puzzle: Breaking the camel\'s back.
the first problem is a fairly simple consequence of the fact that the simplex bounded by the coordinate planes x_0 = ... = x_n = 1 and x_1+...+x_n = 1 has n-dimensional measure equal to 1/n!, but imo a better solution technique is as follows. Let E(t) denote the expected number of turns to reach t starting at 0. We have, for 0<t\leq 1,
E(t) = (1-t) + \int^t_0 [E(x)+1]dx This is an integral equation with solution E(t) = a\exp(t). Note that as t decreases to 0, E(t) tends to 1. In particular we conclude that a=0 and E(t) = exp(t), so the desired answer is E(1) = \exp(1) = e |
#6
|
|||
|
|||
Re: Math puzzle: Breaking the camel\'s back.
[ QUOTE ]
I have a solution for problem 1 although I couldn't get the text in white . <font color="white">Solution : Re-formulate the problem and select random numbers from the interval [0,1] . </font> [/ QUOTE ] The Font color is on the bottom right. Just click the color you want. |
#7
|
|||
|
|||
Re: Math puzzle: Breaking the camel\'s back.
[ QUOTE ]
With probability 1/2 , the camel's back will be broken first on the second straw . You may argue that the probability x2 <x1 is 1/2 and so the probability 1< x1+x2 <1+x1 is 1/2 . [/ QUOTE ] Let me clarify this part . x2 may either belong to the interval [0,x1] or [x1,x2] and either choice is equally likely . The probability x2 belongs to [0,x1] is 1/2 , or equivalently , the probability x2 belongs to [1,1+x1] is 1/2 . |
#8
|
|||
|
|||
Re: Math puzzle: Breaking the camel\'s back.
[ QUOTE ]
[ QUOTE ] With probability 1/2 , the camel's back will be broken first on the second straw . You may argue that the probability x2 <x1 is 1/2 and so the probability 1< x1+x2 <1+x1 is 1/2 . [/ QUOTE ] Let me clarify this part . x2 may either belong to the interval [0,x1] or [x1,x2] and either choice is equally likely . The probability x2 belongs to [0,x1] is 1/2 , or equivalently , the probability x2 belongs to [1,1+x1] is 1/2 . [/ QUOTE ] I still don't really understand this reasoning. [img]/images/graemlins/frown.gif[/img] Can someone explain it further, as if to a mildly retarded twelve-year-old? |
#9
|
|||
|
|||
Re: Math puzzle: Breaking the camel\'s back.
[ QUOTE ]
[ QUOTE ] With probability 1/2 , the camel's back will be broken first on the second straw . You may argue that the probability x2 <x1 is 1/2 and so the probability 1< x1+x2 <1+x1 is 1/2 . [/ QUOTE ] Let me clarify this part . x2 may either belong to the interval [0,x1] or [x1,x2] and either choice is equally likely . The probability x2 belongs to [0,x1] is 1/2 , or equivalently , the probability x2 belongs to [1,1+x1] is 1/2 . [/ QUOTE ] is there something i dont get about the notation here? how can x2 belong to the group [1,1+x1] if x2 in itself cant be >1? |
#10
|
|||
|
|||
Re: Math puzzle: Breaking the camel\'s back.
Was this how you started?
<font color="white"> X[j] are positive continuous iiidrv with cdf F(.) and S[n] = X[1]+...+X[n] If T is the stopping time for capacity x, E[T(x)] = 1 + F(t) + F[2](t) + F[3](t) +... where F[n](t) is the cdf of S[n] Using characteristic functions, with phi(z) = E[e^(izX)] E[T(t)] = lim r->infinity{integral_-r to r: [1/(2*pi*i)](1-exp(-izt)/[z(1-phi(z))] dz} </font> |
|
|