This problem was proposed by Warut Suksompong, Thailand.

please, please correct me if im wrong

actually this is definitely wrong because i submitted this for p4 and got a 0. Please help me correct this argument

Wait $P$ can hypothetically be non-surjective.... the set of contiguous partial sums of $(a_i)$ does not necessarily cover all of $\mathbb{Z}$

yayups wrote: Wait $P$ can hypothetically be non-surjective.... the set of contiguous partial sums of $(a_i)$ does not necessarily cover all of $\mathbb{Z}$ there we go (i was so blind i didnt see $i < j$) well i mean this definitely wouldnt have made sense because all that partial sum phrasing would have been completely unncessary but i clearly wasnt in the mood for thinking that day :/ thanks!

Here's a partial solution, leaving out the hard case (polynomial of odd degree greater than 1). The answer is all linear polynomials. We will divide this proof into two parts. Part 01. Proving any linear polynomials satisfy the requirement. This is equivalent to proving that for any permutation sequence of $\mathbb{Z}$, there exists a substring of length more than $1$ which has a sum of $a \ (\text{mod} \ b)$. To do this, consider all numbers which are $a \ (\text{mod} \ b)$, name them $a_1, a_2, a_3, \dots$. Name the sum of all the numbers between $a_i $ and $a_{i + 1}$ as $b_i$. Hence, we now have a block of \[ a_1 b_1 a_2 b_2 a_3 b_3 \dots \]Consider the sum of the blocks $a_1 b_1a_2 b_2\dots a_ib_i$ $i = 1,2, 3, \dots$. Notice that this must not be $a \ (\text{mod} \ b)$. By Pigeon Hole Principle, there must exists two indices $i$ such that the sum is the same modulo $b$. Now, let these indices be $x,z$, then substract block $a_1b_1a_2b_2 \dots a_x b_x$ from $a_1b_1a_2b_2 \dots a_zb_z$, we attain that $a_{x+1}b_{x+1}a_{x+2}b_{x+2}\dots a_zb_z$ is $0$ modulo $b$, therefore, consider \[ a_{x+1}b_{x+1}a_{x+2}b_{x+2}\dots a_zb_za_{z + 1} \]This block clearly has sum $a \ (\text{mod} \ b)$. Part 02. Construct a sequence to eliminate all other polynomials. We deal the three polynomials as follow: SubCase 01. Constant Polynomials Suppose $P(x) = c$. Now, consider a large value $M$ such that $M > (100c+1)^{100}$. Call all numbers larger than $M$ large numbers and otherwise call it small numbers. Consider the following sequence \[ 0, c, 1, c+1, -1, c + 2, 2, c + 3, -2, c + 4, 3, \dots,\]where $c > M$ is a large number. (If eventually $c$ will be used again, this means that all terms in this sequence has exceed $c$ or $-c$. Therefore, just ignore using $c, c + 1$ and so on, and continue). Therefore, the sum of any substring of length greater than $1$ must contain term $c$, which makes the value too large to be the wanted constant. SubCase 02. Polynomials of Even Degree WLOG the leading coefficient of the polynomials is positive. Consider $\min_{x \in \mathbb{N}} P(x) = M$. This must exists since $P(x)$ is positive for large enough $x$. Hence, call numbers $x < (M - 100)^{99}$ tiny. Consider the sequence \[ 0, c, 1, c+1, -1, c + 2, 2, c + 3, -2, c + 4, 3, \dots,\]where $c < x$ is a tiny number. (If eventually $c$ will be used again, this means that all terms in this sequence has exceed $c$ or $-c$. Therefore, just ignore using $c, c + 1$ and so on, and continue). Therefore, the sum of any substring of length greater than $1$ must contain term $c$, which makes the value too small to be in the range of the polynomial where $c$ is a tiny number.

We construct the required sequence if $P$ has degree $\geq 2$. Note that this implies the gaps in the range of $P$ are unbounded. (Since this is the only thing we will use, the following also works for constant polynomials). Choose $a_1$ to be any integer not in the range of $P$. Suppose at some step we have constructed the sequence $a_1,a_2, \dots a_k$ til some positive integer $k$. Let $l$ be the integer with the smallest absolute value that has not yet appeared in the sequence (preference given to positive integer). Let $S$ denote the set of sums of the form $a_i+ \cdots a_j$ where $i<j \leq k$. Due to unbounded nature of gaps there exists an integer $m$ with sufficiently large absolute value (in particular, $|m| > max \{|l|,|a_1|,\dots |a_k| \}$) such that all the numbers in the set $\{x+m | x \in S\} \cup \{x+m+l | x \in S \} \cup \{m+l \}$ lie in such a gap. Now we let $a_{k+1}=m$ and $a_{k+2}=l$. Continuing this way we can build the entire sequence, and it is easy to see that this satisfies the conditions. For the sake of completion, let me also provide a proof that linear polynomials work. Let $P(x)=ax+b$ and let $a_1, a_2 ,\dots$ be the given sequence. Clearly there exist infinitely many indices $i_1 < i_2 \cdots $ such that $a_{i_j} \equiv b \pmod a$. Let $S_j = a_1 + a_2 + \cdots + a_{i_j}$. By PHP, there clearly exist $k<m$ such that $S_k \equiv S_m \pmod a$ $$\implies \ \ a_{i_k+1} + \cdots + a_{i_m} \equiv 0 \pmod a$$$$\implies \ \ a_{i_k}+ \cdots + a_{i_m} \equiv b \pmod a$$So we have found the required run.

We prove that no $P$ with $\deg(P) \ge 2$ satisfy the condition by constructing a sequence whose contiguous subsequence sums avoid the values of $P$. The idea is to pick every other term of the sequence to be huge and pick every other term to be small to cover $\mathbb{Z}$. These small numbers will cover the integers in the order $0, 1, -1, 2, -2, 3, -3, \ldots$, except they skip all of the huge terms which have been already chosen. Here's the algortihm. First pick a huge positive integer $a_1$ which is not a value of $P$. We then pick $a_2 = 0$, a "small" number. Now, assume we have already chosen $a_1, a_2, \ldots , a_{2n-1}, a_{2n}$. Let $a_{2n + 2}$ be the first number in the sequence $0, 1, -1, 2, -2, 3, -3, \ldots$ which is not already in the sequence. We pick $a_{2n+1}$ to be a huge positive integer such that there are no values of $P$ in the interval \begin{align*} [a_{2n+1} - (|a_1| + |a_2| + \ldots + |a_{2n}| + |a_{2n+2}| + 100), a_{2n+1} + |a_1| + |a_2| + \ldots + |a_{2n}| + |a_{2n+2}| + 100] \end{align*}(and $a_{2n+1} \neq a_{2n+2}$). It now follows that no contiguous subsequence ending at either $a_{2n+1}$ or $a_{2n+2}$ is a value of $P$, so this construction really works.

Solved with goodbear, Th3Numb3rThr33. The answer is all linear polynomials. Proof of sufficiency: For $P(x)=cx+b$, take $S$ the set of residues modulo $c$ that occur infinitely often in $(s_i)$. If, for contradiction, $P$ fails, then $S$ has no terms differing by $b\pmod c$. Eventually all terms of $(s_i)_{i\ge M}$ are in $S$ modulo $c$, so $a_i=s_i-s_{i-1}$ is never $b\pmod c$ for $i>M$, contradiction. Proof of necessity: We just choose a suitable sequence $(a_i)$ that fails: For $\deg P$ odd, take $0$, $P($大$)+1$, $1$, $P($更大$)$，$-1$, $P($非常大$)$, $2$, $\ldots$. For $\deg P$ even, without loss of generality $P$ has positive leading coefficient and is bounded below by $M$, and take $0$, 小, $1$, 更小, $-1$, 非常小, $\ldots$, where even-indexed terms are all less than $M$.

does anyone have the marking scheme of this problem?

Does anyone know if we can apply generating functions in this problem?

How tying works.

Case 1: $P$ is linear, say $ax+b$ Look at the sequence modulo $a$, and notice that $P$ obtains any value that is $b$ $\text{mod}$ $a$. Denote $s_i=a_1+a_2+...+a_i$. Then, assume $s_j-s_i\neq b$ $\text{mod}$ $a$ for $j\geq i+1$. Then the sequence obtains $1$ less possible value mod $a$ when being big enough. Doing this sufficiently many times $s_i$ is eventually constant $\text{mod}$ $a$, but not all sufficiently large $a_i$'s are $0$ $\text{mod}$ $a$, contradiction. So all linear $P$ work Case 2: $degP \geq 2$, WLOG $P(x)>0$ for sufficiently large $x$ We construct the sequence by a sort of induction. Say $a_1, a_2, ..., a_n$ satisfied the given condition, where the $a_i$'s are distinct integers. Now take any integer $k$, and we can "fit it in" the sequence. Take $a_{n+1}=M$ and $a_{n+2}=k$, and denote $s_i = a_i+a_{i+1}+...+a_n+k$ for $1\leq i\leq n$. To maintain the problem condition, we only have to have $M+s_i$ and $M+k$ to not be a value of $P$ (over all $i\leq n$). We can make a set $S$ of values $P$ does not obtain, and taking advantage of the degree of $P$, there exist arbitrarily large sequences of consecutive numbers in $S$, just take $M$ in the middle of such a sequence so that by adding $s_i$'s and $k$ we still get a number inside that sequence (not entirely rigorous explanation, more on the intuitive side ) This way, we extend the sequence and by adding the smallest $k$ (both positive and negative) to get the bijective-kind-of sequence described in the problem condition, which implies that non-linear polynomials don't work (skipping the constant ones because they are trivial)

Isnt this problem just asking us to find all surjective polinomials from Z to Z? Assuming P non surjective with the property then let n be an integer not in the image of P then pick the sequence a1=n a2=0 and all other numbers are whatever you wish then n belongs to the image of P contradiction

Remark: Upon revisiting this problem after half a year, I realize that this isn't bad at all. I claim that our answers are all linears $P(x) = mx + n$. It suffices to show that for any infinite sequence $a_1, a_2, \ldots $ that contains every integer once, we may find some $a_i + a_{i+1} + \ldots + a_j \equiv n \pmod m$. Consider partial sums $S_1 = a_1, S_2 = a_1 + a_2,$ and so on. Since in the sequence every integer appears once, there are infinitely many indices $i_k$ such that $a_{i_k} \equiv n \pmod m$. In $S_{i_1}, S_{i_2}, \ldots$, which is an infinite sequence, we may always find $S_{i_k} \equiv S_{i_{\ell}} \pmod m$ by Pigeonhole hence\[a_{i_{k} + 1} + \ldots + a_{i_{\ell}} \equiv 0 \pmod m \implies a_{i_k} + \ldots + a_{i_{\ell}} \equiv a_{i_k} \equiv n \pmod m\]works for all sequences $a_i$. It remains to find a counterexample for all $P$ with $\text{deg} P \geq 2$. We want to choose every other number to be large and every other number to be small. Choose $a_1$ to be a large value that $P$ does not hit and $a_2 = 0$. At any point when we already have $a_1 \to a_{2k}$, we choose $a_{2k+2}$ to be the next term in $0, 1, -1, 2, -2, \ldots$ not already covered by $a_1 \to a_{2n}$ and $a_{2n+1}$ to be a large number such that $P$ does not hit any value in $[a_{2n+1} - A, a_{2n+1} + A]$ where $A = (|a_1| + \ldots + |a_{2n}|) + |a_{2n+2}|$. Then any block ending in $a_{2n+1}$ or $a_{2n+2}$ is hit by $P$ and doing this inductively, we are done. $\blacksquare$

The answer is all $f(x)=ax+b$, where $a,b\in\mathbb Z$. We first show that for every linear polynomial such number exists, if $a=0$ it is obvious. Otherwise, for each positive integer $j$ defines $$S_j=\{a_i+...+a_j\pmod a:i< j\}$$Notice that since $S_{j}=(a_{j}+S_{j-1})\cup \{a_j+a_{j-1}\}$, hence $|S_j|\geq |S_{j-1}|$. Moreover, if $|S_j|=a$ then we are done, otherwise, for sufficiently large $j$ we have $|S_j|=|S_{j-1}|$. Therefore, $$a_j+a_{j-1}\in a_j+S_{j-1}$$$$a_j\in S_{j-1}$$This implies for sufficiently large $j$ we have $a_{j}\in S_{j-1}$. Therefore, pick $a_j\equiv b\pmod a$ then we are done. Now suppose $\deg f\geq 2$. Consider the set $$\{a:a=f(b)\text{for some $b\in\mathbb Z$}: a>0\}$$This set is countable and bounded below by zero, hence we can denote its elements by $a_1<a_2<...<a_n<...$. Suppose $b$ is an integer and $T$ is a set, we say that the pair $(b,T)$ is good if there exists some integer $m$ such that $$a_m<b+\min T<b+\max T<a_{m+1}$$ Then notice that $a_{m+1}-a_m$ is unbounded so for finite set $T$ there exists infinitely many $k$ such that $k,T$ is good. We construct a sequence as follows: Firstly let $c_1=1$. Afterwards, choose a sufficiently large number $k$ such that $k,\{1\}$ is good and let $c_2=k$. Now suppose we have picked $c_1,...,c_{2n}$ we will let $c_{2n+2}$ be the number with the smallest absolute value that is not in $c_1,...,c_{2n}$. Now we let $$S=\{c_i+...+c_{2n}:i\leq 2n\}\cup \{c_i+...+c_{2n}+c_{2n+2}:i\leq 2n\}$$Let $k$ be a number such that $k,S$ is good then we can pick $c_{2n+1}=k$. It is easy to see that every integer appears in $\{c_n\}$ but no such pairs $(i,j)$ exists, this completes the proof.

The answer is all linear polynomials. Suppose $P$ has degree $> 1$. I will inductively create a sequence with no partial sum in the range of $P$. Suppose we've added $a_1, a_2, \cdots, a_{k}$ so far. Let $m$ be the number with smallest absolute value that has not been added into the sequence yet (if both $m$ and $-m$, then pick arbitrary one). We commit to adding $m$ as $a_{k+2}$ and wish to choose a suitable $a_{k+1}$. There are $2k+1$ values $v$ such that $a_{k+1} + v$ must not be in the range of $P$. Let these $2k+1$ values be inside an interval $[a,b]$. Then we just want to find a consecutive set of $b-a$ numbers not in the range of $P$. But since $P$ has degree $\ge 2$, we can indeed do this (and we have infinite choices, so $a_{k+1}$ can be chosen distinct from the previous ones). Suppose $P$ was constant, just alternate between a big term and a small term, which clearly works. So now it suffices to show linears work. Suppose $P(x) = ax+b$. Look at the sums $a_1, a_1 + a_2, \cdots, a_1 + a_2 + \cdots +$, let $S_k = a_1 + a_2 + \cdots + a_k$. We want some two nonconsecutive values of $S$ these differ by $b \pmod a$. Consider all integers that are $b \pmod a$ and pick one, say $a_j$. We have that $S_{j-1}, S_j$ differ by $b$, so neither of these two can appear ever again as a value of $S$. So move forward, find another value that is $b \pmod a$ and repeat. Since there are only finitely many residues mod $a$, this is a contradiction, so indeed we can find two values $S_i, S_j$ with $j-i>1$ such that $a | S_j - S_i - b$, as desired. $\blacksquare$

Answer is all linear. Constant is obviously dead. For degree > 1, assume it is not possible to add a integer $c$, then simply go to a location where the poly is sufficiently sparse beyond all current sum conditions, add the big number, then add the c after the big number. Repeat to construct ever integer. For linear, simply notice if it is $ax+b$ that when we take partial sums, the step up from $x$ to $x+b$ occurs infinitely many times, so for some residue mod $a$, the step-up is completely at least twice. Simply take the larger of the higher step-up minus the smaller of the lower one to finish.

First we show all linear polynomials work. Notice how if $P(x)=ax+b$ we just need to show we can have $i,j$ such that $a_i+a_{i+1}+ \dots + a_j \equiv b \mod a.$ So we define $s_i=a_1+\dots + a_i,$ and we desire to show that we can have $s_j-s_i\equiv b \mod a.$ In order to do this we consider the pairs $(s_1,s_2),(s_2,s_3),\dots (s_i,s_{i+1}), \dots.$ Observe how there will be some pair $(s_j,s_{j+1})$ for which $s_{j+1}-s_j\equiv b \mod a,$ as we have that $s_{j+1}-s_j=a_j.$ In fact there are infinitely many of such pairs, so if we look at them modulo $a,$ then by $PHP$ two will eventually be the same. So we have that there exist $m,n$ for which $m>n,$ $s_m\equiv s_n$ and $s_{m+1}\equiv s_{n+1}$ modulo $a.$ So $b\equiv s_{m+1}-s_m\equiv s_{m+1}-s_n,$ which ends the proof. Now we need to show that all polynomials with $degP\geq 2$ don't work, so we'll greedily construct a sequence for which the statement is false. Assume we have a sequence $a_1,a_2,\dots a_n$ for which there is no sum equal to $P(x)$ for any $x.$ Notice how as $degP\geq 2$ then $P(x+1)-P(x)>N$ has solution for all $N\in\mathbb{N},$ so we choose $a_{n+1}=\lfloor\frac{P(x)+P(x+1)}{2}\rfloor,$ such that $P(x+1)-P(x)>> \vert a_1 \vert +\dots + \vert a_n \vert.$ After that we choose $a_{n+2}$ different from all the previous $a_i's$ with $\vert a_{n+1}\vert$ minimum. Doing this infinitely we guarantee that every integer is on the sequence, but all sums always fall between $P(x)$ and $P(x+1)$ for some $x.$

The answer is linear polynomials only. Proof that linear polynomials work: Suppose $P(x)=cx+d$. For every $i \geq 1$ let $S_i$ be the set of modulo-$c$ residues $\{a_i,a_i+a_{i-1},\ldots,a_i+\cdots+a_1\}$. Note that $S_{i+1}=(S_i+a_{i+1}) \cup \{a_{i+1}\}$. This immediately implies $|S_{i+1}| \geq |S_i|$, and since $|S_i| \leq c$ for all $i$ we find that $|S_i|$ is eventually constant, so we must have $0 \in S_i$ for all sufficiently large $i$. Some large $i$ must exist with $a_{i+1} \equiv d \pmod{c}$, whence some subsequence ending at $a_{i+1}$ sums to $d \pmod{c}$. $\blacksquare$ Proof that no other polynomials work: For constant polynomials $P(x)=c$, we inductively construct a sequence: let $x_{2i}$ be the smallest number in absolute value (break ties arbitrarily) which has not yet been placed into the sequence. Then pick $x_{2i-1}$ to be massive and positive (and not yet appearing in the sequence) such that any subsequence ending in $x_{2i-1}$ or $x_{2i}$ is massive compared to $c$, which is certainly possible. For other polynomials, for any $d>0$ we can find infinitely many intervals $I:=[n,n+d]$ (where $n$ is an integer) such that the range of $P$ over $\mathbb{Z}$ does not intersect with $I$. This basically allows us to repeat the previous construction: let $x_{2i}$ be the smallest number in absolute value not yet already in the sequence. Then find some massive interval very far away and pick $x_{2i-1}$ somewhere inside it so that any subsequence ending in $x_{2i-1}$ or $x_{2i}$ falls in this interval, which is also possible. This finishes the problem. $\blacksquare$

The answer is all linear polynomials. First suppose $P(x)=mx+d$ (with $m$ nonzero). Break the sequence into blocks such that each block begins with a term equivalent to $d\pmod{m}$ (we may discard the first few $a_i$ but this is irrelevant). Since contiguous subsequences are differences of prefix sums, by PHP some contiguous subsequence of blocks sums to $0\pmod{m}$. Take this subsequence along with the term immediately after it, which we know is equivalent to $d\pmod{m}$. Now suppose $P$ is constant or has degree $\ge 2$. All we need is that $\text{im}P$ contains arbitrarily large gaps. We will inductively construct $\{a_n\}$, starting with $a_1=0$. For each $i\ge 1$, let $x$ be an integer of minimal magnitude that hasn't yet appeared in the sequence, let $S=|x|+|a_{2i-1}|+|a_{2i-2}|+\dots+|a_1|$, and choose a massive $N$ such that $[N-x,N+x]$ is disjoint from $\text{im}P$ and $N$ is not already in the sequence. Then set $a_{2i}=N$ and $a_{2i+1}=x$.