## Misdirected

Posted by Chris on February 1, 2011 – 4:39 pm

You have k letters and k addressed envelopes. How many different ways are there to place every letter into a wrong envelope?

NB You can only put one letter in one envelope.

February 1st, 2011 at 5:58 pm

I think it’s (1-k)! Since there are k! different ways of placing letters in envelopes.

February 1st, 2011 at 5:59 pm

Sorry, scratch that, I meant (k-1)!

February 1st, 2011 at 6:04 pm

Nope!

February 1st, 2011 at 6:23 pm

I’m going with k*(k+1)/2.

February 1st, 2011 at 6:33 pm

Wild stab in the dark, E(meaning sigma) ==>

0

E(ri-1)

r=k

no no no, gibberish, my brain wants a 1/k in there… like

0

E(1/k)*r

r=k

But I’m still very doubtful…

February 1st, 2011 at 6:52 pm

No-one is even warm (except a Σ could sensibly be used). You won’t get it by guessing.

Here’s a non-hint. Letter 1 can go into 1 of k-1 envelopes. If e.g. put letter 1 into envelope 2, then letter 2 can also go into any of the remaining k-1 envelopes.

February 1st, 2011 at 11:13 pm

f(1)=0

f(2)=1

f(k)(odd)=k(k-1)*f(k-2)+k-1

f(k)(even)=k*f(k-1)+1

February 2nd, 2011 at 3:29 am

Given the 1st reply states ‘the number of total ways to put k letters into k envelopes is k!

now there is only 1 way that all the correct letters in all the correct evelopes can occur in k!

therefore the number of ways to get it wrong is….

k!-1

February 2nd, 2011 at 5:23 am

Nathan’s answer is correct but is written in an awful way. First of all, I think Chris wants a closed formula (i.e., one that involves a sum), rather than a recursive one. And second, even the recursive formula is “ugly”, since it consists of two completely different rules that even involve different “predecessors”! I will give a small hint by “fixing” the recursive formula of Nathan via: f(k)=k*f(k-1)+(-1)^k. Of course, somebody should convert it to a partial sum for the exp(-1) Taylor expansion, which is the explicit formula I gave too many hints, so I’d better stop now.

February 2nd, 2011 at 7:10 am

I see that Nathan is on the right track. Obviously, Slavy has read the book and seen the film

As usual, I don’t care so much about the final solution, but how it was obtained.

February 2nd, 2011 at 9:20 am

Hi Craig. The question implies that ALL of the letters are to be incorrectly addressed, not at least one.

Even so, your answer wouldn’t be right. You can’t only get one wrong and the others right; if one is wrong, then it’s used the envelope of another. So the letter for that envelope must be placed in another envelope as well, and there are k-1 possibilities for that.

February 2nd, 2011 at 11:19 am

The answer is either ((k!)/2)-1 or ((k!)-1)/2 because if you have one letter wrong it cuts your probabilities in half for the other letters and then subtract one for the right answer or vice versa.

February 2nd, 2011 at 11:43 am

Hi JG. It’s not that simple. Nathan is very nearly there, and Slavy has given many clues.

February 3rd, 2011 at 4:17 am

k

February 3rd, 2011 at 7:28 am

Actually, I don’t know how to find the answer by induction (i.e., recursively) and I checked Nathan’s formula by solving the problem first and then comparing the solution to his. So, to some extend my hints are misleading and useless, since one can verify them only after they solve the problem themselves. A useful hint is to try to compute the number of cases, where at least one letter is in the correct envelope and subtract it from the total number of possibilities. The latter is not that easy to find and you should additionally consider all the intermediate cases, when at least N letters are in their own envelopes for any N=2,…,k.

February 3rd, 2011 at 8:17 am

Hi Slavy. When I did it, I used f{k) and g(k) for the two different cases. I was then able to construct a recursion. After examining it I found the approximate 1/e factor; hence etc.

The comments you made led me to believe that you had completely solved it.

Hi Anthony. A bold (but very wrong) guess.

As it’s still getting attention, I’ll wait before posting my analysis.

February 3rd, 2011 at 9:30 am

k letters

k adressed letters

every letter can be put into every letter, so k*k is my guess

February 3rd, 2011 at 10:15 am

Hi all. There are enough clues on this page to let you know that the solution isn’t trivial. It can only be expressed in terms of a series (or a recursion).

February 3rd, 2011 at 11:27 am

Hi Chris This is a very basic problem in combinatorics so throughout the years I have been seeing it a lot. The first time I solved it was at least 12 years ago…

February 3rd, 2011 at 12:18 pm

There are k letters/envelopes – therefore at most k-1 opportunities to get one envelope/letter combination incorrect.

2 letters incorrectly enveloped- k-2 and so on up to k-k = 0 letters incorrectly enveloped.

k^k-((k-1)+)k-2)+…(k-k))

Please note that I am under a lot of pressure here, no computer, and absolutely no idea! And wrong…

February 3rd, 2011 at 1:31 pm

i tried a buncha methods for like 2 hours and gave up >.>. this problem’s got me ; (.

February 3rd, 2011 at 2:12 pm

Hi mike. I wouldn’t be surprised if it took me that long when I did it.

February 3rd, 2011 at 5:17 pm

I don’t know if it is meaningful, but I’ve noticed the following properties hold true:

f(k) mod (k-1) = 0

g(k) mod (k-1) = 0

February 3rd, 2011 at 5:50 pm

http://www.physics.harvard.edu/academics/undergrad/probweek/sol16.pdf

has the solution and proofs

February 4th, 2011 at 6:24 pm

Wow, this site’s been busy since I last looked.

Let k be the number of letters (and envelopes), then let f[k] be the number of ways of combining the k letters completely incorrectly. NB [] => function brackets.

Let the letters be a, b, c, d, e… and the envelopes be A, B, C, D, E…

There are k-1 ways of putting the first letter into an incorrect envelope. I’ll use

a->B for illustration. That leaves us with bcde… and ACDE…. For this case (i.e. a single letter, b, without a corresponding envelope) let g[k] be the number of ways of getting the addresses completely wrong. So f[k] = (k-1)g[k-1].

We can either put b into A, leaving cde… and CDE… and so f(k-2) ways of completely misadressing those, or we have (k-2) ways of putting b into another envelope, e.g. C,which leaves cde… and ADE… and so for each of those (k-2) possibiities we have g[k-2] ways of completely misaddressing those. There were (k-1) possible ways we could have got to that, so f[k] = (k-1) ( f(k-2) + (k-2) g[k-2]).

Altogether: f[k] = (k-1) g[k-1] = (k-1) ( f(k-2) + (k-2) g[k-2] )

But f[k-1] = (k-2) g[k-2], by using the first half of above.

So f[k] = (k-1) ( f[k-1] + f[k-2] ).

By definition, f[1] = 0 and f[2] = 1 (e.g. using trivial exhaustive analysis, or by sensibly using the equation). So for k = 3 and up, we get: f[k] = 2,9,44,265,1854,14833, 133496, 1334961, 14684570,…

I’m embarrassed to say that I don’t really know how to turn that recursion into a formula using nice maths. However, I noticed some fairly obvious stuff.

e.g. f[11]/f[10] ≈ 11. This suggested that f[k] = k! * s[k], where s[k] is some (almost constant) function of k. I then noticed (it’s all true, LOL) that s[11] ≈ 1/e = 1/2.7182818…

Putting that together, I realised that f[k] -> k!/e as k -> ∞, and so:

f[k] ≈ k!(1/0! – 1/ 1! + 1/2! + 1/3! – 1/4! + …)

I then looked at this with low values of k, and realised that:

f[k] = k! (1/2! – 1/3! + … (-1)^k/k!)

I’ve now taken a look at the link that Nathan gave, and now realise that s[k] is the probability of completely misaddressing all the letters. So, for large k, the probability of misaddressing all the letters -> 1/e.

For k = 2,3,… we have 1/p[k] = 2, 3, 3.66…, 2.7272…, 2.71698…, 2.71844…

And even with only five letters, 1/e is a pretty good approximation to the probability of completely misaddressing all the letters.