Library / SAUDI ARABIAN IMO Booklet /13 of 25

SAUDI ARABIAN IMO Booklet, 2023

Number theory Difficulty 8.1 Shortlist Prove it Saudi Arabia

Let $n \le 100$ be a positive integer. There are 101 numbers written in a row:
$0 \cdot n \text{ mod } 101, 1 \cdot n \text{ mod } 101, \dots, 100 \cdot n \text{ mod } 101.$
How many pairs of neighbouring numbers are there in this row such that the one on the left is bigger than the one on the right?

Solution

The answer is $n-1$ .

Indeed, the main claim is that $an \bmod 101$ is larger than $(a+1)n \bmod 101$ if and only if there is a number divisible by $101$ between $an$ and $(a+1)n$ . Denote by $f(x)$ the remainder of $x$ when divided by $101$ . Note that $f(an) \ne f((a+1)n)$ , otherwise $101 \mid n$ , a contradiction. Put $an = 101k + f(an)$ and $(a+1)n = 101k' + f((a+1)n)$ . Thus
$n = (a + 1)n - an = 101(k' - k) + f((a + 1)n) - f(an).$
Since $-101 < f((a+1)n) - f(an) < 101$ , it is easy to check that $k' - k = 0$ or $1$ .

* If $f(an) < f((a+1)n)$ then $k = k'$ and between $an$ and $(a+1)n$ , there does not exist any multiple of $101$ .
* If $f(an) > f((a+1)n)$ then $k' = k + 1$ and between $an$ and $(a+1)n$ , the number $101k'$ is a unique multiple of $101$ .

So all we are left with is calculating the quantity of non-zero numbers divisible by $101$ between $0$ and $100 \cdot n$ . This quantity is $\lfloor 100n/101 \rfloor = n - 1$ .

$\boxed{n-1}$

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.