Taiwan IMO Selection Camp

Solution: In what follows all congruences are modulo 13. We first prove that
$$\sum_{x=0}^{12} x^k \equiv 0, \text{ for } 0 \le k < 12.$$
The case $k=0$ is easy to prove, so suppose $k>0$. Let $g$ be a primitive root modulo 13; hence $g, 2g, \dots, 12g$ is some permutation of $1, 2, \dots, 12$. Therefore
$$\sum_{x=0}^{12} x^k \equiv \sum_{x=0}^{12} (gx)^k = g^k \sum_{x=0}^{12} x^k,$$
since $g^k \ne 1$, it must be that $\sum_{x=0}^{12} x^k = 0$.

Let $S = \{(x_1, \dots, x_n) | 0 \le x_i \le 12\}$. It suffices to prove that the number of $n$-tuples $(x_1, \dots, x_n) \in S$ with $f(x_1, \dots, x_n) \ne 0$ is a multiple of 13, because $|S| = 13^n$ is a multiple of 13.

Consider the sum
$$\sum_{(x_1, \dots, x_n) \in S} (f(x_1, \dots, x_n))^{12},$$
this sum counts the number of $n$-tuples $(x_1, \dots, x_n) \in S$ with $f(x_1, \dots, x_n) \ne 0$, this is because Fermat's Little Theorem says
$$(f(x_1, \dots, x_n))^{12} \equiv \begin{cases} 1, & \text{if } f(x_1, \dots, x_n) \ne 0, \\ 0, & \text{if } f(x_1, \dots, x_n) = 0. \end{cases}$$

On the other hand we can expand $(f(x_1, \dots, x_n))^{12}$ to obtain
$$(f(x_1, \dots, x_n))^{12} = \sum_{j=1}^{N} c_j \prod_{i=1}^{n} x_i^{e_{ji}},$$
where $N, c_j, e_{ji}$ are integers. Because $f$ is a polynomial of degree less than $n$, for every $j$ we have $e_{j1} + e_{j2} + \dots + e_{jn} < 12n$, so for every $j$ there exists $i$ such that $e_{ji} < 12$. Hence we have
$$\sum_{(x_1, \dots, x_n) \in S} c_j \prod_{i=1}^{n} x_i^{e_{ji}} = c_j \prod_{i=1}^{n} \sum_{x=0}^{12} x^{e_{ji}} \equiv 0,$$
because one of the sums in the product is 0. Therefore
$$\sum_{(x_1, \dots, x_n) \in S} (f(x_1, \dots, x_n))^{12} = \sum_{(x_1, \dots, x_n) \in S} \sum_{j=1}^{N} c_j \prod_{i=1}^{n} x_i^{e_{ji}} \equiv 0,$$
hence the number of $n$-tuples $(x_1, \dots, x_n)$ such that $f(x_1, \dots, x_n) \not\equiv 0 \bmod 13$ must be a multiple of 13, as claimed.