One approach is to assume $\deg f<n$ and then $f$ can be recovered by Lagrange's interpolation formula at the knots $0,1,\dots,n-1$ where $f$ takes values $t^j+\varepsilon_j, j=0,1,\dots,n-1, |\varepsilon_j|<1$. Using these constraints, one could get contradiction by showing $|f(n)-t^n|\ge 1$. We exploit another approach using finite differences. Suppose on the contrary $\deg f<n$. Then any finite difference $\Delta^n_h f(x) $ of order $n$ and step $h$ at a point $x$ is $0$. We'll show this is impossible. Let us estimate $\Delta_1^n f(0)$. $$\Delta_1^n f(0)=\sum_{i=0}^n (-1)^{n-i} \binom{n}{i} f(i) $$ Now, we consider two case: $n$ - even and $n$ - odd. They are similar, let first $n$ be even. \begin{align*}\Delta_1^n f(0) &=\sum_{i \text{ is even}} \binom{n}{i} f(i) -\sum_{i \text{ is odd}} \binom{n}{i} f(i)\\ &> \sum_{i \text{ is even}} \binom{n}{i} (t^i-1) - \sum_{i\text{ is odd}} \binom{n}{i}(t^i+1)\\ &=(1-t)^n - 2^{n}\\ &\ge 2^n-2^{n}=0 \end{align*}Thus, on the one hand we got $\Delta_1^n f(0)>0$ and on the other hand $\Delta_1^nf(0)$ should be $0$ because $f(x)$ is a polynomial of degree less than $n$, contradiction. The case when $n$ is odd is absolutely similar.

I'm not sure we need the case distinction about parity: As before, the key is the identity \[\sum_{k=0}^n (-1)^k\binom{n}{k} f(k)=0\]for any polynomial $f$ of degree less than $n$. This can be viewed as either an incarnation of finite differences or of Lagrange Interpolation, it is really the same thing! Now if $f(k)=t^k-\varepsilon_k$ with $\vert \varepsilon_k\vert \le 1$ we have \[\sum_{k=0}^n \binom{n}{k}(-t)^k=\sum_{k=0}^n \binom{n}{k} (-1)^k\varepsilon_k.\]The LHS has absolute value exactly $(t-1)^n \ge 2^n$ while the RHS has absolute value less than $\sum_{k=0}^n \binom{n}{k}=2^n$ by the triangle inequality. Done.

Here is a nice bonus question: There is a polynomial of degree less than $n$ with \[P(k)=3^k-(-1)^{n-k}\]for all $k=0,1,2,\dots,n$. Can you write it down in a nice form? Also, find the polynomial $P$ of degree less than $n$ with \[P(k)=2021^k-(-1)^{n-k}2019^k\]for all $k=0,1,2,\dots,n$.

Let's induct on $n$ Suppose FTSOC that $deg\ f<n$ Let $g(x)=f(x+1)-f(x)$ we know that $deg\ g = deg\ f -1$ but $f(k) \in (t^k-1,t^k+1)$, So $$t^{k+1}+1-(t^k-1)> f(k+1)-f(k)> t^{k+1}-1-(t^k+1)$$$$\Longrightarrow 2>g(k)-t^k(t-1)>-2 \Rightarrow |g(k)-t^k(t-1)|<2$$Let $h(x)=\frac{g(x)}{t-1}\Rightarrow |h(k)-t^k|<\frac2{t-1}<1$ Then, there is a polynomial $h\in \mathbb{R}[x]$ with $deg\ h<n-1$ such that $h(k)-t^k<1, \forall k\in \{1,2,...,n-1\}$, a contradiction by our induction hypothesis! The affirmation follows by induction.

jasperE3 wrote: Given a real number $t\ge3$, suppose a polynomial $f\in\mathbb R[x]$ satisfies $$\left|f(k)-t^k\right|<1,\enspace\forall k=0,1,\ldots,n.$$Prove that $\deg f\ge n$. This also appeared in India TST 2001.