1
$\begingroup$

A question posed on John D. Cook's blog asks:

Suppose you have a large number of buckets and an equal number of balls. You randomly pick a bucket to put each ball in one at a time. When you’re done, about what proportion of buckets will be empty?

Can you explain the answer to this question in a way understandable to high school students? How about to ten year olds?

  • 1
    The usual "mean" argument is explainable in terms of gambling: the $i$-th gambler hoping for no hit in her bin. The behaviour of $\left(\frac{n-1}{n}\right)^n$ can be made plausible by a dozen calculator computations.2012-10-12

1 Answers 1

3

Let $F_n$ be the set of functions from $[1,\ldots,n]$ to $[1,\ldots,n]$. We want to approximate:

$ \sum_{f\in F_n}|\operatorname{Im} f|, $

so we set a "double counting" approach.

$ \sum_{f\in F_n}|\operatorname{Im} f| = \sum_{i\in[1,\ldots,n]}\left|\left\{ f\in F_n:i\in\operatorname{Im} f\right\}\right| = \sum_{i\in[1,\ldots,n]}\left(n^n-\left|\left\{ f\in F_n:i\not\in\operatorname{Im} f\right\}\right|\right),$

so:

$ \sum_{f\in F_n}|\operatorname{Im} f| = n(n^n-(n-1)^n)$

and the average cardinality of $|\operatorname{Im}f|$ turns out to be:

$ n\left(1-\left(1-\frac{1}{n}\right)^n\right), $

so, for a large number of buckets, $\frac{n}{e}$ of them will be empty, in the average case.

  • 0
    I think that any explanation of this solution should come after some deep insight about "double counting" and other combinatorial techniques, much more useful with respect to the problem in itself.2012-10-12