 Posers and Puzzles

1. 01 Aug '13 09:38
I have n letters and n envelopes. If I put the letters in the envelopes randomly, one in each, find the probability that at least one letter is in the right envelope.
2. 01 Aug '13 21:14
Originally posted by talzamir
I have n letters and n envelopes. If I put the letters in the envelopes randomly, one in each, find the probability that at least one letter is in the right envelope.
n
3. 02 Aug '13 20:581 edit
Originally posted by neilarini
n
It is just 1 - 1/n.

The series of probabilities that all letters will be in the wrong envelop is:

P = (n-1)/n * (n-2)/(n-1) * ... * 2/3 * 1/2

which reduces to

P = (n - 1)! / n! = 1/n

The probably of any given letter being in the correct envelop is the inverse:

~P = 1 - P

~P = 1 - 1/n

This is actually the same odds you get for card games like poker: "If I draw n cards, and I need to draw any one of X cards to win, what are my chances of winning?"
4. 03 Aug '13 15:02
Is it..?

1 letter, 1 envelope: 1 out of 1. 100 % chance; not 1 - 1/1 = 0%
2 of each: 1 out of 2. 50 % chance. = 1 - 1/2
3 of each: 4 out of 6. 67 % chance. = 1 - 1/3
4 of each: 14 out 24. about 58.3%, not 1 - 1/4 = 75%.
5. 04 Aug '13 14:24
For 1 envelop, (n-1)! / n! doesn't quite simplify to 1/n, you're right.

P = (n-1)! / n! = 0/1
~P = 1 - 0/1 = 1

I'm trying to figure why it doesn't work for n > 3. I think because I'm double-counting certain cases like:

n = 4
3/4 chance of not drawing 1: draw 3
2/3 chance of not drawing 2: draw 4
Now there are no possible ways to match any envelope.
6. 20 Aug '13 20:44
Consider this as all the possible permutations of n numbers. Letter to the right envelope then matches the case of some number k is at the k'th place.

n = 1: only sequence is 1. 1 / 1! = 1, so 100% chance.

n = 2: new sequences can be generated by replacing any number in any above sequence with a 2, and moving the replaced number to the end of the sequence. If it was formerly in the right place, this reduces the # of letters to the right place by one; if not, it the number of letters to the right place stays the same. OR, for any sequence above, 2 can be added to the end, increasing the # of letters to the right place by one.

Replace: 1 --> 21. reduces the # of hits to zero. "zero hits, two misses." (0,2)
Add to the end: 1 --> 12. adds the # of hits to two. "zero misses, two hits." (2,0)

n = 3:
(0,2) sequence; replace either with a three for 2x(0,3) or add 3 to the end (1,2).
(2,0) sequence; replace either with a three for 2x(1,2) or add 3 t the end (3,0)

(0,3) x2
(1,2) x3
(3,0) x1 four involve hits. 4/3! = 67%

n = 4:
(0,3)x2: replace any for 6x(0,4) or add 4 to the for 2x(1,3)
(1,2)x3: replace the only hit for 3x(0,4), replace either miss for 6x(1,3) or add the end for 3x(2,2)
(3,0): replace any hit for 3x(2,2) or add 4 to the end for (4,0).

Which yields
(0,4) x9
(1,3) x8
(2,2) x6
(4,0) x1 all but 9 include at least one hit, so 15/4! gives the likelihood.

And so on and and so forth. There is a non-trivial limit for the chance of at least one hit as n grows without limit, and the sequences approaches that value fast. Sadly, so far I haven't figured out a pretty way to get the likelihood for k envelopes in a pretty, closed form.