Nine Bottles

There are nine bottles, each containing a different type of liquid, but the labels have all fallen off. Knowing nothing about the contents, a passerby reapplies the labels at random. What is the expected number of correctly labeled bottles? (That is, if the labels are randomly assigned many times, what is the average number of correct labels?)

It might be easier to try the problem for smaller numbers of bottles first.

Source: Internet newsgroup rec.puzzles, Used as Ken's POTD 5/16/94.

Solutions were received from several people. All pointed out that the expected number of correctly labelled botted is 1. Here is a summary of the solutions:

Consider the bottle #1 . Over all possible permutations (N=9!), there is a one-in-nine chance that this bottle gets its correct label. Same result concerning each of the eight bottles #2, 3, 4,...9. In total, there are 9 * N/9 = N bottles correctly labeled, that means (N-correctly-labeled-bottles/(N-possible-configurations) = 1 bottle is labelled correctly on average.

The correct labelings can be viewed separately, since we are considering the total number correct labels over all possible permutations.

Mail to Ken