Only one person at MOP got a 7 on this problem.

how so good The answer is $\boxed{\text{yes}}$. Lemma 1. Fibonacci numbers are surjective modulo $9$. Proof. Omitted. $\blacksquare$ Lemma 2. Let $n$ be the degree of $P$. The exists a (cubic) polynomial $Q$ such that $P(Q(x))$ has $x^{3n-1}$ as its only negative coefficient. Proof. The key is that $Q(x)=x^3+x+1$ almost works for $P(x)=x^n$, except the $x^{3n-1}$ coefficient is $0$. Take large positive constants $C$ and $D$, and consider $$Q(x)=C(Dx^3-x^2+Dx+D).$$With $C$ sufficiently big, only the $x^n$ term of $P$ matters, so $Q$ works. $\blacksquare$ Now, for all sufficiently large $k$, consider $P(Q(10^k))$. The coefficients will all be isolated, besides the $x^{3n-1}$ term. As we increase $k$, we increase the decimal digit sum of $|P(Q(10^k))|$ by $9$, so there are a fixed $b$ and $c$ such that all numbers of the form $9a+b$ with $a\ge c$ are achievable. Since Fibonacci numbers are periodic, we are done by Lemma 1. $\square$

The answer is yes; for every nonconstant $P$ one can find a positive integer $n$ so that the sum of the digits of $\lvert P(n)\rvert$ is a Fibonacci number. Let $s(n)$ be the sum of the digits of $n$. Lemma. There exist arbitrarily large Fibonacci numbers $F_n$ so that $F_n \equiv k \pmod 9$ for all $k \in \mathbb{Z}$. Proof. Bash. $\square$ WLOG the leading coefficient of $P$ is positive. We now prove the problem assuming that $P$ has even degree $d > 0$, and and all coefficients of $P$ are positive (in particular, none are zero). If $P$ is not of this form but $P$ is non-constant, then $Q(n) = P(a(n^2+n+1))$ is for large enough $a$, which solves the problem upon applying the result to $Q$. Let $P(n) = a_dn^d + a_{d-1}n^{d-1} + \cdots + a_0$. We make the following definitions, where $N$ and $q$ are as-of-now undetermined (but imagine that $N \gg q \gg 1$): \begin{align*} M &= (d-1)N-q \\ t &= 10^N - 1 \\ T &= 10^M t \end{align*}We now consider the quantity \[P(T) = \sum_{k=0}^d a_k10^{kM}t^k.\]For $k < d-1$, $a_kt^k \leq a_k10^{Nk} < 10^M$ for sufficiently large $N$. So \[s(P(T)) = \sum_{k=0}^{d-2}s(a_kt^k) + s\mathopen{}\left(a_{d-1}t^{d-1} + a_dt^d10^M\right)\mathclose{}.\] Consider \[a_kt^k = a_k10^{kN} - \binom{k}{1}a_k10^{(k-1)N} + \cdots \mp \binom{k}{k-1}a_k10^{N} \pm a_k.\]If $N$ is large enough, this should separate all the terms into $k+1$ groups of random digits separated by stretches of 0's and 9's. Specifically, since there are $\lceil\tfrac{k}{2}\rceil$ negative terms, increasing $N$ increases this digit sum by $9\lceil\tfrac{k}{2}\rceil$. Note that this has no dependence on $q$. The last term is similar. Since $d$ is even, we have \[a_{d-1}t^{d-1} + a_dt^d10^M = \begin{multlined}[t]a_d10^{(2d-1)N-q} - \cdots - \binom{d}{d-1}a_d10^{dN-q} + a_{d-1}10^{(d-1)N} \\ + a_d10^{(d-1)N-q} - \binom{d-1}{1}a_{d-1}10^{(d-2)N} + \cdots - a_{d-1}.\end{multlined}\]If $q$ is sufficiently large and $N$ is much larger than $q$ (specifically we need both $10^q$ and $10^{N-q}$ to exceed the coefficients), this should again separate out into terms. However, here, there are $\lceil\tfrac{d}{2}\rceil + \lceil\tfrac{d-1}{2}\rceil$ negative terms, where all but one are preceded by a "gap" of $10^N$ and the last is preceded by a gap of $10^{N-q}$. Therefore, increasing $N$ increases the digit sum by $9(\lceil\tfrac{d}{2}\rceil + \lceil\tfrac{d-1}{2}\rceil)$, while increasing $q$ decreases it by exactly $9$. To recap, increasing $q$ by $1$ decreases the digit sum by $9$, while increasing $N$ by $1$ increases the digit sum by $9p$, where $p = \textstyle\sum_{k=0}^{d} \lceil\tfrac{k}{2}\rceil$. Notice that for this construction to work, $q$ must still be small compared to $N$, so we can't just move around $q$ that much. However, we can do the following: Pick $N \gg q \gg 1$ and consider $K = s(P(T))$. Find some $F_n > K$ so that $F_n \equiv K \pmod 9$. Increase $N$ until $0\leq K-F_n<9p$. Increase $q$ at most $p$ times (possible if $N$ is sufficiently large) until $K = F_n$. Hence we have made the digit sum of $P(T)$ equal to a Fibonacci number, as desired.

numbersandnumbers wrote: Lemma. There exist arbitrarily large Fibonacci numbers $F_n$ so that $F_n \equiv k \pmod 9$ for all $k \in \mathbb{Z}$. Proof. Bash. $\square$ Dear numbersandnumbers, how to check the "arbitrarily large" part? It seem pretty difficult to bash up to arbitrarily large Fibonacci number...

Perhaps using fibonacci mod 9 list? ($1,1,2,3,5,8,4,3,7,1,8,0,8,...$)

Muriatic wrote: numbersandnumbers wrote: Lemma. There exist arbitrarily large Fibonacci numbers $F_n$ so that $F_n \equiv k \pmod 9$ for all $k \in \mathbb{Z}$. Proof. Bash. $\square$ Dear numbersandnumbers, how to check the "arbitrarily large" part? It seem pretty difficult to bash up to arbitrarily large Fibonacci number... Claim: There are infinitely many Fibonacci numbers in each residue class modulo $9$. Proof. Note the Fibonacci sequence is periodic modulo $9$ (indeed it is periodic modulo any integer). Moreover (allowing negative indices), \begin{align*} F_{0} = 0 &\equiv 0 \pmod 9 \\ F_{1} = 1 &\equiv 1 \pmod 9 \\ F_{3} = 2 &\equiv 2 \pmod 9 \\ F_{4} = 3 &\equiv 3 \pmod 9 \\ F_{7} = 13 &\equiv 4 \pmod 9 \\ F_{5} = 5 &\equiv 5 \pmod 9 \\ F_{-4} = -3 &\equiv 6 \pmod 9 \\ F_{9} = 34 &\equiv 7 \pmod 9 \\ F_{6} = 8 &\equiv 8 \pmod 9. \end{align*}$\blacksquare$ In bases $b$ for which surjectivity modulo $b-1$ fails, the problem is false. For example, $P(x) = 11x+4$ will avoid all Fibonacci numbers if we take sum of digits in base $12$, since its base $12$ sum is necessarily $4 \pmod{11}$, hence not a Fibonacci number.

How much progress was needed to earn a point of partial? I noticed that there were only six 1s and one 2 Specifically, would this be enough: - Showing that there exists an arbitrarily large Fibonacci number for each residue mod 9 (admittedly trivial; just bash it out to $F_{23}$) - Proving that for $P(n)$ with $d$ negative coefficients, there exists a sufficiently large $M$ such that $S(|P(10^{m+1})|) = S(|P(10^m)|)+9d$ for all integers $m>M$ - Attempting to adjust $d$ by trying $P(n \pm c)$ and the like but (unfortunately ) not getting much of anywhere

Currently one of my most favorite problems! The answer is $\textbf{yes}$. Now, suppose otherwise, we will prove the following statement: Quote: For any nonconstant polynomial $P(x) \in \mathbb{Z}[x]$, there exists a positive integer $n$ such that \[ S(|P(n)|) = F_k \]for some positive integer $k$. $\textbf{Claim 01.}$ The Fibonacci numbers are surjective modulo $9$ and in fact, there are infinitely many Fibonacci numbers with each residue modulo $9$. $\textit{Proof.}$ It's enough to prove the existence of such Fibonacci numbers in each residue modulo $9$, since it is well known that Fibonacci numbers are periodic modulo $n$. By allowing negative Fibonacci, $F_{k - 1} = F_{k + 1} - F_k$, we would have \[ F_0 = 0 \equiv 0 \ (\text{mod} \ 9) \]\[ F_1 = 1 \equiv 1 \ (\text{mod} \ 9) \]\[ F_3 = 2 \equiv 2 \ (\text{mod} \ 9) \]\[ F_4 = 3 \equiv 3 \ (\text{mod} \ 9) \]\[ F_7 = 13 \equiv 4 \ (\text{mod} \ 9) \]\[ F_5 = 5 \equiv 5 \ (\text{mod} \ 9) \]\[ F_{-4} = -3 \equiv 6 \ (\text{mod} \ 9) \]\[ F_{9} = 34 \equiv 7 \ (\text{mod} \ 9) \]\[ F_{-2} = -1 \equiv 8 \ (\text{mod} \ 9) \] We could first WLOG that $a_n > 0$. Define a polynomial of degree $n$ as $\textit{nikolai}$ if and only if it has nonnegative coefficients of $x^k$ for $k = 0, 1, 2, \dots, n - 2, n$ but has a negative coefficient of $x^{n - 1}$. $\textbf{Claim 02.}$ For any nonconstant polynomial $P(x) \in \mathbb{Z}[x]$, there exists a polynomial $R(x) \in \mathbb{Z}[x]$ such that $P(R(x))$ is $\textit{nikolai}$. $\textit{Proof.}$ We will first ignore the condition of $R(x) \in \mathbb{Z}[x]$. Suppose we have a polynomial \[ P(x) = a_n x^n + a_{n - 1} x^{n - 1} + \dots + a_1 x + a_0 \]We wanted \[ P(R(x)) = a_n R(x)^n + a_{n - 1} R(x)^{n - 1} + \dots + a_1 R(x) + a_0 \]to be $\textit{nikolai}$. Suppose that $a_i R(x)^i$ is $\textit{nikolai}$ for each $i = 0, 1, \dots, $. To ensure that the coefficient of each $x^k$ is positive, we could consider $C \cdot R(x)$ instead of $R(x)$ with a large constant $C > 10^{100} \cdot \max r_i^{\deg R}$ where $r_i$s are coefficients of $R(x)$. We could check easily that this works. Now, it suffices to prove that there exists a polynomial $R(x) \in \mathbb{Q}[x]$ such that $a_i R(x)^{i}$ is $\textit{nikolai}$. We could easily check that $R(x) = (x^3 - \varepsilon x^2 + x + 1)$ satisfy the requirement where $\varepsilon \to 0$, and $\varepsilon \in \mathbb{Q}$. Therefore, we could take $\varepsilon = \frac{1}{D}$ with $D$ a large constant $D > 10^{10} \cdot \deg R $ Since we want $C \cdot R(x)$ to be an integer coefficient polynomial, then we could take $D | C$. $\textbf{Claim 03.}$ All $\textit{nikolai}$ polynomials satisfy the given problem's criteria. $\textit{Proof.}$ Notice that $P(R(x))$ is $\textit{nikolai}$ as stated. Let \[ P(R(x)) = b_n x^n - b_{n - 1} x^{n - 1} + \dots + b_1 x + b_0 \]where $b_i \ge 0$ for $0 \le i \le n -2$ and $b_{n - 1}, b_n > 0$. Now, consider $P(R(10^k))$ for a large integer $k > 10^{572} \cdot \max \{ b_1, b_2, \dots, b_n \}$. Therefore, the decimal expansion of $P(R(10^k))$ consists of concatenation of $b_0, b_1, b_2, \dots, b_{n - 2}$ with some spacing of "0"s and $10^k \cdot b_n - b_{n - 1}$ in front, where as $k$ increases, the number of "9" will increase. Therefore, $S(P(R(10^k))$ is eventually surjective at all points $\ge c$ for a constant $c$ which is unique modulo $9$. Combining this and $\textbf{Claim 01.}$ finishes the problem.

Solved with rama1728. Yes, it must be. Fix $P(n) = a_1x^{k} + a_2x^{k-1} + \dots + a_{k+1}.$ Suppose WLOG $a_1 > 0.$ Define a polynomial $Q(n) = a(bn^3-n^2+bn+b)$ for positive integers $a,b.$ By setting $b$ very large, we guarantee the expansion of $(bn^3-n^2+bn+b)^{k},$ and thus $a_1(Q(n))^k,$ have all coefficients positive except the $x^{3k-1}$ term which is negative. By setting $a$ very large, the coefficients in $a_1(Q(n))^k$'s expansion grow arbitrarily large in proportion to any coefficient in the expansion of any other $a_i (Q(n))^{k+1-i},$ implying the $x^i$ term of $P(Q(n))$ is positive iff the $x^i$ term of $a_1(Q(n))^k$ is positive. So we let $P(Q(n))$ have all coefficients positive except the $x^{3k-1}$ term which is negative. Let $$P(Q(n)) = b_1x^{3k} - b_2x^{3k-1} + \dots + b_{3k+1}$$ for positive integers $b_1, b_2, \dots b_{3k+1}.$ For all large enough $e,$ $P(Q(10^e))$ can be read as $b_1-1,$ then $10^{e} - b_2,$ then $b_3$ preceded by leading zeros, then $b_4$ preceded by leading zeros, and so on. Note $10^{e+1} - b_2$ is just $10^{e} - b_2$ with a $9$ tacked on, and zero digits don't affect sum of digits. Thus, the sum of digits of $P(Q(10^e))$ is $9$ less than $P(Q(10^{e+1}))$ for all large enough $e.$ It is easily verified that there are an infinite number of Fibonacci numbers congruent to any residue $\pmod{9}$ which finishes. $\blacksquare$

Let $P(x) = \sum_{i=0}^d a_ix^i$ We will show that the Fibonacci sequence $F_n$ has infinitely many $k$ so that $F_k \equiv m\pmod{p}$ for any $m$. Note that $F_1 \equiv 1$, $F_3 \equiv 2$, $F_4 \equiv 3$, $F_5 \equiv 5$, $F_6 \equiv 8$, $F_7 \equiv 4$, $F_9 \equiv 7$, $F_{11} \equiv 8$, $F_{12} \equiv 0 \pmod{9}$ so $F_n$ is surjective modulo $9$. Then it is well known that $F_n$ is periodic modulo $m$ for any $m$, so our claim is proven. Then let $Q(x) = \sum_{i=0}^{3} b_ix^i$. We will show that there is some choice of $b_i$ so that $P(Q(x))$ has all positive coefficients, except for the coefficient of $x^{3d-1}$. This is done by letting $b_3$ be extremely large and letting $b_2 = -1, b_1 = b_0 = 0$. This works since $b_3$ is sufficiently large enough that any coefficients of $P(Q(x))$ that are partially $b_3^ab_1^bb_0^c$ are positive. All coefficients can be written like this except for $x^{3d-1}$, which is clearly negative. Now plug in $x = 10^e$ for sufficiently large $e$, so that $P(Q(x))$ is are the coefficients of $P(Q(x))$ strung together by zeroes, with the exception of the coefficient of $x^{3d-1}$ since it is negative. We get $P(Q(x)) = \overline{ABCD\dots 999 \dots 00 \dots EFGH\dots}$. The number of nines trailing $ABCD\dots$ increases by exactly one if we plug in $10^{e+1}$ instead, so repeating this combined with the fact that there are infinitely many Fibonacci numbers modulo $m \pmod{9}$ gives us that the sum of digits of $P(Q(x))$ will reach a Fibonacci number. So $P(x)$ must be constant.