Zadanie ZM-1527
o zadaniu...
- Publikacja w Delcie: kwiecień 2017
- Publikacja elektroniczna: 30 marca 2017
Na przyjęcie przyszło 
osób w kapeluszach 
Następnie każde dwie osoby przywitały się dokładnie raz, przy czym każde powitanie polegało na zamianie kapeluszami, które w danej chwili witające się osoby miały na głowach. Okazało się, że po nastąpieniu wszystkich powitań każdy miał z powrotem swój kapelusz. Udowodnić, że taka sytuacja jest możliwa wtedy i tylko wtedy, gdy 
daje resztę 0 lub 1 przy dzieleniu przez 4.
do 
oraz oznaczmy liczbę wszystkich powitań przez 
Niech 
będzie permutacją zbioru 
która liczbie 
przyporządkowuje numer osoby, mającej na głowie kapelusz 
-tej osoby po 
-tym powitaniu. Mamy więc 
oraz 
gdzie 
jest transpozycją, a 
to numery osób uczestniczących w 
-tym powitaniu.
jest iloczynem 
transpozycji (wszystkich możliwych par elementów zbioru 
). Z drugiej strony, w myśl warunków zadania, 
Ponieważ identyczność jest permutacją parzystą, więc wynika z tego, że 
skąd uzyskujemy 
To oznacza, że jeżeli opisana sytuacja jest możliwa, to 
daje resztę 0 lub 1 przy dzieleniu przez 4.
dającego resztę 0 lub 1 przy dzieleniu przez 4 istnieje kolejność powitań prowadząca do opisanej w treści zadania sytuacji, przeprowadzimy dowód indukcyjny.
to bezpośrednio sprawdzamy, że
mamy odpowiednią kolejność powitań, czyli odpowiedni iloczyn transpozycji. Aby uzyskać odpowiednią kolejność dla 
dokonajmy następujących zmian w tym iloczynie:
W ten sposób uzupełniliśmy iloczyn o 
transpozycji (odpowiadających powitaniom z "nową" osobą numer 
) i łatwo sprawdzić, że warunki zadania dla nowej kolejności są spełnione.
osób, dokonujemy podobnych zmian:
oraz dołączamy (w dowolnym miejscu) zestaw sześciu kolejno po sobie następujących powitań czterech nowych osób:
osobach. To kończy dowód indukcyjny.