@above actually a_i need not be all equal, in fact once you get that k is a perfect power, then any choice of (a_1, ..., a_k) would work :0 [I personally think this is the troll/tricky part of the problem] I didn't believe this at first, but for (1,2,3,4) you can construct the polynomial x^2+5x-10 which works.

navi_09220114 wrote: @above actually a_i need not be all equal, in fact once you get that k is a perfect power, then any choice of (a_1, ..., a_k) would work :0 [I personally think this is the troll/tricky part of the problem] wait, this means I messed up with construction part during the mock,

here's my submission from the mock. I'm not 100% sure all the details are fine, and I'd be happy if someone took a look

If $k$ is a perfect power all collections work otherwise none work: Part 1: $k$ must be a perfect power Let $P$ have degree $r$. It is not hard to see that there exists a constant $c$ such that when expanded both of the following polynomials have the same $n^r$ and $n^{r-1}$ coefficient. $$P(n+a_1)+P(n+a_2)+\dots+P(n+a_k)$$$$P(\sqrt[r]kn+c)$$If $\sqrt[r]{k}$ is irrational then it is well known that ${\sqrt[r]{k}n}$ is dense in $[0,1]$. Take a very large $n$ such that $\sqrt[r]{k}n+c\approx \frac{1}{2}$. Notice if we take the floor or ceiling of $\sqrt[r]{k}n+c$ then the coefficient of $n^r$ will remain the same but the coefficient of $n^{r-1}$ will change. So we must have $\sqrt[r]{k}$ an integer. Part 2: If $k=a^r$ is a perfect power all collections work It is sufficient to show that for any collection there is a polynomial of degree $r$ with rational coefficients such that, $$P(n+a_1)+P(n+a_2)+\dots+P(n+a_k)=P(an)$$Let $a_0,a_1,\dots,a_r$ be the coefficients of the polynomial. Notice that the $n^r$ coefficient is the same on both sides. On the LHS the $n_i$ is given by $ka_i+c_{i+1}a_{i+1}+c_{i+2}a_{i+2}+\dots+c_{r}a_{r}$. On the RHS it is given by $a_ia^i$. Notice if $a_{i+1},a_{i+2},\dots,a_{r}$ are determined then there exists a rational value of $a_i$ such that the $n^i$ coefficients match. This means we can choose a random $a_r$ and go down the line until we have determined $a_0$. Now we can scale up $P$ and finish.

Official Solution. The solution set is all $k\ge 1$ which is a perfect $d$-th power for some $d\ge 2$, and $(a_1, a_2, \cdots, a_k)$ are arbitrary integers. When $k=1$, then let $m=n+a_1$, and $P$ be any non-linear polynomial works. Henceforth, assume $k\ge 2$ from now. Let us first prove that $k=C^d$ must hold for some positive integer $C\ge 2$. Suppose $(a_1, \cdots, a_k)$ is a collection of integers satisfying the equation for some polynomial $P$ with degree $d\ge 2$. Lemma. Let $P(x)$ and $Q(x)$ are polynomials with integer coefficients, equal degree, and have positive leading coefficients. Suppose for all positive integers $n$ there exist a positive integer $m$ with $P(n)=Q(m)$, then $P(x)=Q(Cx+D)$ for some integers $C\ge 1$ and $D$. Proof of Lemma. Suppose we have a sequence $z_1, z_2, \cdots$ of positive integers such that $$P(n)=Q(z_n)$$As $P$ and $Q$ are both eventually strictly increasing, then $z_n$ is eventually strictly increasing as well. In fact, $\lim_{n\rightarrow \infty} z_n=+\infty$. Suppose $p_d$ and $q_d$ are the leading coefficients of $P(x)$ and $Q(x)$ with degree $d$. $\textit{Step 1:}$ $\displaystyle \lim_{n\rightarrow \infty}\frac{z_n}{n}\rightarrow \sqrt[d]{\frac{q_d}{p_d}}$. $\textit{Proof of Step 1:}$ Write $P(x)=p_dx^d+O(x^{d-1})$, $Q(x)=q_dx^d+O(x^{d-1})$, then as $n$ tends to infinity, $$\frac{P(n)}{n^d}\rightarrow p_d \quad \text{and} \quad \frac{Q(z_n)}{z_n^d}\rightarrow q_d \quad \Rightarrow \quad \left(\frac{z_n}{n}\right)^d=\frac{z_n^d}{Q(z_n)}\cdot\frac{P(n)}{n^d}\rightarrow \frac{q_d}{p_d}$$Hence this implies $\displaystyle\frac{z_n}{n}\rightarrow \sqrt[d]{\frac{q_d}{p_d}}$, as $n\rightarrow \infty$. $\textit{Step 2:}$ $\displaystyle \lim_{n\rightarrow \infty}(z_{n+1}-z_n)\rightarrow \sqrt[d]{\frac{q_d}{p_d}}$. $\textit{Proof of Step 2:}$ We will invoke the Mean Value Theorem: If $Q'$ denote the derivative of $Q$, then there exist $y_n\in[z_n,z_{n+1}]$ such that $$Q(z_{n+1})-Q(z_n)=Q'(y_n)(z_{n+1}-z_n) \Rightarrow z_{n+1}-z_n=\frac{P(n+1)-P(n)}{Q'(y_n)}$$Note that as $z_n\le y_n\le z_{n+1}$, then $\displaystyle\frac{y_n}{n}\rightarrow \sqrt[d]{\frac{q_d}{p_d}}$ as well from Step 1. This implies that $y_n^{d-2}n^{1-d}\rightarrow 0$. However by expanding the coefficients, $P(n+1)-P(n)=dp_dn^{d-1}+O(n^{d-2})$, while $Q'(y_n)=dq_dy_n^{d-1}+O(y_n^{d-2})$, so $$\frac{P(n+1)-P(n)}{Q'(y_n)}=\frac{dp_dn^{d-1}+O(n^{d-2})}{dq_dy_n^{d-1}+O(y_n^{d-2})}=\frac{dp_d+O(n^{-1})}{dq_dy_n^{d-1}n^{1-d}+O(y_n^{d-2}n^{1-d})}$$$$\rightarrow \frac{dp_d}{dq_dy_n^{d-1}n^{1-d}}=\frac{p_d}{q_d}\left(\frac{n}{y_n}\right)^{d-1}$$The last quantity tends to $\sqrt[d]{\frac{q_d}{p_d}}$ by Step 1 again, hence $\displaystyle z_{n+1}-z_n\rightarrow \sqrt[d]{\frac{q_d}{p_d}}$ as $n\rightarrow \infty$. Now we prove the Lemma: As the sequence $z_{n+1}-z_n$ is an integer sequence that tends to a limit $C=\sqrt[d]{\frac{q_d}{p_d}}>0$, then it must be eventually constant, and the limit $C$ must be a positive integer. Hence $z_n=Cn+D$ for some integers $C\ge 1$ and $D$, for all large enough $n$. This implies $P(n)=Q(Cn+D)$ for all large enough $n$, making it a polynomial identity, namely $$P(x)=Q(Cx+D)$$for some integers $C\ge 1$ and $D$. $\square$ Now, let us consider the main problem again. Without loss of generality, we may assume $P$ has positive leading coefficient, otherwise consider $-P$ instead. By the lemma, there exist some integers $C\ge 1$ and $D$ so that $$P(x+a_1)+P(x+a_2)+\cdots+P(x+a_k)=P(Cx+D)$$Considering the leading coefficient implies $k=C^d$, hence $k$ must be a perfect $d$-th power as claimed. As $k\ge 2$, then $C\ge 2$ as well. From now on, let's direct our attention to construct an appropriate polynomial $P$ with degree $d$, whenever $(a_1, \cdots, a_k)$ are integers and $k=C^d$ with $C\ge 2$. The idea is to relax the condition on $P$ to have rational coefficients instead, recursively solve for the coefficients from the highest degree to the lowest degree, then scale it back to have all coefficients being integers. Till this end, given any $(a_1, a_2, \cdots, a_k)$ with $k=C^d$, let's find a polynomial $P$ with rational coefficients such that $P$ has degree $d$ and $$ P(x+a_1)+P(x+a_2)+\cdots+P(x+a_k)=P(Cx) \quad (*) $$Suppose $P(x)=b_dx^d+b_{d-1}x^{d-1}+\cdots+b_0$ where $b_i$ are allowed to be rationals, if we define for all $j\ge 0$, $$s_j=\sum^k_{i=1}a_i^j$$as the $j$-th moment of the $a_i$'s, then by comparing the coefficients from $x^{d-1}, x^{d-2}, \cdots$, we get the following equations: \begin{align*} b_{d-1}C^{d-1}&= b_dds_1+b_{d-1}s_0 \\ b_{d-2}C^{d-2}&= b_d\dbinom{d}{2}s_2+b_{d-1}(d-1)s_1+b_{d-2}s_0 \\ &\cdots\\ b_{d-j}C^{d-j}&= b_d\dbinom{d}{j}s_j+b_{d-1}\dbinom{d-1}{j-1}s_{j-1}+\cdots+b_{d-j+1}(d-j+1)s_1+b_{d-j}s_0\\ &\cdots\\ b_0&=b_d\dbinom{d}{d}s_d+b_{d-1}s_{j-1}+\cdots+b_1s_1+b_0s_0 \end{align*}Note that $s_0=k=C^d$, so the coefficient of $b_{d_j}$ in the $j$-th equation is $$C^{d-j}-s_0=C^{d-j}-C^d\neq 0$$This is non-zero as $C\ge 2$. Hence we can set $b_d=1$, then rewrite the $j$-th equation as: $$b_{d-j}= \frac{1}{C^{d-j}-s_0}\left( b_d\dbinom{d}{j}s_j+b_{d-1}\dbinom{d-1}{j-1}s_{j-1}+\cdots+b_{d-j+1}(d-j+1)s_1\right)$$Note that $s_j\in \mathbb{Z}$ for all $j$, hence if $b_d, b_{d-1}, \cdots, b_{d-j+1}\in \mathbb{Q}$, then $b_{d-j}\in\mathbb{Q}$. Hence by starting with $b_1=1$ and then solving these equations recursively for $b_{d-1}, b_{d-2}, \cdots, b_0$, we must obtain rational solutions for each variable. This gives us the desired $P$ with rational coefficients satisfying (*), and by multiplying a suitable factor to the coefficients of $P$ we can make all of them integers as desired. This completes the proof. $\blacksquare$ Comment 1. There exist simpler bounding solutions to prove that $m$ must be of the form $Cn+D$ for some bounded $D$, and then use Pigeonhole Principle to prove that some $D$ makes the equation true for infinitely many $n$. Nevertheless, this solution shows the power of Mean Value Theorem in a very nice way. Comment 2. The tricky part of this problem is that once we obtain that $k$ is a perfect $d$-th power, one may be tempted to continue the bounding argument and seek further restrictions of $a_1, a_2, \cdots, a_k$. The second part of the proof is completely different from the previous ideas unlike sequences/bounding, but to rather construct linear equations and solve them in $\mathbb{Q}$. (not $\mathbb{Z}$!) This belief that all such $a_i$'s work is actually the hardest part of the problem, in the proposer's opinion.

I don't think the solution in #6 is correct, because c is not necessarily an integer there . While mocking,I think I found a simpler way to prove $a=k^{1/d}$ intgeger.Basically u substitute as in #6 but the only conclusion u can have that is $||a^{d-1} *(b_{d-1} +l-\{a*n\})||$ tends to zero as the lhs is an integer for a bounded integer $l$ .We can run through $||a^{d-1} *(b_{d-1} +l)||$ for all l and thereby choose by kronecker $\{a*n\}$ much smaller compared to the minimum value of this over all $l$ but non zero and get a contradiciton. ....Then I proceeded to bluff in my writeup that $a_i$'s must all be equal

$c$ needs not be an integer

Answer: If $k$ is of the form $b^c$ where $b$ and $c$ are naturals and $c>1$, then any choices for $a_i$ works. Otherwise, no choices for $a_i$ works. Let the polynomial $Q(n) = \sum^{k}_{i = 1} P(n+a_i)$ Let $f(n) = P^{-1}(Q(n))$. Lemma 1: There exists a number $R$ s.t. $f(n+1) - f(n)$ is constant for all $n>R$. Proof: Suppose it is not constant. Notice that for sufficiently large n, we must have $f(n+1) - f(n)$ is bounded. This is because $Q$ is a polynomial of the same degree as $P$ and we have $Q(n+1) - Q(n) = P(f(n+1)) - P(f(n))$. Thus if $f(n+1) - f(n)$ is unbounded, then we will have infinite cases of $n$ where the leading coefficent of the LFS is larger than the leading coefficent of the RHS, thus creating a contradiction. Also, we must have that for sufficiently large n, $f(n+1) - f(n) \leq f(n+2) - f(n+1)$, because if we consider the polynomial $P(x) - P(x-g)$ and $P(x+h) - P(x)$ for some $g, h$ where $g > h$, we will have that the leadin coefficient of $P(x) - P(x-g)$ is larger than the leading coefficient of $P(x+h) - P(x)$, thus for large enough $x$, we will have $P(x+h) - P(x) < P(x) - P(x-g)$. This implies that if $f(n+1) - f(n) > f(n+2) - f(n+1)$, we will have $$P(f(n+1)) - P(f(n)) > P(f(n+2)) - P(f(n+1))$$$$Q(n+1) - Q(n) > Q(n+2) - Q(n+1)$$However this cannot possibly be true for sufficiently large n, since the derivative of Q will be increasing after some point, thus our claim is true. $\blacksquare$ Now this means that for large enough values of $n$, we will have $f(n) = gn + d$ for some constants g and d. Let $l$ be the degree of $P$ and $h$ its leading coefficient. The leading coefficient of $Q(n)$ is $g^lh$ but the leading coefficient of $\sum^{k}_{i = 1} P(n+a_i)$ is $hk$, thus for $Q(n) = \sum^{k}_{i = 1} P(n+a_i)$ to be true for all natural $n$, we need $k = g^l$. Thus from now on we will have $k = b^c$ and also we have $f(n) = bn + d$. Also notice that this is true for large enough values of $n$, but this can be extended for all values of $n$, since the polynomial $P(bn + d) - \sum^{k}_{i = 1} P(n+a_i)$ has infinitely many solutions, thus the polynomials are equal. Now we will prove that if $k = b^c$, then any values for $a_1, a_2, ..., a_k$ can work. We will prove that there exist a polynomial $P$ with rational coefficents and degree $c$ s.t. $\sum^{k}_{i = 1} P(n+a_i) = P(bn)$ for all integers $n$. Let $d_i$ be the $i$th coefficient of $P$. Let us construct $P$ from the top down starting from the coefficient of $n^c$ and going down step by step. Firstly, notice that the coefficient of $n^c$ will be $b^c$ for both sides. Now, by induction, we will assume that the coefficients of $n^c, n^{c-1}, ..., n^{t+1}$ for both sides are equal and $d_c, d_{c-1}, ..., d_{t+1}$ have all been constructed. First observation is that the values of $d_{t-1}, d_{t-2}, ..., d_0$ do not change the value of the coefficient of $n^t$ for both sides. Now if we only consider the coefficient of $n^t$ for both sides, we have $Xn^t + d_{t}kn^t = Yn^t + d_{t}b^{t}n^t$. If we rearrange this, we get $d_t = \frac{X-Y}{b^t - k}$, but note that since $t<c$, we have that the denominator is nonzero (except when $b=1$, but then note $k=1$ and thus any polynomial will work), and also all the numbers are rational, thus we get $d_t$ is rational, and we can repeat this for all $d_i$.