, 2019

Solution:

A tricky $7$-tiny polynomial takes the form
$$\left(c_{6} x^{6}+\ldots+c_{1} x+c_{0}\right)(x-4)$$
For each fixed value of $k$, $c_{k}-4 c_{k+1}$ should lie in $[-7,7]$, so if we fix $c_{k}$, there are around $15 / 4$ ways of choosing $c_{k+1}$. Therefore if we pick $c_{0}, \ldots, c_{6}$ in this order, there should be around $(15 / 4)^{7}$ tricky $7$-tiny polynomials.

A $1$-tiny polynomial takes the form $\varepsilon_{6} x^{7}+\cdots+\varepsilon_{1} x+\varepsilon_{0}$ with $\varepsilon_{i} \in\{-1,0,+1\}$, so there are $3^{8}$ $1$-tiny polynomials.

A nearly tricky $7$-tiny polynomial $P$ takes the form $Q+T$ where $Q$ is roughly a tricky $7$-tiny polynomial, and $T$ is $1$-tiny. Furthermore, there is a unique decomposition $Q+T$ because $T(4)=P(4)$ and each integer $n$ can be written in the form $\sum \varepsilon_{k} 4^{k}$ in at most one way. Therefore the number of nearly tricky $7$-tiny is around $(15 / 4)^{7} \cdot 3^{8} \approx 68420920$, which is worth $16$ points.

The exact answer can be found by setting up recurrences. Let $t(d, \ell)$ be the number of polynomials of degree at most $i$ of the form
$$\left(\ell x^{d-1}+c_{d-2} x^{d-2}+\cdots+c_{0}\right)(x-4)+\left(\varepsilon_{d-1} x^{d-1}+\cdots+\varepsilon_{1} x+\varepsilon_{0}\right)$$
which has integer coefficients between $-7$ and $7$ except the leading term $\ell x^{d}$. It follows that $t(0,0)=1$, $t(0, k)=0$ for all $k \neq 0$, and $t(d+1, \ell)$ can be computed as follows: for each value of $c_{d-1}$, there are $t\left(d, c_{d-1}\right)$ ways to pick $c_{d-2}, \ldots, c_{0}, \varepsilon_{d-1}, \ldots, \varepsilon_{0}$, and exactly $w\left(c_{d-1}-4 \ell\right)$ ways of picking $\varepsilon_{d}$, where $w(k)=\min (9-|k|, 3)$ for $|k| \leq 8$ and $0$ otherwise. Therefore setting $c=c_{d-1}-4 \ell$ we have
$$t(d+1, \ell)=\sum_{c=-8}^{8} t(d, c+4 \ell) w(c)$$
The number of nearly tricky $7$-tiny polynomials is simply $t(8,0)$, which can be computed to be $64912347$ using the following C code.

```
int w(int a){
if(a<-9 || a > 9) return 0;
else if(a == -8 || a == 8) return 1;
else if(a == -7 || a == 7) return 2;
else return 3;
}
int main()
{
int m=8,n=7,r=4,d,l,c,c4l;
int mid = 2 + n/r;
int b = 2*mid+1;
long int t[500] [500];
for(l=0; l<b; l++){
t[0][l] = (1 == mid) ? 1 : 0;
}
for(d=0; d<m+1; d++){
for(l=0; l<b; l++){
t[d+1][l] = 0;
for(c=-8; c<9; c++){
c4l = c + 4*(l-mid) + mid;
t[d+1][l] += (c4l >= 0 && c4l <= 2*mid) ? t[d][c4l]*w(c) : 0;
}
}
}
printf("%ld",t[8][mid]);
}