Track / Stage 6 / 18 of 400 #1018 of 2000

Problem 1018

National olympiad, first round

Number theory Difficulty 6.0 Prove it

1. For a natural number $n$ , let $x_{n}$ denote the number obtained by consecutively writing all natural numbers from 1 to $n$ one after another (e.g., $x_{14}=$ 1234567891011121314). Let the function $f: \mathbb{N} \rightarrow \mathbb{N}_{0}$ be defined as follows: $f(n)$ is the smallest number of digits that need to be removed from the representation of the number $x_{n}$ so that the newly obtained number is divisible by 8 (it is allowed to remove all digits of $x_{n}$ , in which case the newly obtained number is considered to be zero). Do there exist natural numbers $t$ and $n_{0}$ such that for all $n \in \mathbb{N}, n \geqslant n_{0}$ , it holds that $f(n+t)=f(n) ?$

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

1. Suppose such numbers $t$ and $n_{0}$ exist. Then the set of all possible values that the function $f$ can take is clearly equal to $\{f(n): 1 \leqslant$ $\left.n \leqslant n_{0}+t-1\right\}$ . Since this set is finite, it has a maximum element; let this be $M$ . Now let $k$ be an arbitrary natural number whose decimal representation ends with $M+1$ ones. Then the number $x_{k}$ also ends with $M+1$ ones, so for it to be even (and especially divisible by 8), we must remove all those $M+1$ ones from the end of its decimal representation. Therefore, $f(k) \geqslant M+1$ , i.e., the function $f$ takes a value greater than $M$ , a contradiction.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.