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?

  • 0
    Do you mean that you randomly select a bucket, then put a ball in it, then randomly select the next bucket (which might again be the same bucket), and so on?2012-10-12
  • 0
    Yes, I believe that's what the question intends.2012-10-12
  • 0
    @Martin: Yes, that’s fairly clear if you read the discussion in the blog.2012-10-12
  • 0
    High school, no problem. Can one explain *anything* to a $10$ year-old?2012-10-12
  • 3
    @André: Depends on the individual in both cases. I don’t think that one could explain it to the majority of high school students, and there are a few $10$-year-olds to whom you could explain it reasonably well; I was one of them, once upon a time. I shouldn’t be surprised if Qiaochu was one, and quite possibly several others here.2012-10-12
  • 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

2

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.

  • 3
    This looks more like a solution of the problem than an attempt to give an explanation to high-school students (let alone ten-year olds).2012-10-12
  • 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