III MEMO - Zadanie 7

Zawody matematyczne:

III MEMO, 2009

Na tablicy napisano liczby $0,1,2,\dots,n$ ( $n\geq2$ ). W każdym kroku wymazujemy liczbę będącą średnią arytmetyczną dwóch różnych, jeszcze nie wymazanych liczb. Postępowanie to kontynuujemy tak długo, jak jest to możliwe. Niech $g(n)$ będzie najmniejszą możliwą ilością liczb pozostawionych na tablicy. Wyznaczyć $g(n)$ w zależności od $n$ .

Rozwiązanie

Zacznijmy od obserwacji, że $g(n)\geq2$ , bo nie możemy zostawić na tablicy mniej, niż 2 liczb. Ponadto jeśli $g(n)=2$ , to liczbami pozostałymi na końcu są 0 i $n$ .

Dla $n=2^k$ , gdzie $k$ jest liczbą naturalną, możemy kolejno usuwać liczby postaci $2m+1=\frac{2m+2(m+1)}{2}$ , potem wszystkie postaci $4m+2=\frac{4m+4(m+1)}{2}$ , następnie $8m+4=\frac{8m+8(m+1)}{2}$ , itd., tak długo, aż na tablicy pozostaną jedynie 0 i $n=2^k$ . Zatem $g(2^k)\geq2$ i wobec wcześniejszej uwagi $g(2^k)=2$ .

Załóżmy teraz, że $n$ nie jest potęgą 2. Przypuśćmy, że $g(n)=2$ , tzn. istnieje pewien sposób usuwania liczb, przy którym na końcu zostaje tylko 0 i $n$ . Przeanalizujemy tę procedurę od końca, zaczynając od 0 i $n$ na tablicy i dopisując w każdym kolejnym kroku nową liczbę, będącą średnią arytmetyczną pewnych dwóch liczb, będących w tym momencie na tablicy.

W pierwszym kroku musimy dopisać $\frac{n+0}{2}=\frac{n}{2}$ . W drugim mamy dwie możliwości: $\frac{n+n/2}{2}=\frac{3n}{2^2}$ i $\frac{0+n/2}{2}=\frac{n}{2^2}$ . Nietrudno zauważyć, że w $k$ -tym kroku możliwa do napisania jest jedna z liczb postaci $t\cdot\frac{n}{2^k}$ dla pewnego $t\geq 1$ .

Istotnie, zakładając indukcyjnie, że po $k-1$ krokach ( $k\geq2$ ) wszystkie liczby na tablicy są postaci $t'\cdot\frac{n}{2^{k-1}}$ dla pewnego $t'\geq0$ , w $k$ -tym kroku możemy dopisać jedynie liczbę postaci $\left.\left(t_1\cdot\frac{n}{2^{k-1}}+t_2\cdot\frac{n}{2^{k-1}}\right)\right/2=t\cdot\frac{n}{2^k}$ dla pewnego $t\geq1$ , po czym wszystkie liczby na tablicy są całkowitymi wielokrotnościami liczby $\frac{n}{2^k}$ .

Zauważmy, że 1 nie można przedstawić jako $t\cdot\frac{n}{2^k}$ , więc nigdy nie zostanie dopisana. Wracając do procedury usuwania, odpowiadającej analizowanej procedurze dopisywania liczb, wnioskujemy, że na końcu zostały nie usunięte liczby 0, 1 i $n$ . Stąd $g(n)\geq3$ . Otrzymana sprzeczność z założeniem $g(n)=2$ dowodzi, że każda procedura usuwania liczb z tablicy musi się skończyć pozostawieniem przynajmniej 3 liczb.

Uzasadnimy, że pozostawienie dokładnie 3 liczb na tablicy jest możliwe. Niech $k$ będzie liczbą całkowitą, dla której $2^k<n<2^{k+1}$ . W pierwszym etapie usuwamy kolejno $n-1$ , $n-2,\dots, 2^{k}+1$ . Jest to możliwe, bo jeżeli $m>2^k$ i usunęliśmy $n-1,n-2,\dots m+1$ , to $m$ jest średnią arytmetyczną liczb $n$ i $2m-n$ , a przy tym $2m-n>2^{m+1}-n>0$ oraz $2m-n<m$ , więc obie liczby $n$ i $2m-n$ są w tym momencie obecne na tablicy.

Po pierwszym etapie pozostały na tablicy liczby $0,1,\dots,2^k$ i $n$ . Teraz usuwamy liczby z ciągu $0,1,\dots,2^k$ , w sposób opisany w pierwszej części rozwiązania, dzięki któremu na końcu pozostają tylko dwie liczby: 0 i $2^k$ . Tym samym pozostawiamy na tablicy jedynie liczby 0, $2^k$ i $n$ .

Udowodniliśmy zatem, że $g(n)=2$ , gdy $n$ jest potęgą 2, zaś w przeciwnym wypadku $g(n)=3$ .