Let be a positive integer. There are 101 numbers written in a row:
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?
, 2023
Solution
The answer is .
Indeed, the main claim is that is larger than if and only if there is a number divisible by between and . Denote by the remainder of when divided by . Note that , otherwise , a contradiction. Put and . Thus
Since , it is easy to check that or .
* If then and between and , there does not exist any multiple of .
* If then and between and , the number is a unique multiple of .
So all we are left with is calculating the quantity of non-zero numbers divisible by between and . This quantity is .
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.