#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.
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> |
#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 ] 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? |
#10
|
|||
|
|||
Re: Math puzzle: Breaking the camel\'s back.
[ QUOTE ]
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? [/ QUOTE ] There are many solutions. In white, I have written up the one I found without pencil or paper when I was 13 after an uncle posed the problem at a family Thanksgiving dinner, and at which blah_blah hinted. <font color="white"> The expected value of a random variable X taking positive integer values is the sum of the probabilities P(X>=1)+P(X>=2) + P(X>=3) + ... This useful trick is actually a change of the order of summation in something that looks like a single sum, but can be expanded: E(X) = P(X=1) + 2 P(X=2) + 3 P(X=3) + ... = P(X=1) + P(X=2) + P(X=3) + ... + _________P(X=2) + P(X=3) + ... + _______________ + P(X=3) + ... Summing rows, this is P(X>=1)+ P(X>=2)+ P(X>=3)+... Anyway, P(X>=n) = P(the first n-1 straws add up to less than 1, so with k=n-1 we want the sum of the probabilities that the first k straws add up to less than 1 for k=0,1,... The plane x1+...+xk =1 cuts off a simplex of volumn 1/k! from the unit cube, so the expected value is 1/0! + 1/1! + 1/2! + ... = e. </font> Also at that dinner, we discussed the geometric mean of the numbers in [0,1], which is again related to e. I'll post my solutions to Parts 2 and 3 later. I used a method which at least looks different from the suggestions of blah_black and bigpooch. However, I would not be surprised if they were all similar, from some perspective. |
|
|