2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Можно ли определить четность суммы переменных?
Сообщение08.11.2020, 15:20 


07/11/20
3
Имеется набор 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$.

 Профиль  
                  
 
 Posted automatically
Сообщение08.11.2020, 15:25 
Заслуженный участник


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

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

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

 Профиль  
                  
 
 Posted automatically
Сообщение08.11.2020, 15:57 
Заслуженный участник


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


-- 08.11.2020, 16:00 --

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

 Профиль  
                  
 
 Re: Можно ли определить четность суммы переменных?
Сообщение08.11.2020, 16:18 


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

 Профиль  
                  
 
 Re: Можно ли определить четность суммы переменных?
Сообщение08.11.2020, 16:23 


07/11/20
3
kotenok gav в сообщении #1491203 писал(а):
А почему нельзя сконструировать


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

 Профиль  
                  
 
 Re: Можно ли определить четность суммы переменных?
Сообщение08.11.2020, 16:32 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Можно ли определить четность суммы переменных?
Сообщение09.11.2020, 00:13 
Заслуженный участник


18/01/15
3224
Xaositect в сообщении #1491210 писал(а):
Доказано в книге Минского-Паперта о персептронах.
Только по-русски пишут "Пейперт":
М.Минский, С.Пейперт, Персептроны.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group