Browse · MathNet
PrintKanada 2014
Canada 2014 counting and probability
Problem
Fix positive integers and . A list of 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 of the numbers on the blackboard are all simultaneously divisible by .
Solution
We will think of all numbers as being residues mod . Consider the following strategy:
If there are less than non-zero numbers, then stop. If the first number is 0, then recursively solve on the remaining numbers. * If the first number is with , then choose the interval stretching from the first number to the th-last non-zero number.
First note that this strategy is indeed well defined. The first number must have value between 0 and , and if we do not stop immediately, then there are at least non-zero numbers, and hence the third step can be performed.
For each with , we claim the first number can take on the value of at most a finite number of times without taking on the value of in between. If this were to fail, then every time the first number became , I would have to add 1 to the selected numbers to avoid making it . This will always increase the -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 -th last non-zero number, at which point we are done since .
Rephrasing slightly, if , the first number can take on the value of at most a finite number of times between each time it takes on the value of . It then immediately follows that if the first number can take on the value of at most a finite number of times, then it can also only take on the value of a finite number of times. However, if it ever takes on the value of 0, we have already reduced the problem to , so we can assume that never happens. It then follows that the first number can take on all the values at most a finite number of times.
Finally, every time the first number takes on the value of , it must subsequently take on the value of or 0, and so that can also happen only finitely many times.
If there are less than non-zero numbers, then stop. If the first number is 0, then recursively solve on the remaining numbers. * If the first number is with , then choose the interval stretching from the first number to the th-last non-zero number.
First note that this strategy is indeed well defined. The first number must have value between 0 and , and if we do not stop immediately, then there are at least non-zero numbers, and hence the third step can be performed.
For each with , we claim the first number can take on the value of at most a finite number of times without taking on the value of in between. If this were to fail, then every time the first number became , I would have to add 1 to the selected numbers to avoid making it . This will always increase the -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 -th last non-zero number, at which point we are done since .
Rephrasing slightly, if , the first number can take on the value of at most a finite number of times between each time it takes on the value of . It then immediately follows that if the first number can take on the value of at most a finite number of times, then it can also only take on the value of a finite number of times. However, if it ever takes on the value of 0, we have already reduced the problem to , so we can assume that never happens. It then follows that the first number can take on all the values at most a finite number of times.
Finally, every time the first number takes on the value of , it must subsequently take on the value of or 0, and so that can also happen only finitely many times.
Techniques
Invariants / monovariantsGames / greedy algorithmsRecursion, bijectionModular Arithmetic