LVII OM - II - Zadanie 6

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

\[<br /> x_k\neq y_k,\quad x_l\neq y_l,\quad x_m\neq y_m.<br /> \]

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

\[<br /> (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).<br /> \]

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.

  1. 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

    \[<br /> \begin{cases}<br /> x_{n-1} - y_{n-1} &\equiv (x_i - y_i)+(x_j - y_j) (\mod p) \\<br /> x_n - y_n &\equiv i(x_i -y_i)+j(x_j -y_j) (\mod p).<br /> \end{cases}<br /> \]

    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.

  2. 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

    \[<br /> \begin{cases}<br /> x_{n-1} - y_{n-1} &\equiv x_i - y_i (\mod p) \\<br /> x_n - y_n \equiv i(x_i - y_i) (\mod p)<br /> \end{cases}<br /> \]

    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.

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

Komentarze

Dodaj nową odpowiedź