LVII OM - I - Zadanie 4

Uczestnicy zawodów matematycznych rozwiązywali sześć zadań, każde oceniane jedną z ocen 6, 5, 2, 0. Okazało się, że
dla każdej pary uczestników $ A, B $ można wskazać takie dwa zadania, że w każdym z nich $ A $ uzyskał inną ocenę niż $ B $.

Wyznaczyć największą liczbę uczestników, dla której taka sytuacja jest możliwa.

Rozwiązanie

Wykażemy, że największą liczbą uczestników, dla której taka sytuacja jest możliwa, jest 1024. W dalszym ciągu przyjmiemy, że dopuszczalnymi ocenami są liczby 0, 1, 2, 3 (zamiast 5 punktów stawiamy 4, a następnie każdą ocenę dzielimy przez 2).

Niech $ P = \{0,1,2,3\} $ i rozważmy zbiór

\[<br /> X = \{(a_1,a_2,\dots ,a_6) \;:\; a_1,a_2,\dots ,a_6 \in P \}.<br /> \]

Zbiór $ X $ ma oczywiście 4096 elementów. Będziemy rozważać podzbiory $ A $ zbioru $ X $ o następującej własności (*):

(*) jeśli $ (a_1,a_2,\dots,a_6) $, $ (b_1,b_2,\dots,b_6) \in A $ to istnieją i,j takie, że

\[<br /> 1 \leq i,j \leq 6,\quad i \neq j,\quad \text{oraz}\quad a_i \neq b_i,\;a_j \neq b_j.<br /> \]

Wystarczy pokazać, że największa liczba elementów zbioru $ A $ o własności (*) wynosi 1024.

Najpierw pokazujemy, że jeśli zbiór $ A $ ma własność (*), to ma co najwyżej 1024 elementy. Załóżmy zatem, że mamy dany podzbiór
$ A $ zbioru $ X $ mający własność (*) i przypuśćmy, że ma on co najmjniej 1025 elementów. Ponieważ istnieją dokładnie 1024 ciągi
długości 5 o wyrazach ze zbioru czteroelementowego $ P $, więc z zasady szufladkowej Dirichleta wynika, że w zbiorze $ A $ istnieją
co najmniej dwa ciągi, mające te same wyrazy od pierwszego do piątego. Te ciągi różnią się więc tylko jednym wyrazem – szóstym,
co jest sprzeczne z własnością (*). Zatem zbiór $ A $ ma co najwyżej 1024 elementy.

Teraz pokazujemy, że istnieje zbiór A mający co najmniej 1024 elementy i mający własność (*). Wystarczy mianowicie wziąć następujący zbiór:

\[<br /> A = \{(a_1,a_2,\dots,a_6) \in X \;:\; 4 | a_1 +a_2 +\dots+a_6\}.<br /> \]

Najpierw pokazujemy, że zbiór $ A $ ma co najmniej 1024 elementy. Weźmy dowolne liczby $ a_1,a_2,\dots,a_5 \in P $. Takiego
wyboru możemy dokonać na 1024 sposoby. Niech $ r $ będzie resztą z dzielenia przez 4 sumy $ a_1+a_2+\dots+a_5 $ i przyjmijmy
$ a_6 =4 - r $. Wtedy oczywiście $ (a_1,a_2,\dots,a_6) \in A $, a więc wskazaliśmy w zbiorze $ A $ co najmniej 1024 różne ciągi.
Wreszcie pokazujemy, że zbiór $ A $ ma własność (*). Przypuśćmy, że

\[<br /> (a_1,a_2,\dots,a_6),\; (b_1,b_2,\dots,b_6) \in A<br /> \]

oraz ciągi $ (a_1,a_2,\dots,a_6) $ i $ (b_1,b_2,\dots,b_6) $ różnią się tylko jednym wyrazem, np. wyrazem o indeksie $ k:\;a_k \neq b_k $, gdzie $ 1 \leq k \leq 6 $
oraz $ a_i = b_i $ dla $ i\neq k $. Ponieważ liczby $ a_1 +a_2 +\dots +a_6 $ i $ b_1 +b_2 +\dots+b_6 $ są podzielne przez 4, więc ich
różnica też jest podzielna przez 4. Ale

\[<br /> (a_1 + a_2 +\dots +a_6)-(b_1 +b_2 +\dots +b_6)= a_k -b_k.<br /> \]

Zatem liczba $ a_k - b_k $ jest podzielna przez 4. Ponieważ $ a_k,b_k \in P $ , więc

\[<br /> a_k - b_k \in \{-3,-2,-1,0,1,2,3\}.<br /> \]

W zbiorze $ \{-3,-2, -1,0,1,2,3\} $ jest tylko jedna liczba podzielna przez 4, mianowicie 0. Zatem $ a_k = b_k $, wbrew założeniu,
że ciągi $ (a_1,a_2,\dots,a_6) $ oraz $ (b_1,b_2,\dots,b_6) $ różnią się wyrazem o indeksie $ k $. Ta sprzeczność dowodzi, że zbiór
$ A $ ma własność (*), co kończy dowód.

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

Komentarze

Dodaj nową odpowiedź