wu :: forums
wu :: forums - Misaddressed Letters

Welcome, Guest. Please Login or Register.
Jul 5th, 2022, 9:59pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: william wu, Grimbal, Icarus, Eigenray, ThudnBlunder, towr, SMQ)
   Misaddressed Letters
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Misaddressed Letters  (Read 2771 times)
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Misaddressed Letters  
« on: May 26th, 2003, 10:28pm »
Quote Quote Modify 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: male
Posts: 7
Re: Misaddressed Letters  
« Reply #1 on: Jun 5th, 2003, 7:24am »
Quote Quote Modify Modify

Okay, despite lurking in these forums for a LONG time, this is my first post.  So go easy on me Grin
 
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  Wink
 

IP Logged
Dante
Newbie
*





   


Gender: male
Posts: 7
Re: Misaddressed Letters  
« Reply #2 on: Jun 5th, 2003, 9:30am »
Quote Quote Modify 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 Wink
IP Logged
Icarus
wu::riddles Moderator
Uberpuzzler
*****



Boldly going where even angels fear to tread.

   


Gender: male
Posts: 4863
Re: Misaddressed Letters  
« Reply #3 on: Jun 5th, 2003, 6:05pm »
Quote Quote Modify 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
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright 2000-2004 Yet another Bulletin Board