Library / /13 of 17

, 2014

Combinatorics Difficulty 6.7 National olympiad Prove it Canada

Fix positive integers $n$ and $k \ge 2$ . A list of $n$ integers is written in a row on a blackboard. You can choose a contiguous block of integers, and I will either add 1 to all of them or subtract 1 from all of them. You can repeat this step as often as you like, possibly adapting your selections based on what I do. Prove that after a finite number of steps, you can reach a state where at least $n-k+2$ of the numbers on the blackboard are all simultaneously divisible by $k$ .

Solution

We will think of all numbers as being residues mod $k$ . Consider the following strategy:

* If there are less than $k-1$ non-zero numbers, then stop.
* If the first number is 0, then recursively solve on the remaining numbers.
* If the first number is $j$ with $0 < j < k$ , then choose the interval stretching from the first number to the $j$ th-last non-zero number.

First note that this strategy is indeed well defined. The first number must have value between 0 and $k-1$ , and if we do not stop immediately, then there are at least $k-1$ non-zero numbers, and hence the third step can be performed.

For each $j$ with $1 \le j \le k-2$ , we claim the first number can take on the value of $j$ at most a finite number of times without taking on the value of $j-1$ in between. If this were to fail, then every time the first number became $j$ , I would have to add 1 to the selected numbers to avoid making it $j-1$ . This will always increase the $j$ -th last non-zero number, and that number will never be changed by other steps. Therefore, that number would eventually become 0, and the next last non-zero number would eventually become zero, and so on, until the first number itself becomes the $j$ -th last non-zero number, at which point we are done since $j \le k-2$ .

Rephrasing slightly, if $1 \le j \le k-2$ , the first number can take on the value of $j$ at most a finite number of times between each time it takes on the value of $j-1$ . It then immediately follows that if the first number can take on the value of $j-1$ at most a finite number of times, then it can also only take on the value of $j$ a finite number of times. However, if it ever takes on the value of 0, we have already reduced the problem to $n-1$ , so we can assume that never happens. It then follows that the first number can take on all the values $0, 1, 2, \dots, k-2$ at most a finite number of times.

Finally, every time the first number takes on the value of $k-1$ , it must subsequently take on the value of $k-2$ or 0, and so that can also happen only finitely many times.

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.