You are given 100 addressed envelopes and 100 addressed letters to be inserted into the envelopes. If the letters are inserted randomly into the envelopes, what is the probability that no letter will reached its destination?

  • 2
    $\begingroup$ I believe this serves better for Math.StackExchange. $\endgroup$ – Sid Jan 21 '17 at 7:07
  • 1
    $\begingroup$ @Sid, I belive not. Do you see straightforward solution? Or why you say so? 90% of puzzles on PuzzleSE involve math and still belong here. $\endgroup$ – klm123 Jan 21 '17 at 7:08
  • $\begingroup$ How exactly randomly? You can toss letters like a deck of cards and then put top letter to 1st envelop, next topest - to 2nd, etc. Or you can take first letter, select random envelop and put the letter in; take 2nd letter, select random Free envelop and put the letter in; etc. There are a lot of other ways to make random matching, Result will be different often times. $\endgroup$ – klm123 Jan 21 '17 at 7:11
  • $\begingroup$ You pick an envelope and than insert a letter in it, picked randomly from the remaining letters. $\endgroup$ – Moti Jan 21 '17 at 7:32
  • $\begingroup$ @klm123 I would assume an unweighted random distribution, i.e. the probability a letter would end up in a certain envelope is 1/100 and there are no double-ups. $\endgroup$ – boboquack Jan 21 '17 at 7:33

This is what is known as The Montmort's Matching problem

The notation that is used is $$ \frac{!100}{100!}$$ where $$ !n = \text{Round}\left(\frac{n!}{e}\right)$$

So, good luck on solving that. I can't do 100! right now.

Here's the source of my answer:

| improve this answer | |
  • $\begingroup$ I was not aware of that one, which is identical to mine. Since the answer is wrong, there and here - it still has value. $\endgroup$ – Moti Jan 21 '17 at 7:35
  • $\begingroup$ It's hard to get an exact answer, but can't you say round (100!/e) / 100! is going to be pretty darn close to 1/e? $\endgroup$ – ffao Jan 22 '17 at 21:23
  • $\begingroup$ @ffao Yeah, it's pretty close to 1/e. I should have thought that. $\endgroup$ – Sid Jan 23 '17 at 8:03

As @Sid said, the probability is:


$!n$ is known as the derangement function or subfactorial function, derangement coming from de-arrange, which is basically the problem stated in mathematical terms.

After a calculation with the first formula from here, we get $!100$ equal to 34332795984163804765195977526776142032365783805375784983543400282685180793327632432791396429850988990237345920155783984828001486412574060553756854137069878601

By the standard calculation, $100!$ is equal to 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

So dividing one by the other, to get the probability, we find that it simplifies (not much) to 31558460190368334142403172251016987632596585387385351360123576545034640511335607814234249336435599042786906208463545257680087329214038704042662363131791 Vinculum 85784788869626424111622401884222790734458947712066172203969776843158677495888832458667541716332051322446135686492023481931137024000000000000000000000000

Which is approximately 0.367879441171442321595523770161460867445811131031767834507...

| improve this answer | |
  • $\begingroup$ The answer is wrong as the source to Sid answer. $\endgroup$ – Moti Jan 21 '17 at 7:36
  • $\begingroup$ @Moti, can you point to where I've made a mistake? I've taken the number of ways you can take the envelopes completely incorrectly (one definition of $!n$) and divided it by the number of ways you can take the envelopes. $\endgroup$ – boboquack Jan 21 '17 at 7:42
  • $\begingroup$ Montmort's matching problem seems to me to have a basic miss interpretation by starting with the Bernoulli trials assumption that attempts to use the independent probability of 1/n rather than allowing the progression from one choice to another. $\endgroup$ – Moti Jan 21 '17 at 7:56

The answer is to the best of my understanding as follows: 99/100 X 98/99 X 97/98 X... 2/3 X 1/2 = 1/100. What is wrong with this process - the first letter can be inserted only in 99 envelopes of the 100 (probability of 99/100), the second in 98 of the remaining 99 (probability of 98/99)... and so on. Multiply the probabilities to get the result of 1/100.

| improve this answer | |
  • 4
    $\begingroup$ Suppose I put letter #1 into envelope #2. Then letter #2 can go in any 99 of the remaining envelopes, so this solution doesn't work. $\endgroup$ – boboquack Jan 21 '17 at 7:56
  • $\begingroup$ I realized later that the probability is actually higher. $\endgroup$ – Moti Jan 22 '17 at 7:06

Not the answer you're looking for? Browse other questions tagged or ask your own question.