LVII OM - II - Zadanie 6

Zawody matematyczne:

LVII OM, 2005-2006

Etap:

Dana jest liczba pierwsza $p$ oraz liczba całkowita $n$ , przy czym $p \geq n \geq 3$ . Zbiór $A$ składa się z $n$ -wyrazowych ciągów o wyrazach ze zbioru $\{0,1,2,\dots ,p-1\}$ i ma następującą własność:

Dla dowolnych dwóch ciągów $(x_1,x_2,\dots ,x_n)$ oraz $(y_1,y_2,\dots ,y_n)$ ze zbioru $A$ istnieją takie różne liczby
$k, l, m$ , że

$ x_k\neq y_k,\quad x_l\neq y_l,\quad x_m\neq y_m. $

Wyznaczyć największą możliwą liczbę elementów zbioru $A$ .

Rozwiązanie

Odpowiedź: $p^{n-2}$ .

Każde dwa różne ciągi zbioru $A$ muszą różnić się na co najmniej jednej z początkowych $n - 2$ pozycji. Wobec tego liczba
ciągów w tym zbiorze nie przekracza liczby wszystkich ciągów $(n-2)$ -wyrazowych o wyrazach ze zbioru $p$ -elementowego, czyli
liczby $p^{n-2}$ .

Skonstruujemy $p^{n-2}$ ciągów o wyrazach ze zbioru $S = \{0,1,2,\dots ,p-1\}$ mających postulowaną własność.
W tym celu rozpatrzmy wszystkie ciągi $(x_1,x_2,\dots ,x_n)$ o wyrazach ze zbioru $S$ spełniające warunki

$ (1) \qquad x_{n-1} \equiv \sum_{i=1}^{n-2} x_i (\mod p) \text{ oraz } x_n \equiv \sum_{i=1}^{n-2} i x_i (\mod p). $

Ciągów takich jest $p^{n-2}$ , ponieważ każdy ciąg ( $(x_1,x_2,\dots ,x_{n-2})$ o wyrazach ze zbioru $p$ -elementowego $S$
wyznacza jednoznacznie wartości $x_{n-1}$ i $x_n$ .

Każde dwa różne ciągi spełniające zależności (1) różnią się na co najmniej jednej z początkowych $n - 2$ pozycji.
Chcemy zaś dowieść, że każde dwa takie ciągi $(x_1,x_2,\dots ,x_n)$ oraz $(y_1,y_2,\dots ,y_n)$ różnią się na co najmniej
trzech pozycjach.

Jeśli ciągi te różnią się na co najmniej trzech miejscach o numerach $1,2,\dots ,n-2$ , to nie ma czego dowodzić. Pozostaje zatem rozpatrzeć następujące dwa przypadki.

Odcinki początkowe $(x_1,x_2,\dots ,x_{n-2})$ oraz $(y_1,y_2,\dots ,y_{n-2})$ różnią się na dokładnie dwóch pozycjach
o numerach $i$ , $j$ ( $1 \leq i < j \leq n-2$ ).

Wtedy $x_i \neq y_i$ oraz $x_j = y_j$ . Z zależności (1) otrzymujemy

$ \begin{cases} x_{n-1} - y_{n-1} &\equiv (x_i - y_i)+(x_j - y_j) (\mod p) \\ x_n - y_n &\equiv i(x_i -y_i)+j(x_j -y_j) (\mod p). \end{cases} $

Stąd $(x_n - y_n)-i(x_{n-1} - y_{n-1}) \equiv (j -i)(x_j -y_j) (\mod p)$ .

Liczba $p$ jest pierwsza, a liczby $x_j$ i $y_j$ są różne i należą do zbioru $S$ . Ponadto $1 \leq j -i <n \leq p$ .
Stąd wynika, że liczba $(x_n - y_n)-i(x_{n-1} - y_{n-1})$ nie jest podzielna przez $p$ . Zatem któraś z liczb
$x_{n-1} - y_{n-1}$ lub $x_n - y_n$ nie jest podzielna przez $p$ . Wobec tego $x_{n-1}\neq y_{n-1}$ lub $x_n \neq y_n$ .
Rozpatrywane ciągi różnią się więc na pozycji o numerze $n-1$ lub $n$ , czyli łącznie na co najmniej trzech pozycjach.
Odcinki początkowe $(x_1,x_2,\dots ,x_{n-2})$ oraz $(y_1,y_2,\dots,y_{n-2})$ różnią się na dokładnie jednej pozycji
o numerze $i$ ( $1 \leq i \leq n-2$ ).

Wtedy $x_i \neq y_i$ i podobnie korzystając z zależności (1) mamy

$ \begin{cases} x_{n-1} - y_{n-1} &\equiv x_i - y_i (\mod p) \\ x_n - y_n \equiv i(x_i - y_i) (\mod p) \end{cases} $

Stąd wynika, że liczby $x_{n-1} - y_{n-1}$ oraz $x_n - y_n$ nie są podzielne przez $p$ . Zatem $x_{n-1} \neq y_{n-1}$
oraz $x_n =y_n$ , czyli i w tym przypadku rozpatrywane ciągi różnią się na co najmniej trzech pozycjach.