Author |
Topic: Expected number of days a box of tomatoes lasts (Read 2128 times) |
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
 |
Expected number of days a box of tomatoes lasts
« on: Apr 14th, 2010, 5:24pm » |
 Quote  Modify
|
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 Limn->oo k/n <= 1-1/e.
|
| « Last Edit: Apr 14th, 2010, 8:48pm by Aryabhatta » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Expected number of days a box of tomatoes last
« Reply #1 on: Apr 15th, 2010, 5:51am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Expected number of days a box of tomatoes last
« Reply #2 on: Apr 15th, 2010, 8:01am » |
Quote Modify
|
k(n) can also be written as
k(n) = 2 k(n-1) - k(n-2) - (-1)n/n!
k(n) =  k=0..n (-1)k (n-k)/(k+1)!
k(n) = k=0..n (-1)k (n+1)/(k+1)! - k=0..n (-1)k (k+1)/(k+1)!
k(n) = (n+1) * k=0..n (-1)k/(k+1)! - k=0..n (-1)k/k!
k(n) = (n+1) * k=0..n - (-1)k+1/(k+1)! - k=0..n (-1)k/k!
k(n) = (n+1) * k=1..n+1 - (-1)k/k! - k=0..n (-1)k/k!
k(n) = (n+1) * [1 - k=0..n+1 (-1)k/k!] - k=0..n (-1)k/k!
k(n) = n+1 - (n+1)*k=0..n+1 (-1)k/k! - k=0..n (-1)k/k!
k(n) = n+1 - (n+2)*k=0..n+1 (-1)k/k! + (-1)n+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.
|
| « Last Edit: Apr 15th, 2010, 8:09am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Expected number of days a box of tomatoes last
« Reply #3 on: Apr 15th, 2010, 9:11am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Expected number of days a box of tomatoes last
« Reply #4 on: Apr 15th, 2010, 10:02am » |
Quote Modify
|
I'm not sure I understand correctly.
We have
k = i=1..n e_i
e_i = j=1..i p_j
p_j <= 1/(n-j+1)
If we use the latter to determine the upper bound, I get
k <= i=1..n j=1..i 1/(n-j+1) = n
|
| « Last Edit: Apr 15th, 2010, 10:02am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Expected number of days a box of tomatoes last
« Reply #5 on: Apr 15th, 2010, 10:06am » |
Quote Modify
|
on Apr 15th, 2010, 10:02am, towr wrote:I'm not sure I understand correctly.
We have
k = i=1..n e_i
e_i = j=1..i p_j
p_j <= 1/(n-j+1)
If we use the latter to determine the upper bound, I get
k <= i=1..n j=1..i 1/(n-j+1) = n |
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Expected number of days a box of tomatoes last
« Reply #6 on: Apr 15th, 2010, 10:14am » |
Quote Modify
|
Ah, of course.  That explains things. The e_i obviously can't be more than 1, and those ones would.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print