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