XII OM - III - Zadanie 6

Zawody matematyczne:

XII OM, 1960-1961

Etap:

III

Ktoś napisał sześć listów do sześciu osób i zaadresował do nich sześć kopert. Iloma sposobami można listy tak włożyć do kopert, żeby żaden list nie trafił do właściwej koperty?

Rozwiązanie

Niech $F (n)$ oznacza ilość wszystkich sposobów takiego włożenia $n$ listów $L_1, L_2, \ldots, L_n$ do $n$ kopert $K_1, K_2, \ldots, K_n$ , żeby żaden list $L_i$ nie trafił do właściwej koperty $K_i$ , czyli krócej, żeby nie było żadnego ,,trafienia''. Mamy obliczyć $F (6)$ .

Przypuśćmy, że wkładamy fałszywie wszystkie listy umieszczając list $L_1$ w kopercie $K_i$ ( $i \ne 1$ ). Możliwe są $2$ przypadki :

a) List $L_i$ trafił do koperty $K_1$ . Pozostałe $4$ listy należy wówczas włożyć fałszywie do pozostałych $4$ kopert, na co jest $F (4)$ sposobów. Ponieważ $K_i$ może być każdą z $5$ kopert $K_2$ , $K_3$ , $K_4$ , $K_5$ , $K_6$ , więc przypadek a) może się zdarzyć $5 \cdot F (4)$ razy.

b) List $L_i$ nie trafia do koperty $K_1$ . Przypisując listowi $L_i$ kopertę $K_1$ jako ,,niby-właściwą'' możemy powiedzieć, że wtedy żaden z listów $L_2$ , $L_3$ , $L_4$ , $L_5$ , $L_6$ nie trafia do właściwej koperty, na co jest $F (5)$ sposobów. A ponieważ $K_i$ może być - jak poprzednio - każdą z $5$ kopert, więc przypadek b) może się zdarzyć $5 \cdot F (5)$ razy.

Ponieważ przypadki a) i b) obejmują wszystkie możliwości, więc

$ F (6) = 5P (5) + 5P (4) $

Analogicznie

$F (5) = 4F (4) + 4F (3)$

$F (4) = 3F (3) + 3F (2)$

$F (3) = 2F (2) + 2F (1).$

Lecz oczywiście

$ F(1)=0, \ F(2) = 1, $

wobec czego z równań poprzednich otrzymujemy kolejno,

$ F (3) = 2,\ F (4) = 9,\ F (5) = 44, \ F (6) = 265. $

Uwaga. W rozumowaniach powyższych rozwiązań I i II liczba $6$ nie odgrywa żadnej istotnej roli. Można je równie dobrze zastosować do $n$ listów i $n$ kopert. Sposób I prowadzi wówczas do wzoru

$ (1) \qquad F (n) = (n - 1) F (n - 1) + (n - 1) F (n - 2). $

Jest to tzw. wzór zwrotny, albo redukcyjny, z którego można obliczyć $F (n)$ , gdy znane są wartości $F (n - 1)$ i $F (n - 2)$ . Podobnie sposób II prowadzi do wzoru redukcyjnego

$ (2) \qquad F(n) = n!- \binom{n}{1} F(n - 1) - \binom{n}{2} F(n - 2) - \ldots - \binom{n}{n-2} F (2) - 1. $

Wzór (1) pozwala w następujący sposób obliczyć $F (n)$ w zależności od $n$ . Napiszemy ten wzór w postaci

$ (3) \qquad F (n) - n F (n - 1 )= - [F (n - 1) - (n - 1) F(n-2)]. $

Ze wzoru (3) widzimy, że funkcja $F (k) - kF (k - 1)$ ma dla każdego naturalnego $k > 1$ tę samą wartość bezwzględną, ale zmienia znak przy przejściu od $k$ do $k + 1$ . A ponieważ