Original problem

The original proposed version did not have the restriction that $a_1=1$. Below we solve this original version where we allow $a_1 \neq 1$. For a solution to the shortlist version requiring $a_1=1$, see posts below. Solution 1 First, note that $\sum_{m=1}^{n}(-1)^m\binom{n}{m}m^x = 0$ for $x = 1,\dots,n-1$, so $K = n-1$ is possible. (For a proof of the identity, consider applying the principle of inclusion-exclusion on the sets $A_i$, the number of ways of creating a string of $x$ characters from an alphabet of $n$ characters, not using the $i$th character.) Now suppose $K=n$ is possible, and $f(x) = 0$ for $x = y+1, \dots y + n$ Then $$\begin{pmatrix}1^{y+1} & \dots & n^{y+1} \\ \vdots & \ddots & \vdots \\ 1^{y+n} & \dots & n^{y+n} \end{pmatrix} \begin{pmatrix} a_1 \\ \vdots \\ a_n \end{pmatrix} = \begin{pmatrix} 0 \\ \vdots \\ 0 \end{pmatrix}$$so the above matrix is singular. Thus it's transpose is also singular, so there exist rational numbers $b_1, \dots b_n$, not all zero, such that $$\begin{pmatrix}1^{y+1} & \dots & 1^{y+n} \\ \vdots & \ddots & \vdots \\ n^{y+1} & \dots & n^{y+n} \end{pmatrix} \begin{pmatrix} b_1 \\ \vdots \\ b_n \end{pmatrix} = \begin{pmatrix} 0 \\ \vdots \\ 0 \end{pmatrix}$$hence $p(t) = \sum_{m=1}^{n}b_m t^{y+m}$ is zero for $t = 1, \dots, n$. Thus $p$ is a polynomial with roots $1, \dots, n$ as well as a root of degree $y+1$ at 0, but this is impossible as $p$ is a non-zero polynomial of degree at most $y+m$. Hence $K = n-1$ is the maximal possible value of $K$. Solution 2 For $0 \leq m \leq n-1$, begin by defining polynomials: $$ P_{m}{(y)} \coloneqq \prod\limits_{\substack{0 \leq i \leq n-1 \\ i \neq m}} \frac{y-i}{m-i} $$which have the properties: \begin{align*} \deg{P_{m}}&=n-1 \\ P_{m}{(y)}&=\begin{cases} 1 & y=m \\ 0 & y \in \left\{0,1,\ldots,m-1,m+1,\ldots,n-1\right\} \end{cases} \\ P_{m}{(n)}&=\frac{n!/(n-m)}{\left(m-(n-1)\right) \cdots \left(m-(m+1)\right) \cdot 1 \cdot 2 \cdots m}=(-1)^{n-m-1} \frac{n!}{(n-m)! \, m!}=(-1)^{n-m-1} \binom{n}{m} \end{align*}Now observe that, for $x \in \left\{1,2,\ldots,n-1\right\}$, if we define: $$ Q_{x}{(y)}\coloneqq \sum\limits_{m=0}^{n-1} m^{x} \cdot P_{m}{(y)}=\sum\limits_{m=1}^{n-1} m^{x} \cdot P_{m}{(y)} $$Then $Q_{x}{(y)}=y^{x}$ for $y \in \{0,1,\ldots,n-1\}$ and, as $\deg{Q_{x}} \leq n-1$, this means: $$ Q_{x}{(y)} \equiv y^{x} \implies n^{x}=Q_{x}{(n)}=\sum\limits_{m=1}^{n-1} m^{x} \cdot P_{m}{(n)}=\sum\limits_{m=1}^{n-1} (-1)^{n-m-1} \binom{n}{m} m^{x} $$Rearranging this, we get the identity: $$ \sum\limits_{m=1}^{n} (-1)^{n-m} \binom{n}{m} m^{x}=0 \quad \text{for} \quad x \in \left\{1,2,\ldots,n-1\right\} \quad \quad (\ast) $$Setting $a_{m}=(-1)^{n-m} \binom{n}{m}$ in the definition of $f$ from the question, we see $a_{n}=1$ and by $(\ast)$, $f(1)=f(2)=\cdots=f(n-1)=0$. Thus $K=n-1$ is possible. Next we will show that $K=n$ is not possible and thus $K=n-1$ is maximal. Assume $f(x)=f(x+1)=\cdots=f{\left(x+(n-1)\right)}=0$. We construct integers $b_{i}$ such that: $$ g(y)=\prod_{i=1}^{n-1}{(y-i)}=\sum_{j=0}^{n-1}{b_j y^{j}} $$This has the property that $g(y)=0$ for $1 \leq y \leq n-1$ and $g(n)=n!$. We now have: $$ 0=\sum_{j=0}^{n-1}{b_{j} f(x+j)}=\sum_{j=0}^{n-1}b_j \sum_{m=1}^{n}a_m m^{x+j}=\sum_{m=1}^{n} a_m m^{x} \underbrace{\sum_{j=0}^{n-1} b_j m^{j}}_{g(m)}=a_{n} n^{x} g(n)=a_n n^{x} \left(n!\right) $$Which implies $a_n=0$ giving a contradiction. Remark: It is also possible to prove the identity $(\ast)$ by applying the principle of inclusion-exclusion on the sets $A_i$, the number of ways of creating a string of $x$ characters from an alphabet of $n$ characters, not using the $i$th character using that: $$ \sum\limits_{\substack{I \subset \left\{1,\ldots,n\right\} \\ |I|=m}} \left\lvert \bigcap\limits_{i \in I} A_{i}\right\rvert=\binom{n}{m} \#\left\{\text{Strings of length }x \text{ not using characters }1,\ldots,m\right\}=\binom{n}{m} (n-m)^{x} $$And then using PIE: $$ \left\lvert A_{1} \cup \cdots \cup A_{n}\right\rvert=\sum\limits_{m=1}^{n} (-1)^{m+1} \sum\limits_{\substack{I \subset \left\{1,\ldots,n\right\} \\ |I|=m}} \left\lvert \bigcap\limits_{i \in I} A_{i}\right\rvert=\sum\limits_{m=1}^{n} (-1)^{m+1} \binom{n}{m} (n-m)^{x} $$As $x \leq n-1$, no string of length $x$ can use all the characters, thus $A_{1} \cup \cdots \cup A_{n}$ is just the set of all strings of length $x$ and hence: $$ n^x=\sum\limits_{m=1}^{n} (-1)^{m+1} \binom{n}{m} (n-m)^{x}=\sum\limits_{m=0}^{n-m} (-1)^{n-m+1} \binom{n}{n-m} m^{x} \implies (\ast) $$

Let me just add one simpler proof of $\sum_{m=1}^{n}(-1)^{n-m} \binom{n}{m}m^x=0$ for $x = 1,\dots,n-1$ from the above solution. By finite differences, for $1 \leq k<n$, we have $$0=\Delta_1^n[x^k](0)=\sum_{m=0}^n(-1)^{n-m}\binom{n}{m}m^k.$$

$K=n-1$ is not the answer, the answer is $n-2$. The construction above doesn't work because $a_1\neq 1$. Here is the official solution:

Another way to show that $n-1$ fails is to prove the kernel of the coefficient matrix has dimension 1(by making use of Vandermonde determinant). As finite difference gives an explicit solution, $a_{n}$ muse have $n$ as its denominator, thus is not an integer for $n\geq 2$