XXIV OM - I - Zadanie 2

Zawody matematyczne:

XXIV OM, 1972-1973

Etap:

Dowieść, że spośród 25 różnych liczb dodatnich można wybrać dwie, których ani suma, ani różnica nie jest równa żadnej z pozostałych liczb.

Rozwiązanie

Oznaczmy dany zbiór liczb przez $A = \{a_1, a_2, \ldots, a_{25}\}$ , gdzie $0 < a_1 < a_2 < \ldots < a_{25}$ . Przypuśćmy, że dla dowolnych $r$ , $s$ , gdzie $1 \leq r < s \leq 25$ , zachodzi: $a_s + a_r \in A - \{a_r, a_s\}$ lub $a_s - a_r \in A - \{a_r, a_s\}$ . Oczywiście $a_r - a_s < 0$ i wobec tego liczba $a_r - a_s$ nie należy do $A$ .

Ponieważ dla $i = 1, 2, \ldots, 24$ mamy $a_{25} + a_i > a25$ , więc $a_{25} + a_i \not \in A$ . Zatem na mocy przypuszczenia $24$ liczby $a_{25} - a_i$ tworzą ciąg malejący o wyrazach należących do zbioru $A - \{a_{25}\}$ o $24$ elementach. Stąd

$<br /> a_{25} - a_i = a_{25-i} \ \textrm{dla}\ i = 1, 2, \ldots, 24.<br />$

Ponieważ dla $j = 2, 3, \ldots, 23$ mamy $a_{24} + a_j > a_{24} + a_1 = a_{25}$ , więc $a_{24} + a_i \not \in A$ i stąd na mocy przypuszczenia mamy $a_{24} - a_j \in A$ . Ponadto $a_{24} - a_j \leq a_{24} - a_2 = (a_{25} - a_1) - (a_{25} - a_{23}) = a_{23} - a_1 < a_{23}$ . Zatem $22$ liczby $a_{24} - a_j$ tworzą ciąg malejący o wyrazach należących do zbioru $A - \{a_{23}, a_{24}, a_{25} \}$ o $22$ elementach. Stąd

$<br /> a_{24} - a_j = a_{24-j} \ \textrm{dla}\ j = 2, 3, \ldots, 23.<br />$

W szczególności $a_{24} - a_{12} = a_{12}$ , a więc $a_{24} - a_{12} \not \in A - \{a_{12}, a_{24}\}$ . Mamy również $a_{24} + a_{12} > a_{24} + a_1 = a_{25}$ , a więc $a_{24} + a_{12} \not \in A$ . Przeczy to początkowemu przypuszczeniu.