Zbiór zadań, (zadania różne)
Zadanie 245
Liczby naturalne od 1 do 2012 ustawiono w porządku rosnącym na okręgu. Następnie rozpoczęto proces skreślania co drugiej nieskreślonej liczby, startując od 1 (pierwsza skreślona liczba to 2). W rezultacie tej procedury skreślania pozostanie jedna liczba. Jaka?
Rozwiązanie
Dla $n = 2^k$ liczbą tą będzie 1. Po pierwszym przejściu zostanie skreślonych $2^{k-1}$ liczb, ostatnią skreśloną liczbą będzie $2^k$. Pozostanie $2^{k-1}$ liczb (parzysta ilość). W każdym następnym przejściu sytuacja powtarza się, więc ostatnią nieskreśloną liczbą dla liczby będącej potęgą dwójki będzie 1.
Niech $n = 2^k + r$, gdzie $2^{k-1} < r < 2^k$. Po skreśleniu r liczb, pozostanie na okręgu $n = 2^k$ liczb, przy czym pierwszą liczbą będzie $2r + 1$, to ona właśnie zostanie nieskreślona.
Dla $n = 2012$ otrzymujemy $2012 = 1024 + 988$,
$r = 988$,
$2r + 1 = 988 \cdot 2 + 1 = 1977$
powrót do zbioru zadań | wersja do druku << poprzednie zadanie następne zadanie >>