Maths Olympiad Prep

Library / /16 of 30

, 2023

Number theory Difficulty 8.1 Shortlist Prove it Saudi Arabia

Let n100n \le 100 be a positive integer. There are 101 numbers written in a row:
0n mod 101,1n mod 101,,100n mod 101. 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 n1n-1.

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

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

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

n1\boxed{n-1}

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

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.