Math puzzle: Breaking the camel's back.

[pzhon]

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.

[blah_blah]

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>.

[pzhon]

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.

[jay_shark]

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 &lt;x1 is 1/2 and so the probability 1&lt; x1+x2 &lt;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 &lt; x1+x2+x3 &lt;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! +....

[blah_blah]

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&lt;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

[jogsxyz]

[ 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.

[jay_shark]

[ QUOTE ]


With probability 1/2 , the camel's back will be broken first on the second straw . You may argue that the probability x2 &lt;x1 is 1/2 and so the probability 1&lt; x1+x2 &lt;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 .

[bigpooch]

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-&gt;infinity{integral_-r to r: [1/(2*pi*i)](1-exp(-izt)/[z(1-phi(z))] dz}
</font>

[Subfallen]

[ 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 &lt;x1 is 1/2 and so the probability 1&lt; x1+x2 &lt;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?

[pzhon]

[ 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&gt;=1)+P(X&gt;=2) + P(X&gt;=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&gt;=1)+
P(X&gt;=2)+
P(X&gt;=3)+...

Anyway, P(X&gt;=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.