Unexpected use of polynomials in combinatorics Can someone please post some (relatively easy, say high school level) combinatorial problems which can be solved with polynomials but NOT generating functions.
Related to this post in ME.SE.
Problem:  Is it possible to weight two dice (possibly unequally) in such a way that every sum from $2$ to $12$ is equally probable?

The Answer is No.  

Comment:  I set this problem for high school students a few years back. These were students who did well at competition style problems. They found this one difficult, but were able to make very good progress on it, and arrived at the first proof entirely on their own. They got the second after the basic idea was proposed to them. It's not intended to be an easy problem and it may well be more difficult than you were looking for.

Motivating Example:  to see that you can not do this with equally weighted dice, suppose you could and let $p_i$ be the probability a given die comes up $i$.  Then $p_1^2=p_6^2=\frac 1{11}\implies p_1=p_6=\sqrt {\frac 1{11}}$ But then the probability of getting a $7$ is at least $2p_1p_6=\frac 2{11}$, a contradiction.

Direct proof (no polynomials):  Say the probabilities for the first die are $p_i$ and for the second $q_i$.  Then $p_1q_1=\frac 1{11}=p_6q_6$.  But then we can get a lower bound on the probability of throwing a $7$ as $$\text {Prob}(Sum = 7)≥p_1q_6+p_6q_1=p_1\times \frac {1}{11p_6}+p_6\times \frac {1}{11p_1}=\frac 1{11}\times \left(\frac {p_1}{p_6}+\frac {p_6}{p_1}\right)≥\frac 2{11}$$ so we reach the same contradiction as in the equally weighted case.  Here, of course, we have used the fact that $x+\frac 1x≥2$.

Proof using polynomials:  Let the $p's$ and $q's$ be as above.  Define two polynomials $$P(x)=\sum_{i=1}^6p_ix^i\quad \&amp;\quad Q(x)=\sum_{i=1}^6q_ix^i$$

Note that both $P(x), Q(x)$ are divisible by $x$ and that $P(1)=Q(1)=1$.

If the weightings were to work we'd have the product $$P(x)Q(x)=\frac 1{11}\sum_{i=2}^{12}x^i=\frac {x^2}{11}\frac {x^{11}-1}{x-1}$$

However, this is impossible.  Indeed, factoring out the factors of $x$ from $P(x),Q(x)$ we get two polynomials of degree $5$ each (noting that neither $p_6$ nor $q_6$ can be $0$).  As $5$ is odd, these must have at least one real root each...but $x^{11}-1$ has no real root other than $1$ (which is not a root of $P(x)$ nor $Q(x)$).
See Lucas's Theorem. There is one proof with groups and another with polynomials. Both are very nice. (There is a third by induction but it is pretty bad.)