Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  1. Standard member talzamir
    Art, not a Toil
    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. Standard member forkedknight
    Defend the Universe
    02 Aug '13 20:58 / 1 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. Standard member talzamir
    Art, not a Toil
    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. Standard member forkedknight
    Defend the Universe
    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. Standard member talzamir
    Art, not a Toil
    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.