LVII OM - I - Zadanie 4

Zawody matematyczne:

LVII OM, 2005-2006

Etap:

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

$ X = \{(a_1,a_2,\dots ,a_6) \;:\; a_1,a_2,\dots ,a_6 \in P \}. $

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

$ 1 \leq i,j \leq 6,\quad i \neq j,\quad \text{oraz}\quad a_i \neq b_i,\;a_j \neq b_j. $

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:

$ A = \{(a_1,a_2,\dots,a_6) \in X \;:\; 4 | a_1 +a_2 +\dots+a_6\}. $

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

$ (a_1,a_2,\dots,a_6),\; (b_1,b_2,\dots,b_6) \in A $

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

$ (a_1 + a_2 +\dots +a_6)-(b_1 +b_2 +\dots +b_6)= a_k -b_k. $

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

$ a_k - b_k \in \{-3,-2,-1,0,1,2,3\}. $

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.