Zadanie nr 8377230

Pięcioro przyjaciół zamierza na przyjęciu dać sobie nawzajem prezenty w taki sposób, że każdy da tylko jednej osobie prezent, i każdy otrzyma prezent tylko od jednej osoby (oczywiście nikt nie daje prezentu sobie). Na ile sposobów można to zrobić?
A) 5 B) 10 C) 44 D) 50 E) 120

Rozwiązanie

Ustalmy jedną osobę, powiedzmy . Może ona dać prezent na 4 sposoby. Niech będzie osobą, która otrzymała prezent od . Mamy teraz dwie istotnie różne sytuacje.

Jeżeli daje prezent , to , i muszą dać sobie prezenty nawzajem – mogą to zrobić na dwa sposoby.

W sumie, w tej sytuacji, mamy 4 ⋅2 = 8 możliwości

Jeżeli nie daje prezentu , to daje jednej z pozostałych 3 osób. Każdy z tych wyborów jest równoważny, powiedzmy, że daje prezent .

Dalej, może dać prezent na 3 sposoby i łatwo zobaczyć, że niezależenie od tego, której osobie daje prezent, osoby i nie mają już żadnego wyboru. Rzeczywiście, jeżeli daje prezent , to i muszą dać prezenty sobie nawzajem. Jeżeli natomiast daje prezent np. , to musi dać (bo musi od kogoś dostać prezent) i musi dać . Podobnie jeżeli daje prezent . Mamy więc w tym przypadku 4⋅3 ⋅3 = 36 możliwości.