3
$\begingroup$

Possible Duplicate:
Number of permutations where n ≠ position n

In how many ways can 5 messages be posted in 5 envelopes so that no correct message is posted, if each envelope only has one correct message from the 5, and each message only has one correct envelope?

Possible notation: We represent each envelope by an upper-case letter, $A, B, C, D, E$, and each message by a lower-case letter, $a,b,c,d,e$, and denote the positioning of the messages in envelopes as $A_x B_xC_x D_x E_x~$, such that a possible envelope-message configuration might be $A_c B_d C_b D_e E_a~$, with message $c$ being slotted in envelope $A$ and message $d$ being slotted in envelope $B$ etc. The correct message for envelope $A$ is message $a$ etc.

I have a potential solution to this problem, but I'm wondering if there are some alternate, simpler solutions.

  • 1
    There is, as the links show,$a$lot of material on this, of$a$general character. But for $5$ envelopes, all one needs is patience and carefulness, though$a$small idea saves quite a bit of time. Letter $a$ goes into one of $B$, $C$, $D$, $E$. By symmetry the number of "good" permutations is $4$ times the number of good permutations that send $a$ to $B$. Now just make a complete list of the good permutations that send $a$ to $B$. Hint: they are of two types (i) $b$ is sent to $A$ and (ii) $b$ is sent somewhere else. It should not take more than a few minutes.2011-09-29

0 Answers 0