Obviously, $n=1$ fails. However, to show that $\boxed{n=2}$ works, note that linear polynomials work; for quadratic polynomials, if $bX$ is the middle term, then $P(X)=P(-b-X)$, so quadratics work. We now claim that $n\ge 3$ fail. To show that $n\ge 5$ fail, let $m=\lceil\log_2 n\rceil$. Then take $P(X)=X^m\left(X^{2^{m-2}}+2^m-1\right)+1$ if $m$ is odd, and $P(X)=X^{m+1}\left(X^{2^{m-2}}+2^m-1\right)+1$ if $m$ is even (so that all terms of $P(X)$ have odd degree). It is easy to check that this has degree $\le n$ for $n\ge 5$. Moreover, note that $P(X)\equiv 1\pmod{2^m}$. Thus, if $P(x_1)+P(x_2)+...+P(x_k)=P(x_{k+1})$, then $k\equiv 1\pmod{2^m}$. But $1\le k\le n\le 2^m$, so $k=1$. Now it remains to show that $P(x)=P(y)$ cannot happen, but the derivative is positive everywhere, so we are done. To show that $n=3$ fails, just take $P(X)=X(X^2+2)+1$. Then $P(X)\equiv 1\pmod{3}$, and thus if $P(x_1)+P(x_2)+...+P(x_k)=P(x_{k+1})$ then once again we get $k=1$. Since $P'(X)>0$ for all $X$, $P(x)=P(y)$ cannot happen, and we are done again. To show $n=4$ fails, take $P(X)=X^2(X^2+7)-4X+1$. Then note $P(X)\equiv 1\pmod{4}$, and once again we get $k=1$. Suppose $P(x)=P(y)$ for some $x,y$. Then $x^4-y^4+7(x^2-y^2)=4(x-y)$, or $(x+y)(x^2+y^2+7)=4$. But $|x^2+y^2+7|\ge 7$, so $|x+y|\le \frac{4}{7}$. Since $x+y$ is an integer, $x+y=0$, which contradicts $(x+y)(x^2+y^2+7)=4$. Thus we are done for $n=4$ as well.

The answer is $n = 2$ only. First, we contend the result holds for $n = 2$. The result is immediate if $\deg P = 0$ (take $k=1$) or $\deg P = 1$ (take $k=2$). For $\deg P = 2$, we note the polynomials $P(x) = x^2+bx+c$ are never injective, and hence fail the constraint when $k = 1$. Next we remark that the result is vacuously false for $n = 1$. Finally, the main part: we show that each fixed $n \ge 3$ does not work. Select a prime $p > 2$ such that $p \le n \le 2p$ (by Bertrand postulate). Then, consider the polynomial \[ P(x) = x^p + (2p-1)x + 1. \]We have $P(x) \equiv 1 \pmod p$ and $P(x) \equiv 1 \pmod 2$ for every $x \in \mathbb Z$, whence $P(x) \equiv 1 \pmod{2p}$. Thus if such $x_i$ exist we have \[ \underbrace{1 + \dots + 1}_k \equiv 1 \pmod{2p} \]and so $2p \mid k-1$, but from $k \le n$ we conclude $k = 1$. This means there must be integers $a \neq b$ such that $P(a) = P(b)$, whence \[ \frac{a^p - b^p}{a-b} = -(2p-1) \]which is impossible since the left-hand side is always positive (for $a \neq b$).

Another approach based on an idea I heard from Kevin Ren: call $k(P)$ the minimal $k$ for which there exist distinct integers $x_1,x_2,\dots,x_k,x_{k+1}$ satisfying $P(x_1)+P(x_2)+\dots+P(x_k)=P(x_{k+1})$. The key idea is Quote: If $P(x)\equiv 1\pmod{M}$ $\forall x$, then $k(P)\equiv 1\pmod{M}$. If $P$ is also injective, i.e. $k(P)\neq 1$, then $k(P)\ge M+1$ follows. Taking for each $m\ge 3$ the polynomial \[ P_m(x)=x\cdot (x^2+1)(x^2+2)\dots(x^2+m)+1 \]is increasing and always $1$ mod $m!$, so $k(P_m)\ge m!+1$. Since $\cup_{m\ge 3}[2m+1;m!]$ covers $[7;\infty)\cap \mathbb{Z}$, this proves that $n\ge 7$ does not satisfying the condition. Using $P(x)=x(x+1)(x-1)+6x+1$ which is increasing and always $1$ mod $6$, we can kill $3\le n\le 6$, leaving only the trivial $n=1$, $n=2$, dealt with as above. $\blacksquare$

Problem 2. Very nice problem. The key idea of my solution is that if we have $P(x)$ injective and $P(x) \equiv 1 \pmod{n}$ always, we are done. The $P(x)$ strictly increasing is the hardest part to handle. Here's the sketch of my solution without the big calculations. First of all, check that $n=1$ fails and $n=2$ works. We will show that $n=2$ is the only solution. Denote $S_n = \{x| 0 \le x < n, \exists m \neq 0 \pmod{n}, m^2 \equiv x \pmod{n} \}$. I claim that if $1+2|S_n| \le n$, then $n$ does not satisfy the condition. This will eliminate a lot of candidates. Take the polynomial $P(x) = x \prod_{i \in S_n} (x^2 + n - i) +1$. It is easy to see that, by definition of $S_n$, that $P(x)$ is always $1$ in $\pmod{n}$. Say that $P(x_1) +P(x_2) + \cdots +P(x_k) = P(x_{k+1})$. Then, we have $k \equiv 1 \pmod{n}$, so $k=1$. Therefore, we have $P(x_1) = P(x_2)$. However, notice that $P'(x)>0$ always, since $P(x)$ only consists of terms with odd degree and positive coefficients (or just calculate the derivative by the rule of product, not so bad). Anyways, clearly this gives a contradiction by MVT or injective property. So we now need to find numbers such that $1+2|S_n| \le n$. Denote $T_n = \{x| 0 \le x < n, \exists m \text{ s.t. } m^2 \equiv x \pmod{n} \}$. The difference is that $m \neq 0 \pmod{n}$ condition is gone. Clearly, $|T_n| \ge |S_n|$, with equality iff $n$ is not prime. Also, notice that we can use CRT with $|T|$ now. Anyways, brute force calculations (very boring tbh) gives us that $1+2|S_n| \le n$ holds for all numbers not in the form $2p$, where $p$ is a prime. Thankfully I checked this with a computer afterwards, it works Now, we show that $2p$ does not satisfy the conditions as well. Take $l=2p-1$, and set $P(x) = x \prod_{i \in S_l} (x^2 + kl - i) + 1$. We will determine $k$ later, between $1$ and $2$. It is easy to see that $P(x) \equiv 1 \pmod{l}$. Similarly, we have $k \equiv 1 \pmod{l}$, so $k=1$ or $k=l+1=2p$. If $k=1$, we have $P'(x) > 0$, which gives us a contradiction. Notice that we can select $k$ so that $P(x)$ is always odd. Just take $i$ as the first element of $S_l$, and set $k$ so that $kl-i+1$ is even. This can be done because $l$ is odd. Anyways, after selecting $k$ accordingly, we now see that $0 \equiv P(x_1) + \cdots + P(x_{2p}) \equiv P(x_{2p+1}) \equiv 1 \pmod{2}$, contradiction. So we are done with our only answer $2$. After writing this here, I just realized that I made a typo describing $P(x)$ on the actual contest. FML. KMS. Wow darn I overcomplicated a problem again didn't I

The polynomial $$P(x) = x ((x-1)(x-2)(x-3) \dots (x-(N-1)) + N!) + 1$$where $N = 2 \lfloor \frac{n-1}{2} \rfloor + 1$ is injective on the integers and hence is a counterexample for $n \ge 3$ since $N! > n$ and $P(x) \equiv 1 \pmod {N!}$.

I solved this problem knowing that this would be a number theory problem. However, I am not sure I would solve this problem without this hint. Is there any motivation for wanting to use number theory in this problem (e.g. prove $P(x) \equiv 1 \pmod{n}$)? Thanks!

I constructed polynomials $P$ is injective and $\equiv1\pmod{n}$ but only for odd $n>2$. For even $n$ there's still a long way to go.

It's a lot easier if the construction is $ \equiv 1\pmod{n!}$.

Ah... After figuring out why $P(x)=x((x-1)(x-2)...(x-n)+n!)+1$ is injective, I solved it for even $n$.

Can anyone prove or disprove the following? Conjecture. For any monic integer polynomial $P$, define $k(P)$ to be the minimal $k$ for which there exist pairwise distinct integers $x_1,x_2,\dots,x_{k+1}$ such that \[ P(x_1)+P(x_2)+\dots+P(x_k)=P(x_{k+1}). \]Then $k(P)$ exists. Conjecture'. The same, but $x_1,x_2,\dots,x_{k+1}$ need not be distinct, and $k>1$.

randomusername wrote: Conjecture. For any monic integer polynomial $P$, define $k(P)$ to be the minimal $k$ for which there exist (not necessarily distinct) integers $x_1,x_2,\dots,x_{k+1}$ such that \[ P(x_1)+P(x_2)+\dots+P(x_k)=P(x_{k+1}). \]Then $k(P)$ exists. This version is easy to prove. First suppose that the constant term $a_0$ of $P$ is non-zero. Then $P(ma_0)$ is a multiple of $P(0)=a_0$, for every integer $m$. Since $P$ is monic, $P(ma_0)$ is positive for $m$ sufficiently large. Hence there exist integers $m,r>0$ with $P(ma_0)=r\cdot P(0)= P(0)+P(0)+\cdots+P(0)$. Next suppose that the constant term $a_0$ of $P$ is zero. Let $t$ be an integer with $q:=P(t)>0$. Then $P(mq)$ is a multiple of $q$. Since $P$ is monic, $P(mq)$ is positive for $m$ sufficiently large. Hence there exist integers $m,r>0$ with $P(mq)=r\cdot P(t)= P(t)+P(t)+\cdots+P(t)$.

my solution in the test $n=1$ fails, and $n=2$ works, because $P(x)=x^2 +ax+b $ is symmetric with $x=- \frac{a}{2}$ if $n \ge 3 $ , it doesn't work. proof) first, when n is odd number, Let $P(x)=x(x-1)(x-2) \cdots (x-n+1)+ n!Ax+1$, when $A$ is integer. then, $P(x) \equiv 1 (mod n!)$ So $k \equiv P(x_1)+P(x_2)+ \cdots P(x_k) \equiv P(x_{k+1}) \equiv 1 (mod n! )$ $\therefore k=1$ when $A$ is bigger then the maximum value of $-(x(x-1)(x-2) \cdots (x-n+1))'$ ( it exists because n is odd number) then, $P(x)$ is increasing function, and $P(x_1)=P(x_2)$ can't satisfy $\therefore n\ge 3 $ odd number fails when n is even number which $n\ge 4$, $P(x)=x(x-1)(x-2) \cdots (x-n+2)+ (n-1)!Ax+1$ works the same $\therefore n=2 $ only satisfy

I shall just show $n \geq 3$ is bad. The idea is to control $P(x)$ modulo $C$ for some fixed constant $C$. Consider polynomials of the form\[P(x) = (x^p - x + 1) + pQ(x)\]where $Q(x)$ is an integer polynomial and $p > 2$ is prime - clearly $P \equiv 1 \pmod p$ for all $x$. Thus, in order for there to exist $k$ and $x_1, \ldots , x_{k+1}$, it must follow that $p \mid k-1$. In fact, for each $n$, we may let $p$ be the largest prime $< n$, and $Q(x) = 2$. In that case, $2 \mid p-1$ too and thus $2p \mid k-1$ and by assumption of maximal $P$ combined with Bertrand's Postulate, $2p \geq n$ hence $k = 1$. In this case, we need $x_1 \neq x_2$ for which $P(x_1) = P(x_2)$. But the polynomial $P(x) = x^p + (2p-1)x + 1$ is clearly injective - impossible. Hence, for $n \geq 3$, we have found a general counterexample, as desired.

so beautiful for my $200$th post lemma : for each $x \neq \{4,6\}$ there exists an odd $n $ such that $n \ge x > \phi(n)$ proof: if $n$ is odd then $x=n$ works if it's even so at least one of $\{n+1,n+3,n+5\} $ is divisible by $3$ let it $x$ $\phi(x) \le \frac{2}{3}.x \le x-5 \le n $ now for $n <15$ we can check it manually $\square$ for $n=2$ it's easy. now for $n \ge 3$ now for any $n \neq \{4,6\}$ choose such $m \ge n > \phi(m)$ is the lemma and consider $P(x)=x^{phi(m)+1}+(m-1)x+1$ this is injective and clearly works (since $P \equiv 1 \bmod m$) now for $n=4$ let $P(X)=x^3+5x+1$ (consider it $\bmod 6$) for $n=6$ let $P(x)=X^5+9x+1$ (consider it $\bmod 10$) and we win

I did a nongeo I claim the answer is $n=2$. $n=1$ doesn't work by $P(x)=x$, $n=2$ doesn't work because every monic quadratic has $2$ $x$ values with the same output, and every monic linear function fails for $n\neq 1$. For $n\ge 3$, let $p$ be the largest prime below $n$. Let $P$ be the product all of the primes below $n$, and let $P_1$ be a sufficently large multiple of $P$. Then let $P(x)=x(x+1)(x+2)\cdots(x+p-1)+P_1x+1$. $P(x)$ is $1\mod P$, and $P\ge n-1$ by, among other things, Bertrand's. Or that if $P< n-1$, then $P+1$ is less than $n$ and $P+1$ isn't divisible by any primes less than $n$, contradiction. Thus $k>1$ doesn't work, and we only need to show that no two integer input values produce the same output value. But since $P'(x)$ is an even function and $P_1$ is sufficiently large, $P'(x)>0$ for all $x$, as desired.

The answer is $n=2$ only. Obviously $n=1$ fails and $n=2$ works, since if the coefficient of $x$ is $a$, then $P(x)=P(-a-x)$. Now we prove that $n \geq 3$ fail. By Bertrand's postulate we can pick some odd $p \leq n \leq 2p$. Then let $$P(x)=x^p+(2p-1)x+1,$$so $P(x) \equiv 1 \pmod{p}$ for all $x$ by Fermat's Little Theorem. Further, $P(x) \equiv 1 \pmod{2}$ for all $x$ as well, so by CRT, $P(x) \equiv 1 \pmod{2p}$. Thus if we select $k$, the LHS of the equation is congruent to $k \pmod{2p}$, while the RHS is congruent to $1 \pmod{2p}$. For size reasons, this means $k=1$, so we just have to show that $P$ is injective over $\mathbb{Z}$. In fact, $P$ is injective over $\mathbb{R}$, since $P'(x)=px^{p-1}+(2p-1)>0$ for all real $x$, so we're done. $\blacksquare$ Remark (slight generalization): Because I apparently can't read, I believe that the phrase "degree at most $n$" can be replaced with "degree exactly $n$" and the problem still holds. By taking $p$ as before, the polynomial $$P(x)=x^n+(2p-1)x^{n-p+1}+1$$works for $n$ odd for the same reason as before. For $n$ even, I believe (haven't checked) that $$P(x)=x^n+(2p-1)x^{n-p+1}+x^p-x+1$$works. Again $P(x) \equiv 1 \pmod{2p}$, but showing injectivity is much harder. Derivative stuff shows that $P$ is injective over $\mathbb{R}_{\geq 0}$, and should be injective over $\mathbb{Z^-}$ (not by derivatives but by comparing $P(-x)$ and $P(-x-k)$ for $x,k>0$). Again by plugging in $-x-k$ and $x$, as well as $-x$ and $x-k$ (both for $x,k>0$), and doing stupid bounding (like showing that we can set $k=1$), we can show that $P$ is indeed injective. Remark (motivation): Also because I can't read, I forgot about monic (actually I read it at first and then dropped it when doing the problem). The idea of controlling $P$ modulo something to be $1$ sort of comes from here. For example, something like $P(x)=100000000x^3+1$ forces $k=1$ just as well, so we adapt this to monic polynomials once we reread the problem by controlling outputs of $P$ using FLT. The other thing that we need (literally necessary) is injectivity by considering $k=1$, which it turns out isn't that hard to get. In particular, if monic is dropped again something like $P(x)=1000000(x^8+2x)+1$ works for $n=8$ and everything else by simple bounding, implying that we can kinda throw terms together and bound as well.

Solved with OronSH. The answer is $\boxed{n = 2}$. To see this works, note that if $P$ is constant, then $k = 1$ holds, and if $P$ has degree $1$, then $k = 2$ holds. If $P$ has degree $2$, then let $P(x) = x^2 + bx + c$. Since $P(x) = P(-b-x)$, we see that $k = 1$ holds if $x_1 + x_2 = b$, which proves that polynomials of degree $2$ work. A counterexample for $n = 1$ is $P(x) = x$, so assume $n \ge 3$. Claim: For any odd positive integer $m \ge 3$, there exists a real number $r$ such that the polynomial $Q_C(x)= (x-1)(x-2) \cdots (x-m) +Cx + 1$ is injective over the real numbers for any real number $C>r$. Proof: It suffices to show that the polynomial $Q_C'(x)$ has no real roots, which would imply there don't exist reals $a,b$ with $Q_C(a) = Q_C(b)$. Note that $Q_C'(x) - C$ is an even degree polynomial with positive leading coefficient, so it has a minimum $c$. Choosing $ r > |c|$ gives that\[Q_C'(x) > c + C > c + r > c + |c| > 0\]for real numbers $x$, as desired. $\square$ Now for any fixed odd positive integer $m$, let\[ P(x) = (x-1)(x-2) \cdots (x-m) + N \cdot m! \cdot x + 1\]and $N$ large enough such that $P$ is injective over the real numbers. Claim: For any integer $x$, $m! \mid (x-1)(x-2) \cdots (x-m)$. Proof: Note that $\frac{(x-1)(x-2) \cdots (x-m)}{m!} = \binom{x-1}{m}$, which is clearly an integer. $\square$ Therefore, $P(x) \equiv 1\pmod{m!}$ for any integer $x$. Now we claim that $P(x)$ is a valid counterexample for both $n=m$ and $n = m + 1$ ($m \ge 3$ of course). There does not exist distinct $x_1, x_2$ with $P(x_1) = P(x_2)$, so $k = 1$ is impossible. For any $1< k \le m + 1$, we have $P(x_1) + P(x_2) + \cdots + P(x_k) \equiv k\pmod{m!}$, and $P(x_{k+1}) \equiv 1\pmod{m!}$, so $m!\mid k - 1$. This is clearly impossible since $0 < k - 1 \le m < m!$, so $P$ doesn't work for $n = m$ or $n = m + 1$. Hence $n = m, n = m + 1$ fail for any odd integer $m\ge3$, so all $n\ge 3$ fail.

The answer is $n=2$ only. Construction: For monic linear polynomials, $P \equiv x-c$, just take $(x_1, x_2, x_3) = (0, 2c, c)$. For quadratic polynomials $x^2+bx+c$, take $(x_1, x_2) = (k, b-k)$ for any integer $k$. Bound: The $n=1$ case is straightforward because linear polynomials are monotonic. For $n \geq 3$ and $n \neq 4$, let $n = p_1^{k_1} p_2^{k_2} \cdots p_\ell^{k_\ell}$ be the prime factorization of $n$. Then, if $n$ is odd, consider \[R(x) = \left(x^{p_1^{k_1}-p_1^{k_1-1}+k_1} + \left(p_1^{k_1} - 1\right)x^{k_1}\right)\left(x^{p_2^{k_2}-p_1^{k_2-1}+k_2} + \left(p_2^{k_2}-1\right)x^{k_2}\right) \cdots \left(x^{p_\ell^{k^\ell}-p_\ell^{k_\ell-1}+k_\ell} + \left(p_\ell^{k_\ell}-1\right) x^{k_\ell}\right).\]Otherwise, let $n = 2^k \cdot p_1^{k_1} \cdots p_\ell^{k_\ell}$, and append a factor of $x^{2^{k-1}+k} +\left(2^k-1\right)x^k$ to $R(x)$. Now, if $\deg R$ is currently even, we append a factor of $x+1$ to $R$. We first prove that $\deg P \leq n$. Reindex so that $p_1 = 2$. This follows because of the inequality $p_i^{k_i-1} \geq k_i$ for all positive integers $k_i \geq 1$, with equality when $k_i = 1$ and $k_i = 2$ when $p_i = 2$. So then \[\deg P - 1 \leq p_1^{k_1} + p_2^{k_2} + \cdots + p_\ell^{k_\ell} \leq p_1^{k_1} p_2^{k_2} \cdots p_\ell^{k_\ell} = n\]because each power is at least $2$. In particular, equality holds if and only if $n = p$ is a prime or $n = 4$. In those cases, we do not append a factor of $x+1$ to $R$, so the inequality still holds. Claim: For any positive integer $m$ and prime $p_i \mid n$, $m^{p_i^{k_i} - p_i^{k_i-1} + k_i}+\left(p_i^{k_i}-1\right)m^{k_i}$ is a multiple of $p_i^{k_i}$. Proof: Take everything modulo $p_i^{k_i}$. If $p_i \mid m$, then $p_i^{k_i} \mid m^{k_i}$, so the result follows. Otherwise, \[\nu_p\left(m^{p_i^{k_i} - p_i^{k_i-1}} - 1\right) = \nu_p\left(m^{p-1} - 1\right) + \nu_p\left(p^{k_i-1}\right) \geq k_i\]by LTE; thus $p_i^{k_i}$ still divides the expression. $\blacksquare$ Thus it follows that $P(m) \equiv 1 \pmod n$ for any positive integer $m$. But then for any $2 \leq k \leq n$, the LHS will be congruent to $k \neq 1$ mod $n$, while the RHS will be congruent to $1$, contradiction.

, $R(x)$ is monotonically increasing (because $p_i^{k_i} - p_i^{k_i-1}$ is even for all $p_i$), so $P(x)$ is monotonically increasing. Thus there do not exist $x_1, x_2$ with $P(x_1) = P(x_2)$, and this completes the proof of the $n \neq 4$ case. Now we deal with the $n=4$ case. In this case, take $P(x) = x^4+15x^2-24x+1$, such that $P(m) \equiv 1 \pmod 4$ for all positive integers $m$. It follows by previous arguments that we must have $k = 1$. Say $P(a) = P(b)$. Then we have \[(a-b)\left((a+b)\left(a^2+b^2+15\right) - 24\right) = 0.\]We can check that there are no pairs of integers $(a, b)$ such that $(a+b)(a^2+b^2+15) = 24$ by a finite case check. This finishes the proof. Remark: The problem dies once one realizes it is actually number theory. Remark: The $k=1$ case gave me incredible grief while solving this problem, as the length of the solution indicates. It's avoidable by using the ``slightly less precise" Bertrand construction, which I actually thought of doing. But spamming terms is fun and makes me look cool