Предположим, что степень многочлена P(x_1, ..., x_n) меньше n. Тогда многочлен представим в виде: P(x_1, ..., x_n) = ∑(i_1 + ... + i_n < n) a_{i_1, ..., i_n} x_1^{i_1} ... x_n^{i_n} где суммирование ведется по всем наборам показателей i_1, ..., i_n, для которых i_1 + ... + i_n < n, и a_{i_1, ..., i_n} - коэффициенты многочлена. Рассмотрим n наборов значений переменных x_1, ..., x_n, в которых одна переменная равна 1, а остальные равны -1. Для каждого набора значение многочлена равно P(1,-1,...,-1) = a_{0,0,...,0} + a_{1,0,...,0} = a_{1,0,...,0} + a_{0,1,...,0} = ... = a_{0,0,...,1} + a_{0,0,...,2} = ... = a_{0,0,...,n-1} + a_{0,0,...,n} P(-1,1,...,-1) = a_{0,0,...,0} + a_{0,1,...,0} = a_{0,1,...,0} + a_{0,0,...,1} = ... = a_{0,0,...,n-2} + a_{0,0,...,n} = - P(1,-1,...,-1) P(-1,-1,...,1) = a_{0,0,...,0} + a_{0,0,...,1} = a_{0,0,...,1} + a_{0,0,...,2} = ... = a_{0,0,...,n-1} + a_{0,0,...,n} = P(1,-1,...,-1) P(-1,...,-1) = a_{0,0,...,0} = P(1,-1,...,-1) Второе равенство следует из того, что при переходе от одного набора переменных к другому меняется знак только для одного слагаемого многочлена. Получаем систему уравнений P(1,-1,...,-1) = A P(-1,1,...,-1) = -A P(-1,-1,...,1) = A P(-1,...,-1) = A где A - положительное число. Эта система не имеет решения, так как количество уравнений (4) больше, чем количество неизвестных коэффициентов многочлена (суммарное число мономов в многочлене меньше n). Значит, предположение о том, что степень многочлена меньше n, приводит к противоречию, и степень многочлена не меньше n.