Komentarz

III MEMO - Zadanie 7

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

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

Dodaj komentarz