Gleb picked positive integers $N$ and $a$ ($a < N$). He wrote the number $a$ on a blackboard. Then each turn he did the following: he took the last number on the blackboard, divided the number $N$ by this last number with remainder and wrote the remainder onto the board. When he wrote the number $0$ onto the board, he stopped. Could he pick $N$ and $a$ such that the sum of the numbers on the blackboard would become greater than $100N$ ? Ivan Mitrofanov
Problem
Source: Tournament of Towns, Junior A-Level Paper, Spring 2020 , p7
Tags: combinatorics, game, remainder
10.06.2020 20:43
We claim that the answer is actually $\boxed{YES}.$ Consider the function $f : [0, 1] \rightarrow [0, 1]$ defined by $f(x) = 1 - x \cdot \left \lfloor \frac1{x} \right \rfloor.$ We claim that for any positive integer $z \in \mathbb{N}$, there exists a real number $x \in (\frac12, 1)$ so that $f^{(k)}(t) \in \left(\frac1{t+2}, \frac1{t+1} \right)$ for any real number $t$ sufficiently close to $x$, where $f^{(k)} (t)$ denotes the iterated application of $f.$ Proving this is rather straightforward. Let the interval $\left(\frac{1}{t+2}, \frac{1}{t+1} \right)$ be denoted by $I_t$ for any $t \in \mathbb{Z}_{\ge 0}.$ Start with the interval $I_z$, then consider the subset of interval $I_{z-1}$ which maps to $I_z.$ Then consider the subset of $I_{z-2}$ which maps to the previously obtained subset of $I_{z-1}$. Continuing in this fashion, we obtain a subinterval $I$ of values in $I_0$ such that for any $r \in I$, $f^{(k)} (r) \in I_k$ for all $0 \le k \le z.$ With this in mind, we can begin the construction. Select some arbitrarily large positive integer $t$ such that $\frac11 + \frac12 + \cdots + \frac1{t} > 1000.$ From the above, consider an interval $I \subset I_0$ so that whenever $x \in I,$ $f^{(k)} (x) \in I_k$ for any $0 \le k \le t.$ Since this interval has nonzero length, it contains a rational number, say $\frac{p}{q}.$ Now the construction is simple. Let $N = t! \cdot q$ and $a = \frac{p}{q} \cdot N.$ It's easy to check that the $(k+1)-$th number written on the blackboard is $f^{(k)} \left(\frac{p}{q} \right) \cdot N$, for all $0 \le k \le t$. The sum of the first $t+1$ numbers written on the blackboard would then be greater than $N \cdot \left(\frac12 + \frac13 + \cdots + \frac1{t+2}\right) > 998N.$ This concludes the solution. $\square$
09.12.2020 02:25
We show more generally that for any $M$ a choice of $N$ and $a$ can be made so that the the sum exceeds $MN$. Let $M\in\mathbb{N}$. Since we know the harmonic series diverges, there exists $L=L(M)\in\mathbb{N}$ such that $$\sum_{n=1}^{L(M)+1}\frac{1}{n}>M.$$Define $x_L$ to be any rational number in the interval $(\frac{1}{L+1},\frac{1}{L})$. Define $x_1,\dots,x_{L-1}$ by $$x_{n-1}=\frac{1-x_n}{n-1}$$for all $2\leq n\leq L$. We see that $x_1,\dots, x_L$ are all clearly rational and will show with induction they satisfy $$\frac{1}{n+1}<x_n<\frac{1}{n}$$for $1\leq n\leq L$. We can see this by induction as follows: Take $n=L$ as the base case which is true by definition of $x_L$, for lower indices by assuming true $x_n$ and proving for $x_{n-1}$ $$\frac{1}{n+1}<x_n<\frac{1}{n}$$$$\frac{n-1}{n}<1-x_n<\frac{n}{n+1}$$$$\frac{1}{n}<\frac{1-x_n}{n-1}<\frac{n}{n+1}\frac{1}{n-1}$$$$\frac{1}{n}<\frac{1-x_n}{n-1}<\frac{1}{n-1}$$\ $$\frac{1}{n}<x_{n-1}<\frac{1}{n-1}.$$Now write $x_n=\frac{a_n}{b_n}$ for $a_n,b_n\in\mathbb{N}$. Now let $$N=\prod_{n=1}^L b_n \qquad a=Nx_1.$$Note $a<N$ and we now show the next numbers written on the board are $Nx_n$ for all $2\leq n\leq L$ (note these are decreasing using the bounds found). By definition of $x_{n-1}$ $$1=x_{n-1}(n-1)+x_n,$$multiply by $N$ $$N=Nx_{n-1}(n-1)+Nx_n$$for $2\leq n\leq L$. Therefore the sum of all the remainders exceeds $$N+\sum_{n=1}^L Nx_n> N \sum_{n=1}^{L+1} \frac{1}{n}> MN.$$ Remark: When one gets into this problem it becomes clear that taking rational approximations will work but what is surprising is that approximations do not seem to be necessary.