XLVII OM - II - Zadanie 4

Zawody matematyczne:

XLVII OM, 1995-1996

Etap:

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.