wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Expected number of days a box of tomatoes lasts
        
(Message started by: Aryabhatta on Apr 14^th, 2010, 5:24pm)

Title: Expected number of days a box of tomatoes lasts
Post by Aryabhatta on Apr 14^th, 2010, 5:24pm

I got this problem from a colleague at the company I work and this is what the email said:

Code:

I got this problem from my friend Olga Leontjeva quite some time ago, but was able to focus on it and crack it only recently (with some help from friends). Olga is known in Russia mostly as a prominent puzzle solver and inventor, but this particular problem looks more like an exercise in applied mathematics.

Intro: there is a story about a man who bought a box of fresh tomatoes. The next morning he decides to eat one of them for breakfast — and realizes that there is one tomato in the box that is not that fresh anymore. In fact, it shows signs of rotting. Being frugal, the man picks this tomato, removes bad parts and eats it. It is certainly not a delicious treat, but — well — the man “saved” his possession. The next morning the situation repeats — and the next — and the next... So the man ends up eating a whole box of half-rotten tomatoes, even though he has bought a box of fresh ones!

Olga’s problem changes the setup of this story in the following manner: the man got luckier this time and the tomatoes in his newly bought box of fresh tomatoes begin to rot in the evening, and not in the morning.

Otherwise, the situation is identical: each tomato in the box has its “bad day”: a number from 1 to n, where n is the number of tomatoes in the box; each number is assigned by the fate to a different tomato and, consequently, different tomatoes have different “bad day” numbers.

Each morning the man picks up a random tomato (fresh! It’s impossible to distinguish the tomato which will start to rot in the evening; all look the same in the morning, fresh and nice) — and eats it (yummy! No taste of rotting!). Each evening he checks the box for signs of rotting. It can happen that the tomato “scheduled” to start rotting on this evening was not eaten before — in this case this rotting tomato gets picked out of the box and thrown out. But if that tomato was taken for breakfast in one of preceding mornings, nothing happens in this evening. So the number of remaining tomatoes decreases any given day by 2 in the first case and by 1 in the second case.

For each given n one can come up with an exact value of k, the average number of days a box of tomatoes lasts. For example, when n equals 2, k equals 3/2. If he has the most luck, the man eats one fresh tomato on each of the n days (when his random choice coincides with “this day’s tomato” each day). If he has the least luck, the box empties twice as fast; so k/n is in between of 1/2 and 1.

Prove: Lim k/n = 1-1/e.
n->oo

Edit: Changed tt to code for better readability.

Also, I forgot to mention, I have only been able to show Lim_n->oo k/n <= 1-1/e.

Title: Re: Expected number of days a box of tomatoes last
Post by towr on Apr 15^th, 2010, 5:51am

It appears that k as function of n follows the recursion
k(n) = [(2*n-1)*k(n-1) - (n-2)*k(n-2) - k(n-3)]/n
(Which I got from simplifying:
g(0) = 1
g(n) = n*g(n-1) + (-1)^n = (n-1) (g(n-1) + g(n-2))
f(0) = 0
f(n) = (n+1)*f(n-1) + g(n-1)

where f(n) = n! k(n), which I've been examining based on the first dozen values. So I don't even have proof it actually, definitely, is the right formula.
g(n) is the number of derangements for n elements.)

k(n)/n does seem to go to 1-e^-1, approaching it from above, but even that I can't manage to prove. ::)
But perhaps that someone else can make something of it.

Title: Re: Expected number of days a box of tomatoes last
Post by towr on Apr 15^th, 2010, 8:01am

k(n) can also be written as
k(n) = 2 k(n-1) - k(n-2) - (-1)ⁿ/n!
k(n) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_k=0..n (-1)^k (n-k)/(k+1)!
k(n) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_k=0..n (-1)^k (n+1)/(k+1)! - http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_k=0..n (-1)^k (k+1)/(k+1)!
k(n) = (n+1) * http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_k=0..n (-1)^k/(k+1)! - http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_k=0..n (-1)^k/k!
k(n) = (n+1) * http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_k=0..n - (-1)^k+1/(k+1)! - http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_k=0..n (-1)^k/k!
k(n) = (n+1) * http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_k=1..n+1 - (-1)^k/k! - http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_k=0..n (-1)^k/k!
k(n) = (n+1) * [1 - http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_k=0..n+1 (-1)^k/k!] - http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_k=0..n (-1)^k/k!
k(n) = n+1 - (n+1)*http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_k=0..n+1 (-1)^k/k! - http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_k=0..n (-1)^k/k!
k(n) = n+1 - (n+2)*http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_k=0..n+1 (-1)^k/k! + (-1)ⁿ⁺¹/(n+1)!

So k(n) -> n+1 - (n+2)/e, and therefore k(n)/n -> 1 - 1/e

Well, that's something at least.

Title: Re: Expected number of days a box of tomatoes last
Post by Aryabhatta on Apr 15^th, 2010, 9:11am

Interesting, towr.

I was thinking along completely different lines!

Here is the proof I had for the <= part.

-------
Let the tomato which rots on day j be labeled j.

So the rotting order is 1,2,3,…n.

Now by symmetry, for n >= a >=j and n >= b >=j, probability that tomato a is eaten on day j = probability that tomato b is eaten on day j. Call this p_j. Let z_j be the probability that no tomato is eaten on day j. (z_j = 0 for j <= n/2)

Thus we have that

(n-j+1) * p_j + z_j = 1

This gives us the upper bound on p_j: p_j <= 1/(n-j+1)

If e_i is the probability that tomato i is eaten,

Then the expected number of days the basket lasts, k = e_1 + e_2 +… + e_n.

Now e_i = p_1 + p_2 + … + p_i

Thus e_i <= 1/n + 1/(n-1)+ … + 1/(n-i+1) = H_n – H_{n-i}

Where H_n is the nth harmonic number: 1 + 1/2 + … + 1/n

Choose r = integral part of n/e and break up e_1 + e_2 + .. + e_n

as

k = e_1 + e_2 + … + e_r + e_{r+1} + … + e_n <= e_1 + e_2 + … + e_r + 1 + 1 + … + 1

Using the fact that H_n – H_m = ln(n/m) + O(1/n^2) and Stirling’s approximation formula, ln(n!) = n*ln(n) – n + O(ln(n))

(ln(x) = natural logarithm of x)

and doing some computations gives us the upper bound of 1-1/e

Title: Re: Expected number of days a box of tomatoes last
Post by towr on Apr 15^th, 2010, 10:02am

I'm not sure I understand correctly.
We have
k = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_i=1..n e_i
e_i = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_j=1..i p_j
p_j <= 1/(n-j+1)
If we use the latter to determine the upper bound, I get
k <= http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_i=1..n http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_j=1..i 1/(n-j+1) = n

Title: Re: Expected number of days a box of tomatoes last
Post by Aryabhatta on Apr 15^th, 2010, 10:06am

on 04/15/10 at 10:02:09, towr wrote:

We do this:

k = e_1 + e_2 + … + e_r + e_{r+1} + … + e_n <= e_1 + e_2 + … + e_r + 1 + 1 + … + 1

Notice that we replaced e_{r+1} etc with 1, instead of Sum 1/(n+j-1) as those sums are more than 1.

Title: Re: Expected number of days a box of tomatoes last
Post by towr on Apr 15^th, 2010, 10:14am

Ah, of course. :-[ That explains things. The e_i obviously can't be more than 1, and those ones would.