Virknē augošā kārtībā izrakstīti naturālie skaitļi no \(1\) līdz \(2004\) ieskaitot, katrs vienu reizi. Izsvītrojam no tās skaitļus, kas atrodas \(1.,\ 4.,\ 7.,\ 10.,\ \ldots\) vietās. No palikušās virknes atkal izsvītrojam skaitļus, kas tajā atrodas \(1.,\ 4.,\ 7.,\ \ldots\) vietās. Ar iegūto virkni rīkojamies tāpat, utt., kamēr paliek neizsvītrots viens skaitlis. Kurš tas ir?
Apzīmēsim skaitli, kas ir pirmais neizsvītrotais pēc \(n\) svītrošanas sērijām, ar \(x_{n}(n=0;\ 1;\ 2;\ \ldots\). Viegli pārbaudīt, ka \(x_{0}=1;\ x_{1}=2;\ x_{2}=3;\ x_{3}=5;\ x_{4}=8\).
Pretēji domai par Fibonači skaitļiem pierādīsim, ka
\[(*)\ x_{n+1}=\left\{\begin{array}{l} \frac{3}{2} x_{n}, \text { ja } x_{n}-\text { pāra skaitlis, } \\ \frac{3}{2} x_{n}, \text { ja } x_{n}-\text { nepāra skaitlis } \end{array}\right.\]
Tiešām, pieņemsim, ka \(x_{n}=2m,\ m \in N\). Apskatām skaitli \(3m\). Ir \(m\) skaitļi, kas mazāki par \(3m\) un dod atlikumu \(1\), dalot ar \(3\). Tāpēc pēc pirmās svītrošanu sērijas \(3m\) atradīsies \(2m\)-jā vietā; tātad vēl pēc \(n\) sērijām tas būs pirmajā vietā. Tagad pieņemam, ka \(x_{n}=2m+1,\ m=0;\ 1;\ \ldots\). Apskatām skaitli \(\frac{3}{2}(2m+1)+\frac{1}{2}=3m+2\). Pēc pirmās svītrošanu sērijas, kurā izsvītros \(m+1\) par to mazākus skaitļus, šis skaitlis atradīsies \(2m+1\)-ā vietā; tātad vēl pēc \(n\) sērijām tas būs pirmajā vietā. Sakarība (*) pierādīta. Tagad pakāpeniski iegūstam \(x_{i}\) vērtības \(1;\ 2;\ 3;\ 5;\ 8;\ 12;\ 18;\ 27;\ 41;\ 62;\ 93;\ 140;\ 210\); \(315;\ 473;\ 710;\ 1065;\ 1598\). Nākošais loceklis jau būtu lielāks par \(2004\), tāpēc uzdevuma atbilde ir \(1598\). *Piezīme:* Pirms pēdējās izsvītrošanas pēdējais skaitlis bija `#2`, pirms tam `#3`, `#5`, `#8`, `#12`, utt. Pēc \(n\) svītrošanām pirmais palikušais ir \(x_n\). Pamato \(x_{n+1} = \left\lceil 3x_n/2 \right\rceil\) pāru un nepāru \(x_n\).