Subscribe via feed.

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.


This post is under “MathsChallenge” and has 25 respond so far.
If you enjoy this article, make sure you subscribe to my RSS Feed.

25 Responds so far- Add one»

  1. 1. Hughclid Said:

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

  2. 2. Hughclid Said:

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

  3. 3. Chris Said:

    Nope!

  4. 4. cazayoux Said:

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

  5. 5. Krazeedude Said:

    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…

  6. 6. Chris Said:

    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.

  7. 7. Nathan Said:

    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

  8. 8. Craig Said:

    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

  9. 9. slavy Said:

    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.

  10. 10. Chris Said:

    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.

  11. 11. Chris Said:

    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.

  12. 12. JG Said:

    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.

  13. 13. Chris Said:

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

  14. 14. anthony Said:

    k

  15. 15. slavy Said:

    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.

  16. 16. Chris Said:

    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.

  17. 17. steve Said:

    k letters
    k adressed letters

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

  18. 18. Chris Said:

    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).

  19. 19. slavy Said:

    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…

  20. 20. Karl Sharman Said:

    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…

  21. 21. mike Said:

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

  22. 22. Chris Said:

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

  23. 23. Nathan Said:

    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

  24. 24. Nathan Said:

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

    has the solution and proofs

  25. 25. Chris Said:

    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.

Post a reply




PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_mssql.dll' - The specified module could not be found. in Unknown on line 0 PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_pdo_mssql.dll' - The specified module could not be found. in Unknown on line 0