Let $k$ be a positive integer and $a_1, a_2,... , a_k$ be nonnegative real numbers. Initially, there is a sequence of $n \geq k$ zeros written on a blackboard. At each step, Nicole chooses $k$ consecutive numbers written on the blackboard and increases the first number by $a_1$, the second one by $a_2$, and so on, until she increases the $k$-th one by $a_k$. After a positive number of steps, Nicole managed to make all the numbers on the blackboard equal. Prove that all the nonzero numbers among $a_1, a_2, . . . , a_k$ are equal.
Problem
Source: MEMO 2022 T2
Tags: algebra
Behanorm_rifghcky
02.09.2022 18:11
Define $P(x)=a_1+a_2x+...+a_kx^{k-1}$,we know that $\exists ~Q(x)=b_0+b_1x+b_2x^2+...+b_{n-k+1}x^{n-k+1}\in \mathbb Z_{\geqslant 0}[x]$ such that $P(x)Q(x)=T(1+x+x^2+...+x^{n-1})$ where $T\in \mathbb R_{\geqslant 0}$.Then we have$\frac{P(x)}{T}\in \mathbb Q_{\geqslant 0}[x]$.By Gauss Lemma we know that there exists $T'\in \mathbb Q_+$such that $\frac{P(x)}{TT'},T'Q(x) \in \mathbb Z_{\geqslant 0}[x]$.So it's enough to show that for any two polynomials $P(x),Q(x)\in \mathbb Z_{\geqslant 0}$ such that $P(x)Q(x)=1+x+x^2+...+x^{n-1}$ we have: all the nonzero coefficients of $P(x),Q(x)$ are $1$. Assume that there are $d_1,d_2$ nonzero terms in $P(x),Q(x)$ respectively.Then there are at most $d_1d_2$ distinct terms in $P(x)Q(x)$ which emplies that $d_1d_2\geqslant n$.On the other hand we have $P(1)Q(1)=n$ which implies $d_1d_2\leqslant n$.Combine the two inequalities we get what we want.