Two Plus Two Poker Forums Math puzzle: Breaking the camel's back.
 Register FAQ Search Today's Posts Mark Forums Read Video Directory TwoPlusTwo.com

 Notices

 Science, Math, and Philosophy Discussions regarding science, math, and/or philosophy.

 11-19-2007, 09:29 PM #1 Pooh-Bah   Join Date: Mar 2004 Posts: 5,363 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.
 11-19-2007, 09:41 PM #2 old hand   Join Date: Feb 2007 Posts: 1,660 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 2x+2/3+o(1)? if so i used laplace transforms.
 11-20-2007, 11:33 AM #3 Pooh-Bah   Join Date: Mar 2004 Posts: 5,363 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.
 11-20-2007, 06:25 PM #4 Pooh-Bah   Join Date: Sep 2006 Posts: 3,655 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! +....
 11-20-2007, 07:13 PM #5 old hand   Join Date: Feb 2007 Posts: 1,660 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
11-20-2007, 07:37 PM   #6
Carpal \'Tunnel

Join Date: Mar 2005
Posts: 6,362
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 . Solution : Re-formulate the problem and select random numbers from the interval [0,1] .
The Font color is on the bottom right. Just click
the color you want.

11-20-2007, 08:50 PM   #7
Pooh-Bah

Join Date: Sep 2006
Posts: 3,655
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 .
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 .

 11-21-2007, 09:58 AM #8 veteran     Join Date: Sep 2003 Location: Hong Kong Posts: 3,208 Re: Math puzzle: Breaking the camel\'s back. Was this how you started? 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}
11-21-2007, 03:00 PM   #9
Carpal \'Tunnel

Join Date: Sep 2004
Location: farther back
Posts: 6,631
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 .
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 .
I still don't really understand this reasoning.

Can someone explain it further, as if to a mildly retarded twelve-year-old?

11-21-2007, 07:38 PM   #10
Pooh-Bah

Join Date: Mar 2004
Posts: 5,363
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?
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.

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.

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.

11-21-2007, 11:55 PM   #11
Carpal \'Tunnel

Join Date: Sep 2002
Location: SW US
Posts: 7,975
Re: Math puzzle: Breaking the camel\'s back.

Quote:
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?
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.

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.

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.
Was your uncle the anomaly, or is your entire family filled with mathematicians?

11-22-2007, 12:29 AM   #12
banned

Join Date: Nov 2005
Location: WOW IM SMART
Posts: 3,678
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 .
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 .
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 &gt;1?

 11-22-2007, 09:20 AM #13 Pooh-Bah   Join Date: Sep 2006 Posts: 3,655 Re: Math puzzle: Breaking the camel\'s back. x2 is either less than x1 or is in between x1 and 1 (note I have x2 above which is a typo) . The probability it is less than x1 is 1/2 . If it is less than x1 with probability 1/2 , then it must belong to the interval [1,1+x1] with the same probability 1/2 . Since adding 1 to x2 has the same distribution as x1 .
11-23-2007, 08:17 PM   #14
Pooh-Bah

Join Date: Mar 2004
Posts: 5,363
Re: Math puzzle: Breaking the camel\'s back.

Quote:
 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.
Solution to Part 2 in white:

As blah_blah pointed out, f(x) satisfies an integeral equation, although I think it is better to write it differently: f(x) = 1 + Integral from x-1 to x of f(t) dt, with initial condition that f(x) = 0 on [-1,0]. This is even simpler if you consider g(x) = f(x)-2x, which satisfies

(1) g(x) = Integral from x-1 to x of g(t) dt,

with initial condition g(x) = -2x on [-1,0].

The integral equation satisfied by g looks like it smooths g out, and damps down the oscillations of g. Since g(x) is an average of values of g on the interval [x-1,x], g is bounded by the values on [-1,0], and then by the values on [0,1], etc. This can be used to show that g is asymptotic to a constant, although I won't give the details here.

The idea I had was to find a conserved quantity, some function h defined on [0,1], so that the integral from t=0 to t=1 of g(x+t) h(t) dt does not depend on x. Let's see what properties h might have to force

H(x) = integral from 0 to 1 of h(t) g(x+t) dt

to be constant. By Leibniz's rule (link),

H'(x) = integral from 0 to 1 of g'(x+t) h(t) dt

Integrating by parts,

H'(x) = g(x+1)h(1) - g(x)h(0) - integral from 0 to 1 of g(x+t) h'(t) dt.

We'd like to choose h to force this to be 0, using what we know about g, equation (1). To get the RHS to involve the integral of g(t) on an interval of length 1, we can set h'=1. Setting h(0)=0 forces a term to drop out, so let h(t)=t.

H'(x) = g(x+1) - integral from t=0 to t=1 of g(x+t) dt
H'(x) = g(x+1)-g(x+1)
H'(x) = 0.

So, we have established that integral from t=0 to t=1 of t * g(x+t) dt is constant. If g is asymptotic to some constant c, then

Limit x-&gt;oo H(x)
= integral from 0 to 1 of t c dt
= c/2

H(-1)
= integral from 0 to 1 of t g(t-1) dt
= integral from 0 to 1 of t (-2 (t-1)) dt
= 1/3

Since H is constant, c=2/3.

So, f(x)=g(x)+2x is asymptotic to 2x+2/3. As a quick check, f(1)=e, which is not too much greater than 2 2/3 = 1/0! + 1/1! + 1/2! + 1/3!.

11-23-2007, 09:47 PM   #15
Pooh-Bah

Join Date: Mar 2004
Posts: 5,363
Re: Math puzzle: Breaking the camel\'s back.

Quote:
 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.
Solution to Part 3 in white:

The method I used for Part 2 generalizes well. Let a(x) be the probability density function for the weight of a summand. We don't require that the weights be bounded, but they have to be positive, so a(x)=0 for x&lt;0. We'll also use that the weight is continuous, although that isn't really required. Let f(x) for the expected index of the partial sum greater than x, and f(x) =0 for x&lt;0. As before, f satisfies an integral equation,

f(x)= 1 + Integral from t=0 to t=x of f(t) a(x-t) dt.
Equivalently, we can let the lower value be -oo, as f is 0 on (-oo,0).

As before, we'll get rid of that constant term by subtracting off a linear factor. To do this, we need the weight to have an expected value, w. We'll also want the variance to exist. Define g(x) = f(x) - x/w. Note that when x&lt;0, g(x) is not 0, but is -x/w instead. Then g satisfies an integral equation

g(x) = Integral from t=-oo to t=x g(t) a(x-t) dt.

We'd like to find a conserved quantity

H(x) = Integral t=-oo to t=x of g(t) h(x-t) dt.

We'll choose h so this is constant. Because of a different choice of variables, we didn't need the integration by parts (yet), but we get a more complicated application of Leibniz's rule since the upper limit of integration is not constant.

H'(x) = g(x)h(0) + Integral from t=-oo to t=x of g(t) h'(x-t)dt

Let h'(x) be c * a(x), so that this last integral resembles the integral equation for g(x).

H'(x) = g(x) h(0) + Integral from t=-oo to t=x of g(t) c a(x-t) dt
H'(x) = g(x) h(0) + g(x) c
H'(x) = g(x) (h(0) + c)

So, setting c=-h(0), H becomes constant.

We can scale h(0) arbitrarily, so let h(0)=1. Then
h(x) = 1 - Probability(weight &lt; x)
h(x) = Probabability (weight &gt; x)

Let the asymptotic value of g be v.

limit as x-&gt;oo H(x)
= limit as x-&gt;oo of Integral from t=-oo to t=x of g(x) h(x-t) dt
= limit as x-&gt;oo of Integral from t=-oo to t=x of v h(x-t)dt
= v * Integral from y=0 to y=oo of h(y) dy
= v * (-1) Integral from y=0 to y=oo of y h'(y) dy (by parts)
= v * Integral from y=0 to y=oo of y a(y) dy
= v * w

H(0)
= Integral from t=-oo to t=0 of g(t)h(-t)dt
= Integral from t=-oo to t=0 of -t/w h(-t) dt
= Integral from y=oo to y=0 of y/w h(y) (-1)dy
= Integral from y=0 to y=oo of y/w h(y) dy
= 1/w Integral from y=0 to y=oo of y h(y) dy
= 1/w (-1) Integral from y=0 to y=oo of y^2/2 h'(y) dy (by parts)
= 1/(2w) Integral from y=0 to y=oo of y^2 a(y) dy
= 1/(2w) * second moment of weight distribution

So, the asymptotic value v satisfies v * w = 2nd moment/(2w), or v= 2nd moment / (2 * 1st moment^2).

f(x) is asymptotic to x/(1st moment) + 2nd moment/(2 * 1st moment^2).

As a check, the nth moment for a random variable uniformly distributed on [0,1] is 1/n, so we get f(x) ~ x/(1/2) + 1/3 /(2 * 1/4) = 2x + 2/3.

How about an exponential distribution with mean 1? The 1st moment is 1, and the second moment is 2 (and variance is 2-1=1). f(x) ~ x + 2/2 = x+1. In fact, f(x) isn't just asymptotic to x+1, f(x)=x+1. The count of exponential distributions adding up to x is 1 more than a random variable with a Poisson distribution with mean x. So the expected value is x+1.

 Thread Tools Display Modes Linear Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are Off Pingbacks are Off Refbacks are Off Forum Rules

All times are GMT -4. The time now is 12:19 AM.

 Contact Us - Two Plus Two Publishing LLC - Privacy Statement - Top