XL OM - III - Zadanie 1

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ść:

\[<br /> k + d_k = m_k \ \textrm{lub} \ k + d_k = m_k + n.<br /> \]

Tę alternatywę można zapisać w postaci

\[<br /> (1) \qquad k + d_k = m_k + \epsilon_k n, \epsilon_k \in \{0,1\} , k = 0,1,\ldots, n-1.<br /> \]

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

\[<br /> \sum_{k=0}^{n-1} d_k = \sum_{k=0}^{n-1} m_k = \sum_{k=0}^{n-1} k = \frac{n(n-1)}{2}.<br /> \]

Dodając stronami $ n $ równości (1) (sumowanie po $ k $ od $ 0 $ do $ n-1 $) otrzymujemy

\[<br /> \frac{n(n-1)}{2} + \frac{n(n-1)}{2} = \frac{n(n-1)}{2} + sn, \ \textrm{gdzie} s=\sum_{k=0}^{n-1} \epsilon_k.<br /> \]

Stąd zaś wynika, że $ s $ (liczba całkowita!) równa się $ \frac{1}{2}(n-1) $ - wbrew założeniu, że $ n $ jest liczbą parzystą. Sprzeczność kończy dowód.

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Komentarze

Dodaj nową odpowiedź