Author |
Topic: Misaddressed Letters (Read 2909 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Misaddressed Letters
« on: May 26th, 2003, 10:28pm » |
 Quote  Modify
|
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)
|
| « Last Edit: May 27th, 2003, 1:54pm by william wu » |
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Dante
Newbie
Gender:
Posts: 7
|
|
Re: Misaddressed Letters
« Reply #1 on: Jun 5th, 2003, 7:24am » |
Quote Modify
|
Okay, despite lurking in these forums for a LONG time, this is my first post. So go easy on me 
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.
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 
|
|
IP Logged |
|
|
|
Dante
Newbie
Gender:
Posts: 7
|
|
Re: Misaddressed Letters
« Reply #2 on: Jun 5th, 2003, 9:30am » |
Quote Modify
|
Interesting. Sorry I maligned your answer THUDandBLUNDER - I never came across that notation before (or indeed subfactorials or derangement). Time to read up on the subject I think
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Misaddressed Letters
« Reply #3 on: Jun 5th, 2003, 6:05pm » |
Quote Modify
|
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!
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print