wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Misaddressed Letters
        
(Message started by: william wu on May 26^th, 2003, 10:28pm)

Title: Misaddressed Letters
Post by william wu on May 26^th, 2003, 10:28pm

Suppose one writes n letters and writes the corresponding addresses on n envelopes. How many ways are there of placing all the letters in the wrong envelopes? (That is, there is no letter in a correct envelope.)

Source: A problem studied by Niclaus Bernoulli and L. Euler. Solutions discovered independently. (Bernoulli-Euler Problem of the Misaddressed Letters)

Title: Re: Misaddressed Letters
Post by Dante on Jun 5^th, 2003, 7:24am

Okay, despite lurking in these forums for a LONG time, this is my first post. So go easy on me ;D

THUDandBLUNDER, I think your answer covers the case where letters may be placed in correct envelopes, whereas this problem states that no letter may be in a correct envelope.

I have done a little bit of analysis, but my math isn't up to actually giving the final solution.

[hide]
I will call the final answer M(n)

The first letter may be placed in any envelope except its own (n-1 possibilities), and after doing this we are left with one free envelope (any of the remaining letters may be placed in it), and one free letter (it can be placed in any of the remaining envelopes). This is a special-case of the problem, for which I will use the notation F(x). So:

M(n) = (n-1)(F(n-1))

To solve M, we need only solve F.

Our action in situation F(x) will be to place the free letter in an envelope. This can be either the free envelope, or one of the others. If we place it in the free envelope, we are left with no free letters, and no free envelopes - this is the original problem, so M(x-1). If we place it in a non-free envelope, we have the same free envelope as before, and a new free letter (matching the non-free envelope we just filled). This is F(x-1). Therefore:

F(x) = M(x-1) + (x-1)(F(x-1))

Expressing in terms of F:

F(x) = (x-2)F(x-2) + (x-1)(F(x-1))

Or more usefully in terms of M:

F(x) = M(x-1) + M(x)

Therefore:

M(n) = (n-1)(M(n-2) + M(n-1))

Common sense tells us that

M(1) = 0
M(2) = 1

so

M(3) = 2
M(4) = 9
M(5) = 44
...

I'm sure there's a way to solve equations of this form, but sadly I didn't pay enough attention in school ;)

[/hide]

Title: Re: Misaddressed Letters
Post by Dante on Jun 5^th, 2003, 9:30am

Interesting. Sorry I maligned your answer THUDandBLUNDER - I never came across that notation before (or indeed [hide]subfactorials[/hide] or [hide]derangement[/hide]). Time to read up on the subject I think ;)

Title: Re: Misaddressed Letters
Post by Icarus on Jun 5^th, 2003, 6:05pm

It's a new notation to me too, and I've seen a lot of mathematics. Just shows that there is always something more out there!