How long do you have to wash grapes for?

The other day I was washing grapes (a bowl full of them), and when I wash any sort of fruit inside a bowl, I try to rub each of them at least once so I can get rid of whatever is on the surface. But since I don’t actually count each one and identify them, I’m never sure if I’ve touched all of them — and so I resort to just picking up a few, rinsing them off, replacing them and repeating for 30 seconds ish under running water.

So as I washed that day, I wondered about this problem: what is the optimal duration to wash grapes for to maximize my chances of washing each grape while minimizing the amount of water spent (because we need to be green, people)?

This seemed like an interesting problem, so I naturally sat down, watched an episode of Start Up while eating the grapes, and then began to think about it.

Let’s state the problem more formally: I have n grapes. Every second, I pick up one grape, wash it, and replace it. How many times do I have to do this before I expect to have washed every grape?

If $n=1$ , this is easy: the first grape I pick is the only grape present, and after one second, every grape is washed. So if I’m eating one grape, I’ll wash for one second.

Here, I’ll introduce some vocabulary: a grape is dirty if I haven’t washed it yet. If I have washed it, I’ll call it clean.

If $n=2$ , the first grape I pick will be dirty (and after one second, it will be clean). The second time around, I have a 50% chance of washing the dirty one, and a 50% of re-washing the clean one. Let’s make this a little clearer: at the beginning, I have two grapes; let’s call them $g_1$ and $g_2$ . Now let’s define two random variables, $x_i$ , which denotes the expected number of seconds (or tries) it takes to select $g_i$ , and $p_i$ , which denotes the probability that I select $g_i$ in the next second. So what I want to calculate is $\mathbb{E} (x_1 + x_2)$ , or the expected number of seconds to select both $g_1$ and $g_2$ .

By linearity of expectation, $\mathbb{E} (x_1 + x_2) = \mathbb{E}x_1 + \mathbb{E}x_2$ . We know that $p_1 = 1$ because both grapes are dirty (either one can be $p_1$ ). We also know that $p_2 = \frac{1}{2}$ , because after the first second, there are guaranteed to be one clean and one dirty grape, which means that the probability of choosing the dirty grape, or $g_2$ , is $\frac{1}{2}$ .

More generally, $p_i = \frac{n-i+1}{n}$ . The probability of selecting the $i$ th dirty grape is the number of dirty grapes over the total number of grapes. The number of dirty grapes is $n - (i-1) = n - i + 1$ . Alright. That means the expected number of seconds to clean that $i$ th dirty grape is $\frac{1}{p_i} = \frac{n}{n-i+1}$ .

So let’s put this all together…

$\sum_{i=1}^{n} \mathbb{E} x_i = \frac{1}{p_1} + \ldots + \frac{1}{p_n} = 1 + \frac{n}{n-1} + \cdots + \frac{n}{1}$

Rewriting it, we see…

$\sum_{i=1}^{n} \mathbb{E} x_i = n (\frac{1}{n} + \frac{1}{n-1} + \cdots + 1)$

The part in the parentheses is known as the $n$ th harmonic number, known as $H_n$ (see https://en.wikipedia.org/wiki/Harmonic_number), so if you want a formula, check that out.

Anyway, back to the original problem: so how long should I wash my bowl of grapes for?? If I have $n$ grapes, then I should wash it for $n * H_n$ seconds (if I wash a grape every second). After this amount of time, I expect to have washed every single grape. The probability of this actually happening is still low, of course, but it’s the average. If you think about it, technically you could get lucky and wash it for $n$ seconds, picking up a dirty grape every second. Or you could go for a whole year if you get unlucky and pick the same grape every single time. But this is a good middle ground 🙂