XLVII OM - II - Zadanie 4

Dany jest ciąg $ a_1, a_2, \ldots , a_{99} $ liczb ze zbioru $ \{0,1,2,3,4,5,6,7,8,9\} $. Zakładamy, że dla $ i =1,2, \ldots, 98 $ zachodzą implikacje:

\[<br />
\textrm{jeśli } a_i = 1, \text{ to } a_{i+1} \neq 2; \quad \text{ a jeśli } a_i = 3, \text{ to } a_{i+1} \neq 4.<br />
\]

Udowodnić, że dla pewnych dwóch różnych liczb $ k,l \in \{1,2, ... ,98\} $ zachodzą równości: $ a_k = a_l $ oraz $ a_{k+1} = a_{l+1} $.

Rozwiązanie

Oznaczmy przez $ P_k $ parę uporządkowaną $ (a_k,a_{k+1}) $. Należy udowodnić, że w ciągu $ P_1,P_2,\ldots,P_{98} $ pewna para powtarza się. Zgodnie z warunkiem zadania, pary $ (1,2) $ oraz $ (3,4) $ są w tym ciągu niedopuszczalne.

Przypuśćmy, wbrew tezie, że w ciągu $ P_1,P_2,\ldots,P_{98} $ nie ma powtórzeń. Z dziesięciu liczb jednocyfrowych można utworzyć $ 10 \cdot 10 - 2 = 98 $ różnych par dopuszczalnych. Każda z nich musi zatem wystąpić w tym ciągu dokładnie jeden raz.

Oprócz pary $ (1,1) $ istnieje dziewięć dopuszczalnych par postaci $ (x,1) $ oraz tylko osiem dopuszczalnych par postaci $ (1,y) $. Jeśli wszystkie one mają się pojawić, to jedynka musi raz wystąpić w ciągu $ a_1,a_2,\ldots,a_{99} $ na miejscu, które nie ma prawego sąsiada - czyli na ostatnim miejscu.

Ponieważ role symboli $ 1 $ i $ 3 $ są symetryczne, analogiczne rozumowanie pokazuje, że także trójka musi wystąpić na ostatnim miejscu. Jednak te warunki nie mogą być spełnione jednocześnie. Otrzymana sprzeczność kończy dowód.

Komentarze

Dodaj nową odpowiedź