2n uczniów i n przyjaciół, na ile sposobów można ich usadzić

[alek22999]

Mamy \(\displaystyle{ 2n}\) uczniów, z których każdy ma przynajmniej n przyjaciół. Pokaż, że można ich usadzić w \(\displaystyle{ n}\) ławkach tak, by każdy z nich siedział z przyjacielem. Pokaż też, że jeśli \(\displaystyle{ n \ge 1}\), to może być to zrobione na conajmniej dwa sposoby.

[Mruczek]

Zróbmy graf, w którym uczniowie to wierzchołki, a każda para uczniów, którzy się znają jest połączona krawędzią.
Na mocy twierdzenia Diraca w tym grafie jest cykl Hamiltona.
Wybieramy z tego cyklu co drugą krawędź. Możemy to zrobić na dwa sposoby.
Każdy z tych dwóch sposobów wyborów odpowiada pewnemu usadzeniu w ławkach - usadzamy uczniów połączonych krawędzią w jednej ławce.