KURSCHAK 1995 Problem 2

Consider a polynomial in $n$ variables with real coefficients. We know that if every variable is $\pm1$ , the value of the polynomial is positive, or negative if the number of $-1$ 's is even, or odd, respectively. Prove that the degree of this polynomial is at least $n$ .