Let $X_1, \ldots, X_n \subset \mathbb{F}_p$ be non-empty subsets, and let $P_1, \ldots, P_k \in \mathbb{F}_p\left[x_1, \ldots, x_n\right]$ be polynomials such that $$ (p-1) \sum_{i=1}^k \operatorname{deg} P_i+n<\sum_{j=1}^n\left|X_j\right| . $$ Prove that if there exists an element $s \in \prod_j X_j$ satisfying $P_1(s) = \ldots = P_k(s) = 0$, then there is at least one other solution to this system of equations in the Cartesian product $\prod_j X_j$.
To do that, the Combinatorial Nullstellensatz should be useful: Let $k$ be a field, and let $f \in k[x_1, \ldots, x_n]$ be a polynomial of degree $\sum_{i=1}^{n} t_i$ for some $t_i \geq 0$ with $[\prod_{i=1}^{n} {x_i}^{t_i}]f\neq 0$ (the coefficient of the monomial $x_1^{t_1}\cdots x_n^{t_n}$ in $f$ is non-zero). If $A_1, \ldots, A_n \subset k$ are finite sets such that $|A_i| > t_i$ for all $i$, then there exists $(a_1, \ldots, a_n) \in A_1 \times \cdots \times A_n$ such that $f(a_1, \ldots, a_n) \neq 0$.
What is a good construction for this $f$? If I let $f(x_1, \ldots, x_n) := \prod_{i=1}^{k} \left(P_i(x_1, \ldots, x_n) - P_i(s_1, \ldots, s_n)\right)$, the degree of $f$ is $\sum_{i=1}^{k} \operatorname{deg} P_i$. Is it true that the monomial $x_1^{t_1}\cdots x_n^{t_n}$ is present in $f$ with a non-zero coefficient if $t_i := \operatorname{deg} P_i$ for some $i$?