Можно ли определить четность суммы переменных?

[Pamparam]

Имеется набор n переменных $x_1, x_2...x_n$, каждая из которых принимает значение 0, либо 1. Можно ли построить многочлен от этих переменных, значение которого равно 0 в случае, когда $x_1 + x_2...+x_n$ четно, либо 1 в противном случае?

В очевидном варианте количество слагаемых многочлена $2^n-1$, что неприемлемо.

P.S.
Модератор поместил тему в карантин по причине отстуствия собственных содержательных попыток решения данной задачи. Увы, с содержательными попытками не очень в силу отсутствия профильного образования. Единственное, что приходит на ум -
сумму каждой пары слагаемых (вне зависимости от их значения) можно привести к 0 или 1, используя формулу $a + b - 2ab$. Но это приводит к тому, что общее количество слагаемых в конечном многочлене будет равно $2^n-1$.

[Pphantom]

Тема перемещена из форума «Математика (общие вопросы)» в форум «Карантин»
по следующим причинам:

- отсутствуют собственные содержательные попытки решения задачи.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Pphantom]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

-- 08.11.2020, 16:00 --

Заодно стоит уж дописать условие полностью (чтобы не возникали результаты, "неприемлемость" которых не оговорена в исходной постановке задачи).

[kotenok gav]

А почему нельзя сконструировать с помощью вашего $x+y-2xy$ (замечу, что это просто $(x-y)^2$) многочлен для нескольких переменных? Скажем, вот для четырёх ($x$, $y$, $z$, $t$): $(x+y-2xy)+(z+t-2zt)-2(x+y-2xy)(z+t-2zt)$.

[Pamparam]

kotenok gav в сообщении #1491203 писал(а):

А почему нельзя сконструировать

Можно, но при большом n количество слагаемых будет слишком большим, там экспоненциальный рост, поэтому и неприемлемо.

[Xaositect]

Есть известный результат, что любой такой многочлен должен иметь степень $n$ и не менее $2^n - 1$ слагаемых. Доказано в книге Минского-Паперта о персептронах.
Но есть компактные представления таких многочленов, напр. $\frac12\left(1 - \prod_i (1 - 2x_i)\right)$

[vpb]

Xaositect в сообщении #1491210 писал(а):

Доказано в книге Минского-Паперта о персептронах.

Только по-русски пишут "Пейперт":
М.Минский, С.Пейперт, Персептроны.