Пусть $%P(x_1,x_2,\ldots,x_n)$% - полином $%n$% вещественных переменных. При каких условиях на коэффициенты этого полинома он принимает значения только 0 или 1 на наборах, состоящих из нулей и единиц? То есть более формально: если $%x_k \in \{0,1\}$% $%\forall k=\overline{1,n}$%, то $%P(x_1,x_2,\ldots,x_n)\in \{0,1\}$% (то есть либо $%P(x_1,x_2,\ldots,x_n)=0$%, либо $%P(x_1,x_2,\ldots,x_n)=1$%).

Понятно, что можно рассматривать только полиномы, "свободные от степеней" переменных, то есть полиномы, которые являются суммами одночленов вида $%a_{i_{1},i_{2},\ldots, i_{m_{i}}} x_{i_{1}} x_{i_{2}} \ldots x_{i_{m_{i}}}$%, так как 0 в любой натуральной степени равен 0, а 1 в любой натуральной степени равна 1.

задан 16 Сен '17 15:19

10|600 символов нужно символов осталось
0

Можно предложить следующее индуктивное описание.

При $%n=0$% мы имеем две константы $%0$% и $%1$%. Пусть к предыдущему описанию добавляется новая переменная $%x$%. Тогда получается многочлен вида $%Ax+B$%, где $%A$%, $%B$% -- многочлены от предыдущего набора переменных. Тогда при $%x=0$% многочлен должен быть взять из предыдущего списка, а при $%x=1$% должен получиться многочлен $%C=A+B$% из предыдущего списка, в силу чего $%A=C-B$%, и мы имели дело с многочленом $%(C-B)x+B=Cx+B(1-x)$%, где упорядоченная пара $%(C,B)$% с элементами из предыдущего списка однозначно задаёт такой многочлен. Достаточно очевидно, что из условий $%C_1x+B_1(1-x)=C_2x+B_2(1-x)$% следует совпадение упорядоченных пар. Поэтому, если в прежнем списке было $%m$% многочленов, то в новом их будет $%m^2$%. Из этого следует, что от $%n$% переменных у нас получится в точности $%2^{2^n}$% многочленов.

Что касается закономерности коэффициентов, то её в "чистом" виде проследить довольно трудно. Например, из $%256$% многочленов трёх переменных появляются такие как $%4xyz+z-2yz-2xz+y-2xy+x$% или $%3xyz+z-yz-2xz+x-xy$%, если раскрыть все скобки.

При $%n=1$% получится множество $%\{0,1,x,1-x\}$%, далее при $%n=2$% возникнет множество из $%16$% многочленов, а именно, $%\{0, 1, y, x, 1-x, 1-y, y+x-xy, xy+1-y, 1-y-x+xy, -xy+1, y-2xy+x, x-xy,$%

$%xy, y-xy, 1-x+xy, 2xy+1-y-x\}$%.

Можно ещё дать такое описание: рассмотрим всевозможные произведения вида $%u_1\ldots u_n$%, где при каждом $%1\le i\le n$% либо $%y_i=x_i$%, либо $%y_i=1-x_i$%. Ясно, что таких произведений будет $%2^n$%. Теперь при каждом из них выберем коэффициент $%0$% или $%1$%, и сложим. Это даст все $%2^{2^n}$% многочленов, о которых мы говорили.

ссылка

отвечен 16 Сен '17 20:23

Большое спасибо за ответ! А что будет, если рассматривать только линейные полиномы $%P(x_1,x_2,\ldots, x_n)=a_1 x_1+a_2 x_2+\ldots+a_n x_n+b$% ?

Для $%n=2$% их будет 6 штук: $%0, 1, x, y, 1-x, 1-y$%. А сколько их будет для произвольного $%n$%? Может, здесь есть какая-то закономерность для коэффициентов $%a_1, a_2, \ldots, a_n, b$% ?

(17 Сен '17 23:08) DianaG

@DianaG: для линейных, как я понимаю, всё просто. Если бы были два члена с ненулевыми коэффициентами, то значений 0 и 1 уже бы не было (или достаточно занулить все переменных кроме x,y и воспользоваться описанием для двух переменных). Иными словами, там кроме констант будет только полиномы от одной переменной. Всего их 2n+2. То есть это 0,1,x_i,1-x_i.

(17 Сен '17 23:17) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,480
×434

задан
16 Сен '17 15:19

показан
339 раз

обновлен
17 Сен '17 23:17

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru