TheBarioBario wrote: Let $m,n$ and $a_1,a_2,\dots,a_m$ be arbitrary positive integers. Ali and Mohammad Play the following game. At each step, Ali chooses $b_1,b_2,\dots,b_m \in \mathbb{N}$ and then Mohammad chosses a positive integers $s$ and obtains a new sequence $\{c_i=a_i+b_i\}_{i=1}^m$, where $$b_{m+1}=b_1,\ b_{m+2}=b_2, \dots,\ b_{m+s}=b_s$$The goal of Ali is to make all the numbers divisible by $n$ in a finite number of steps. FInd all positive integers $m$ and $n$ such that Ali has a winning strategy, no matter how the initial values $a_1, a_2,\dots,a_m$ are. I guess there are some typos since I don't see the notion of s and those periodic definitions really applicable in the problem.

I think this is equivalent to ELMO 2012/6

Nice problem. The solution is $(m,n)=(p^{a},p^{b})$ when $p$ is a prime number. proof proceeds with 4 steps. We call a pair $(m,n)$ good if Ali has a wining strategy. Step 1: If $(m,n)$ is a good pair and $d|m$ then $(d,n)$ is also a good pair. Step 2: $(m,nk)$ is a good pair if and only if $(m,n)$ and $(m,k)$ are both good pairs. Step 3: If $(m,n)$ is a good pair then $\gcd(m,n)>1$. Step 4: $(p^{a},p)$ is a good pair. I just prove the last statement. Let $T:\big(\mathbb{Z}_{p}\big)^{m}\rightarrow \big(\mathbb{Z}_{p}\big)^{m}$ be a 1-shift operator that $$T(a_{1},a_{2},\cdots,a_{m})=(a_{2},a_{3},\cdots,a_{m},a_{1})$$Where $m=p^{a}$. We claim that if at each turn Ali chooses $b_{i}=-a_{i}$ he will win the game. So at each turn the sequence $(a_{1},\cdots,a_{m})$ changes to $\big(T^{s}-\mathrm{Id}\big)(a_{1},a_{2},\cdots,a_{m})$. So it's enough to prove that $$\prod_{j=1}^{p^{a}} (T^{s_{j}}-\mathrm{Id})\equiv 0\;\; (\text{mod}\; p),$$but we have $T-\mathrm{Id}\big| T^{s}-\mathrm{Id}$. Therefore it is enough to prove that $(T-\mathrm{Id})^{p^{a}}\equiv 0 \; (\text{mod}\; p)$ which is true because $$(T-\mathrm{Id})^{p^{a}}\equiv T^{p^{a}}-\mathrm{Id}=0\;\;(\text{mod}\; p).$$

The answer is $(m,n)=(p^k,p^l)$ where $p$ is a prime. First I show it works. Claim: $(m,n)=(p,p)$ works. Proof: Let $P(x)$ be the unique polynomial in $\mathbb{Z}_p[x]$ with degree at most $p-1$ such that $P(j)=a_j$ for all $0\le j\le p-1$ Ali chooses a polynomial $Q(x)$, while Mohammed replaces $P(x)$ with one of $P(x)+Q(x+j)$ for some $j\in \{0,\cdots,p-1\}$. Let $ax^d$ be the leading coefficient of $P(x)$, then picking any polynomial $Q(x)$ with leading term $-ax^d$ decreases the degree of the polynomial by 1. Therefore, this strategy works. Claim: $(m,n)=(p^k, p)$ works. Proof: induct on $k$. For $0\le j<p^{k-1}$, let $P_j(x)$ denote the unique polynomial in $\mathbb{Z}_p[x]$ such that $P_j(t)=a_{j+tp^{k-1}}$ Keep a running counter $c$ the starts at $p-1$ and decreases to $0$. Let $l_j$ be the $x^c$-coefficient of $P_j$. By inductive hypothesis on $k-1$, Ali can get all $l_j$ to be 0 if they play with this sequence. Reflect a move with $b_j=z$ with moves with picking $b$ st $b_{j+tp^{k-1}}$ forming a polynomial with leading term $zx^c$. Now decrement c by 1. This eventually guarantees that $a_{j+tp^{k-1}}$ does not depend on $t$ so we apply inductive hypothesis where $b_j$ is uniquely defined by j mod $p^{k-1}$. To get $(p^k,p^l)$ to work, we apply strategy to get everything divisible by $p$. Now we only use multiples of $p$ and we are dealing with a smaller game $(p^k,p^{l-1})$ Now we show nothing else works. I will first deal with the case where $n=p$ is a prime. Claim: if $m<p$ then Ali cannot win. Proof: consider the quantity $\sum_{j=0}^m (-1)^j \binom mj a_j$ and suppose initially it isn't zero mod p. I claim Mohammed can ensure this quantity is never zero. Notice the sum of all possible values is m times the original value, because the added increments $b_i$ cancels out in this sum. Claim: if $m>p$ then Ali cannot win. Proof: I claim Mohammed can guarantee $a_0,\cdots, a_{p-1}$ is not constant. If $b_i$ is nonconstant Mohammed can choose an appropriate $s$ such that $p\nmid a_0+\cdots+a_{p-1}$. Now, suppose $n$ has two prime factors, call $p<q$. If $m>p$ then Mohammed can guarantee some element is nonzero mod p thus not divisible by n. Otherwise $m<q$ and Mohammed can guarantee one element is not divisible by $q$. Therefore $n=p^l$ for some prime $p$ and integer $l$. If $m$ contains a prime factor not equal to $p$, call $q$ and consider the sums $S_j=a_j+a_{j+q}+\cdots + a_{j+n-q}$. Note shifting $s$ by $\frac nq$ doesn't affect $S_j$ and Mohammed can guarantee $S_j$ is not divisible by $p$. The end.

Note: the ULTIMATE geo god (who is so pro of a geo god that I don't feel privileged to refer to him by his aops username) points out that the same polynomial argument can be carried out in $\mathbb{Z}_{p^k}$, with "lagrange-style" polynomials $f(x): \mathbb{Z}_{p^k} \to \mathbb{Z} = \sum\limits_{j=0}^{p^k-1} f(j) \binom{x-j-1}{p^k-1}$, which works because $\binom{x-j-1}{p^k-1}$ is divisible by $p$ unless $x-j-1\equiv p^k-1 (\bmod\; p^k)$ which means $x=j$ and $\binom{x-j-1}{p^k-1} \equiv 1(\bmod\; p)$. CANBANKAN wrote: Keep a running counter $c$ the starts at $p-1$ and decreases to $0$. Let $l_j$ be the $x^c$-coefficient of $P_j$. By inductive hypothesis on $k-1$, Ali can get all $l_j$ to be 0 if they play with this sequence. Reflect a move with $b_j=z$ with moves with picking $b$ st $b_{j+tp^{k-1}}$ forming a polynomial with leading term $zx^c$. Now decrement c by 1. This eventually guarantees that $a_{j+tp^{k-1}}$ does not depend on $t$ so we apply inductive hypothesis where $b_j$ is uniquely defined by j mod $p^{k-1}$. To clarify, we are playing the $(p^{k-1},p)$ game on $l_0, l_1, \cdots, l_{p^{k-1}-1}$. Suppose in the $(p^{k-1},p)$-game strategy, Ali chooses the sequence $b_0, \cdots, b_{p^{k-1}-1}$. Then Ali will choose polynomials $X_j$ for $0\le j<p^{k-1}$ where the leading coeff of $X_j$ is $b_jx^c$. Then if Mohammed chooses to rotate them by $tp^{k-1}+r$, $l_j$ becomes $l_j+b_{j+tp^{k-1}+r}=l_j+b_{j+r}$ (if I rotate by $p^{k-1}$, the $b_j$'s aren't affected as the $X_j(t)$ become $X_j(t+1)$, whose leading coefficients don't change.) This justifies it being the same game as $(p^{k-1},p)$ because I have $l_0,\cdots,l_{p^{k-1}-1}$ and need to make them 0. He will make all the $P_j$'s have degree at most $p-1$, then $p-2, \cdots,$ and eventually $0$, which implies $a_j=a_{j+p^{k-1}}=\cdots=a_{j+(p-1)p^{k-1}} \forall j$. Now A adapts a strategy on $(a_0,\cdots,a_{p^{k-1}-1})$ and chooses $b_j=b_{j+p^{k-1}}=\cdots=b_{j+(p-1)p^{k-1}}$ in remaining moves, so Mohammed's shifts are equivalent to shifts mod $p^{k-1}$, so a strategy for $(p^{k-1},p)$ finishes.