Math Help Forum - View Single Post

heathrowjohnny · #4 March 1st, 2008, 11:06 PM

2. There are $n!$ total permutations of the $n$ wallets. Now number the wallets from $1$ to $n$ . The first person has a $\frac{n-1}{n}$ probability of picking a wrong wallet. You would have to use a computer for this "brute force" approach.

Or let $P(n,k)$ be the probability that given $n$ people with $n$ wallets, $k$ of them choose the wrong wallet. Then we want $P(n,n)$ . This is our "black box" case.

We know that $P(n,0) = \frac{1}{n!}$ (i.e. probability all people get their wallets). Also by axiom 3 (commonly in textbooks) $\sum_{k=0}^{n} P(n,k) = 1$ . So $P(n,k)$ is the probability that there are $k$ incorrect wallets chosen and $n-k$ correct wallets chosen. These are independent events, so we can multiply probabilities. We get $P(n,k) = \frac{1}{(n-k)!}P(k,k)$ . But this doesn't really give us $P(n,n)$ . So $\sum_{k=0}^{n} \frac{P(k,k)}{(n-k)!} = 1$ . Plugging in values, we get the following formula (there is a pattern, I suppose you could prove it by induction): $P(k) = \sum_{i =0}^{k} \frac{(-1)^{i}}{i!}$ .

So $P(n,k) = \frac{1}{(n-k)!} \sum_{i=0}^{k} \frac{(-1)^{i}}{i!}$ .

Thus $P(n,n) = \sum_{i=0}^{k} \frac{(-1)^{i}}{i!}$ . This is about $\frac{1}{e}$ .

Then the probability that not all the people take their wrong wallets is $1 - \frac{1}{e}$ (some people could take wrong wallets, while other people take correct wallets).

The Following 2 Users Say Thank You to heathrowjohnny For This Useful Post:
Nyoxis, ThePerfectHacker
$Donate to MHF$