I MEMO - Zadanie 2

Rozważamy zbiór $n$ kul ponumerowanych liczbami $1, 2, 3, \ldots, n$ . Danych jest $k>1$ takich zbiorów kul. Chcemy pokolorować wszystkie kule dwoma kolorami, białym i czarnym, tak aby

kule oznaczone tym samym numerem były tego samego koloru;
dowolny podzbiór $k+1$ kul z (niekoniecznie różnymi)
numerami $a_1$ , $a_2$ , $\ldots$ , $a_{k+1}$ spełniającymi
warunek

$ a_1+a_2+\ldots+a_k=a_{k+1} $

musiał zawierać co najmniej jedną kulę każdego koloru.

Dla każdego $k$ znaleźć największe możliwe $n$ , dla którego istnieje pokolorowanie spełniające powyższe warunki.

Rozwiązanie

Dla ustalenia uwagi przyjmijmy, że kule oznaczone numerem 1 są białe. Rozpatrzymy dwa przypadki:

1. Kule z numerem 2 są czarne.

Na mocy warunku b) kule z numerem $1+1+\ldots+1=k$ są czarne oraz kule z numerem $2+2+\ldots+2=2k$ są białe. Skoro kule z numerami 1 i $2k$ są białe, zależność

$ (k+1)+\underbrace{1+\ldots+1}_{k-1}=2k $

wskazuje, że kule z numerami $k+1$ są czarne.

Jednakże kule z numerami $2k$ i 1 są wówczas białe, zaś kule z numerami $k+1$ i 2 są czarne. Wobec równości

$ 2k+\underbrace{1+\ldots+1}_{k-1}=(k+1)+\underbrace{2+\ldots+2}_{k-1}=3k-1 $

niezależnie od koloru kul z numerem $3k-1$ dochodzimy do sprzeczności z warunkiem b), jeżeli $n\ge 3k-1$ . Zatem w tym przypadku mamy $n\le 3k-2$ .

2. Kule z numerem 2 są białe.

Dowolna liczba całkowita z przedziału $\langle k; 2k\rangle$ może być przedstawiona w postaci sumy $k$ liczb, z których każda jest równa 1 lub 2. Skoro kule z numerami 1 i 2 są białe, na podstawie warunku b) kule z numerami $k$ , $k+1$ , $\ldots$ , $2k$ są czarne. W takim razie kule z numerem $k+k+\ldots+k=k^2$ są białe. Kule z numerami $k$ i $k+1$ są czarne, zaś kule z numerami 1 i $k^2$ - białe. Wobec tego równości

$ k+\underbrace{(k+1)+(k+1)+\ldots+(k+1)}_{k-1}= k^2+\underbrace{1+1+\ldots+1}_{k-1}=k^2+k-1 $

dowodzą, że dla obu możliwych kolorów kul z numerem $k^2+k-1$ otrzymujemy sprzeczność z warunkiem b), o ile $n\ge k^2+k-1$ . Musi więc zachodzić nierówność $n\le k^2+k-2$ .

Zatem liczba $n$ nie przekracza większej z liczb $3k-2$ i $k^2+k-2$ . Jednakże dla $k\ge 2$ mamy $k^2+k-2\ge 3k-2$ i w efekcie $n\le k^2+k-2$ .

Wykażemy, że dla $n=k^2+k-2$ istnieje pokolorowanie kul spełniające żądane warunki. Weźmy mianowicie pod uwagę następujące pokolorowanie:

$ \begin{split} \hbox{numery kul białych:}\quad & 1,\,2,\,\ldots,\,k-2,\,k-1,\,k^2,\,k^2+1,\,\ldots,\,k^2+k-2, \\ \hbox{numery kul czarnych:}\quad & k,\,k+1,\,k+2,\ldots,\,k^2-2,\,k^2-1. \\ \end{split} $

Pokolorowanie to spełnia warunek b) dany w treści zadania. Rzeczywiście, jeżeli rozpatrzymy $k$ kul czarnych, to numer każdej z nich jest nie mniejszy niż $k$ i wobec tego suma tych numerów jest nie mniejsza niż $k^2$ , zaś kula o takim numerze jest biała. Niech z kolei $a_1$ , $a_2$ , $\ldots$ , $a_k$ będą numerami białych kul. Mamy udowodnić, że jeżeli $s=a_1+a_2+\ldots+a_k\le k^2+k-2$ , to kule o numerze $s$ są czarne. Jeśli liczby $a_1$ , $a_2$ , $\ldots$ , $a_k$ są mniejsze niż $k$ , to liczba $s$ leży w przedziale $\langle k; k^2-k\rangle$ , jeśli natomiast jedna z liczb $a_1$ , $a_2$ , $\ldots$ , $a_k$ jest nie mniejsza niż $k^2$ , to $s\ge k^2+k-1$ . To kończy dowód faktu, że rozpatrywane pokolorowanie ma żądane własności.