Komentarz

XXXII - III - Zadanie 4

Na stole leży $ n $ żetonów oznaczonych liczbami całkowitymi. Jeśli wśród tych żetonów znajdują się dwa oznaczone równymi liczbami, np. liczbą $ k $, to zastępujemy je jednym żetonem z liczbą $ k+1 $ i jednym z liczbą $ k-1 $. Udowodnić, że po skończonej (nieujemnej) liczbie takich zmian wszystkie żetony będą oznaczone różnymi liczbami.

Rozwiązanie

Udowodnimy najpierw następujący lemat:
Lemat. Niech $ m_0 $ będzie minimalną liczbą spośród liczb wypisanych na żetonach znajdujących się na stole przed dokonaniem jakiejkolwiek zmiany. Jeśli po $ k $ zmianach wśród liczb występujących na żetonach liczby $ m_1^{(k)}, m_2^{(k)},\ldots,m_{j_k}^{(k)} $ są wszystkimi liczbami nie większymi od $ m_0 $, przy czym $ m_{j_k}^{(k)} \leq m_{j_k-1}^{(k)} \leq \ldots \leq m_2^{(k)} \leq m_1^{(k)} \leq m_0^{(k)} = m_0 $, to $ m_i^{(k)}-m_{i+1}^{(k)} \leq 2 $ dla $ i =0, 1, \ldots, j_k-1 $.

Dowód lematu przeprowadzimy przez indukcję względem $ k $.

Dla $ k = 1 $ może być jedynie $ m_1^{(1)} = m_0- 1 $ i ta sytuacja występuje wtedy, gdy były na początku co najmniej dwa żetony z liczbą $ m_0 $. Oczywiście więc $ m_0^{(1)}-m_1^{(1)} \leq 2 $.

Załóżmy, że dla pewnego $ k $ liczby $ m_1^{(k)}, \ldots, m_{j_k}^{(k)} $ są wszystkimi liczbami nie większymi od $ m_0 $ wypisanymi na żetonach po $ k $ zmianach oraz

\[<br /> m_{j_k}^{(k)} \leq m_{j_k-1}^{(k)} \leq \ldots \leq m_2^{(k)} \leq m_1^{(k)} \leq m_0^{(k)} = m_0 \ \textrm{i} \ m_i^{(k)} - m_{i+1}^{(k)} \ \textrm{dla} \ i=0,1, \ldots, j_k-1.<br /> \]

Jeśli w kroku $ (k+ 1) $-szym wymieniamy dwa żetony z liczbą większą od $ m_0 $, to każdy wyraz $ m_i^{(k+1)} $ jest równy odpowiednio $ m_i^{(k)} $, teza jest więc oczywiście spełniona. Niech więc $ m_i^{(k)}= m_{i+1}^{(k)} = m $ i $ (k+1) $-szy krok naszego postępowania polega na zastąpieniu żetonów z liczbą $ m $ przez żetony z liczbami $ m+1 $ oraz $ m-1 $. Ciąg $ (m_i^{(k+1)}) $ powstał więc z ciągu $ (m_i^{(k)}) $ przez zastąpienie dwóch wyrazów równych $ m $ przez wyrazy równe $ m+1 $ i $ m- 1 $. Różnica między tymi wyrazami wynosi $ 2 $, różnica między każdym z tych wyrazów, a wyrazem sąsiednim nie przekracza $ 2 $, różnica między każdą parą innych wyrazów sąsiednich nie uległa zmianie, więc też nie przekracza $ 2 $. Kończy to indukcyjny dowód lematu.

Z lematu wynika, że po każdej zmianie liczba wypisana na dowolnym żetonie nie będzie mniejsza od $ m_0-2n $.

Zauważmy teraz, że jeśli przed rozpoczęciem procedury opisanej w zadaniu dodamy do każdej z liczb wypisanych na żetonach ustaloną liczbę całkowitą, to nie zmieni to w niczym naszego zadania. Dodając ewentualnie liczbę $ 2n-m_0+ 1 $ możemy zakładać, że zarówno na początku, jak i po każdej zmianie wszystkie liczby wypisane na żetonach są dodatnie. Rozważmy teraz iloczyn $ P_0 $ liczb wypisanych początkowo na żetonach, iloczyn $ P_1 $ liczb wypisanych po dokonaniu pierwszej zmiany, iloczyn $ P_2 $ liczb na żetonach po dokonaniu drugiej zmiany itd. Każdy wyraz ciągu $ P_i $ jest iloczynem liczb naturalnych, przy czym $ P_{i+1} $ powstaje z $ P_i $ przsz zastąpienie dwóch czynników równych $ k $ iloczynem $ (k+1) (k-1) $, a więc $ P_i = k^2c $, $ P_{i + 1} = (k+1) (k-1)c $. Ponieważ $ c > 0 $, oraz $ k^2 > k^2-1 = (k+1)(k-1) $, więc $ P_i > P_{i+ 1} $. Ciąg $ (P_i) $ jest więc ciągiem malejącym liczb naturalnych, a taki ciąg musi być skończony. Dowodzi to, że po skończonej liczbie kroków wszystkie żetony będą oznaczone różnymi liczbami.

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

Dodaj komentarz