wu :: forums « wu :: forums - Misaddressed Letters » Welcome, Guest. Please Login or Register. Jul 5th, 2022, 9:59pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: william wu, Grimbal, Icarus, Eigenray, ThudnBlunder, towr, SMQ)    Misaddressed Letters « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
william wu

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
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »