XL OM - III - Zadanie 1

Zawody matematyczne:

XL OM, 1988-1989

Etap:

III

Do obrad przy okrągłym stole zasiadła parzysta liczba osób. Po przerwie obiadowej uczestnicy zajęli miejsca przy stole w sposób dowolny. Udowodnić, że istnieją dwie osoby przedzielone tą samą, co przed przerwą, liczbą osób.

Rozwiązanie

Oznaczmy liczbę osób przez $n$ . Numerujemy miejsca przy stole kolejno liczbami całkowitymi od $0$ do $n - 1$ ; miejsce nr $0$ i kierunek obiegu ustalamy dowolnie. Osoba zajmująca przed przerwą miejsce $k$ zajmuje po przerwie miejsce $m_k$ ; tak określony ciąg $(m_0,\ldots , m_{n-1})$ stanowi permutację zbioru $\{0,1,\ldots, n-1\}$ .

Przypuśćmy, że osoba z miejsca $k$ przesunęła się o $d_k$ miejsc (w ustalonym przez nas kierunku obiegu); $d_k \in \{0,1,\ldots, n - 1\}$ . Dla każdego $k$ zachodzi więc równość:

$ k + d_k = m_k \ \textrm{lub} \ k + d_k = m_k + n. $

Tę alternatywę można zapisać w postaci

$ (1) \qquad k + d_k = m_k + \epsilon_k n, \epsilon_k \in \{0,1\} , k = 0,1,\ldots, n-1. $

Dla dowodu tezy zadania wystarczy wykazać, że pewne dwie osoby przesunęły się o tyle samo miejsc, czyli, że $d_k = d_i$ dla pewnej pary różnych liczb $k$ , $l$ . Załóżmy więc, że tak nie jest. Wówczas ciąg $(d_0,d_1,\ldots, d_{n-1})$ stanowi permutację zbioru $\{0,1,\ldots, n - 1\}$ . A zatem