Author 
Topic: Misaddressed Letters (Read 2756 times) 

william wu
wu::riddles Administrator
Gender:
Posts: 1291


Misaddressed Letters
« on: May 26^{th}, 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. (BernoulliEuler Problem of the Misaddressed Letters)

« Last Edit: May 27^{th}, 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 5^{th}, 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 (n1 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 specialcase of the problem, for which I will use the notation F(x). So: M(n) = (n1)(F(n1)) 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(x1). If we place it in a nonfree envelope, we have the same free envelope as before, and a new free letter (matching the nonfree envelope we just filled). This is F(x1). Therefore: F(x) = M(x1) + (x1)(F(x1)) Expressing in terms of F: F(x) = (x2)F(x2) + (x1)(F(x1)) Or more usefully in terms of M: F(x) = M(x1) + M(x) Therefore: M(n) = (n1)(M(n2) + M(n1)) 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 5^{th}, 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 5^{th}, 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



