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$.
Problem
Source: 2014 CMO #5
Tags: number theory proposed, number theory, Operation
02.08.2014 16:25
This was a really hard problem in my opinion. It took two whole days for the Korean IMO team to solve it. To avoid confusion, let $A$ be the one who choses the block and $B$ be the one who either add or subtract $1$. We shall prove the following claim. Claim. Let $n$, $k$, $t$ be three given positive integers such that $n \ge k-2 \ge 0$. Initially, a list of $n$ integers $a_1 , a_2 , \cdots, a_n $ is written in a row on a blackboard where $0 < a_1 < k$. Whatever $B$ does, $A$ can always make in finite time a state where $a_1 = 0$ or $a_1 = k$ or there exist at least $n-k+2$ multiples of $t$ among $a_2, \cdots, a_n$. Proof. We prove that if $B$ never let $a_1=0$ or $a_1=k$, then we can make at least $n-k+2$ multiples of $t$ by induction on $(k,n)$ in lexicographical order. $(i)$ $k-2$ Since $a_1= 1$, Cinderella may choose only $a_1$ to force the Stepmother to make $a_1=0$ or $a_1 = 2$. $(ii)$ $n=k-2$ There exists at lest $n-k+2 = 0$ multiples of $t$ among $a_2, \cdots, a_n$. $(iii)$ Assume that the statement is true for $k-1$ or for $(k,n-1)$ where $k \ge 3$ and $n \ge k-1$. $A$ will use the following strategy. $A$ first assumes that $B$ will never let $a_1=0$ or $a_1 = k-1$ and apply the strategy used for $(k-1,n-1)$ on $a_1, \cdots, a_{n-1}$ without touching $a_n$. If $B$ actually does let $a_1=k-1$, then $A$ choses the whole block from $a_1$ to $a_n$. After $B$ subtracts $1$ from every number without any other choice, $A$ forgets everything and again assumes that that $B$ will never let $a_1=0$ or $a_1 = k-1$. First suppose that $B$ will let $a_1 = k-1$ for over $t$ times. Since $a_n$ is altered only when $B$ subtracts $1$, among the $t$ times, $a_n$ would have been a multiple of $t$. At this state, $A$ can dispose $a_n$ and use the strategy for $(k,n-1)$ on $a_1, \cdots, a_{n-1}$. Suppose the contrary, that $B$ will not let $a_1=k-1$ after some time. Then by the induction hypothesis, $A$ can make at least $(n-1)-(k-1)+2 = n-k+2$ multiples of $t$ among $a_2, \cdots, a_{n-1}$. Now we return to the original problem. We use induction on $n$ with $k$ fixed. $(i)$ $n=k-2$ It is obvious since $n-k+2 = 0$. $(ii)$ Assume that it is true for $n-1$ when $n \ge k-1$. Since we are interested only on whether a number is a multiple of $k$, we may replace each number to the remainder when divided by $k$. Since $0 \le a_1 < k$, we may apply our lemma to prove that $A$ can make either $a_1$ be a multiple of $k$ or there exist at least $n-k+2$ multiples of $k$ among $a_2, \cdots, a_n$. If $a_1$ becomes of multiple of $k$ then $A$ may dispose of $a_1$ and apply the induction hypothesis on $a_2, \cdots, a_n$. Also if $n-k+2$ multiples of $k$ are made, then we are done.
03.01.2016 09:21
I will give a way to win since you can't make me "inductionable" so you can't make $k|a_n$ start the following algorithsm : give the first $k-1$ "$a_i$" with $a_i\neq 0\pmod k$ a label $1,...,k-1$ and every time refresh this label Every turn choose $a_j,..., a_n$ where $a_j$ was labeled $a_n\pmod k$ If it stops means there is $>n-(k-1)$ zeros under mod $k$,i.e.at least $n-k+2$ zeros. and it's easy to see if some $a_i$ ($i$ smallest) has been changed infinite times,then $k|a_i$ infinite times ,then $a_{i-1}$ will change infinite times , contracdition! so we are done!
03.01.2016 10:29
I use 1hour to solve it but 2 to write down the prove hope I'm right
10.10.2022 12:14
Define the allowance of a number to be the maximum interval it can vary in without implying the problem. Basically if this number is $x_i$, then it equals the minimal value of $b-a$, where $a < b$ are such that if $x_i = a-1$, then the problem is true, and if $x_i = b+1$, then also the problem is true. For example, initially the endpoints of the list, $x_1$ and $x_n$ have allowance at most $k-1$ because that's the most it can vary without becoming a multiple of $k$, and if such a thing happens clearly we can ignore this endpoint and finish by induction. Further, say a number not in the interval $[a,b]$ is banned as $x_i$ cannot take this value without implying the problem. Finally, call a number in the interval $[a,b]$ to be pseudo-banned if $x_i$ can take this value at most some number of times before implying the problem (assuming I am using some optimal strategy). I will prove the stronger claim by induction, that if an endpoint of a list of length $n$ has an allowance $A$, then it is possible to make at least $n-A+1$ numbers divisible by $k$. The base case with $A = 2$ is true as if a number can only be one of $X, X+1$, then we can choose which of these it is by picking the block to be just the singleton and therefore you can control the movement ($1$ up or $1$ down) of any block containing it, so you can make at least all except this one divisible by $k$. Suppose $x_n$ has allowance $A$ and it is constrained to lie in $[\ell,\ell+A-1]$. I'm going to only use the last $n-1$ numbers and ignore the first number for most part. Take two cases: Case 1: $\ell$ is pseudo-banned In this case, fast forward until the point where $m$ becomes banned so the allowance of $x_n$ is now $A-1$, now ignore the first number and by induction we can make at least $(n-1) - (A-1) + 1 = n-A+1$ numbers divisible by $k$, as needed. $\square$ Case 2: $\ell$ is not pseudo-banned In this case, it means that we have $x_n = \ell$ infinitely often irrespective of what moves are made. Fast forward to the first time we have $x_n = \ell$. Now operate on the entire block from $x_1$ all the way till $x_n$. Since you can't go below $\ell$, you're forced to move the whole block up by $1$. Now ignore first element again, fast forward to the next time $x_n = \ell$, and keep repeating this. The net effect on the first element is that it keeps getting $1$ added to itself, so at some point it must become divisible by $k$. So this, together with the inductive hypothesis on the last $n-1$ elements gives a total of at least $1 + ((n-1) - A + 1) = n-A+1$ numbers divisible by $k$, as needed. $\square$ Therefore, in both cases we can get at least $n-A+1$ numbers divisible by $k$. Since initially, an endpoint has allowance at most $k-1$ (as otherwise one of them will be a multiple of $k$), we get that we can make at least $n - (k-1) + 1 = n-k+2$ numbers divisible by $k$, as desired. $\blacksquare$