Zadanie z Kangura - Junior 2007

[Brzezin]

Proszę o rozwiązanie zadania za pomocą kombinatoryki. Oto one:

Czworo 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ć? (Odpowiedzią jest liczba 9.)

Niestety nie mogę dość do wyniku. Gdyby znalazł się ktoś tak miły i uprzejmy i mógłby napisać co i jak to byłoby wspaniale

Pozdrawiam Maks

[Dumel]

rozpatrzmy zbiory będące permutacjami zbioru \(\displaystyle{ {1,2,3,4}}\). przyjmijmy że liczba na i-tej pozycji oznacza że osoba \(\displaystyle{ i}\) daje prezent osobie oznaczonej tą liczbą. jest to zgodne z warunkami zadania bo każdy musi dostawać i dawać jeden prezent. mamy \(\displaystyle{ 4!}\) wszystkich permutacji - trzeba odjąć te, w których ktoś daje prezent samemu sobie, czyli liczba i jest w nich na i-tej pozycji.
wszystkie osoby dają prezent same sobie - \(\displaystyle{ 1}\) permutacja
3 osoby - nie zachodzi (czwarta też by sobie dawała)
2 osoby - \(\displaystyle{ {4 \choose 2}=6}\) -pozostałe dwie mają jednoznacznie wyznaczoną osobę której dają prezent
1 osoba - \(\displaystyle{ 4*2=8}\) - wybieramy jedną osobę, która daje prezent sama sobie, następna może dać prezent jednej z dwóch kolejnych osób, a one już wyboru nie mają

czyli \(\displaystyle{ 4!-1-6-8=9}\)

to zadanie chyba w zeszłym roku też w tej kategorii było, bo skądś je kojarzę i chyba właśnie z kangura