fixfix
2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 кортежи плюс-минус единиц
Сообщение22.01.2011, 01:42 


16/03/10
212

(Оффтоп)

Имеются все возможные (разные) наборы (кортежи) из чисел $\{+1,-1\}$ длины $n$, все они записаны в таблицу размером $n\times2^n$, то есть каждый кортеж в своей строчке. Эту таблицу назовем начальной. Испорченной назовем таблицу, полученную из начальной заменой некоторых чисел на 0. Доказать, что в любой испорченной таблице можно выбрать непустое подмножество строк, сумма которых равна нулю.

 Профиль  
                  
 
 Re: кортежи плюс-минус единиц
Сообщение24.01.2011, 09:58 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Пусть $v_i \in \mathbb{R}^n$ --- $i$-ая строка начальной таблицы и $u_i \in \mathbb{R}^n$ --- $i$-ая строка испорченной таблицы. Пусть $s_i$ --- сумма компонент вектора $v_i$, а $t_i$ --- сумма компонент вектора $u_i$. Требуется доказать, что для некоторого непустого $A \subseteq \{ 1, \ldots, 2^n \}$ выполняется $\sum_{i \in A} t_i = 0$.

Так как для любого $i$ вектор $v_i-2u_i$ состоит из $\pm 1$, то существует функция $d: \{ 1,\ldots,2^n \} \to \{ 1,\ldots,2^n \}$ такая, что $v_i - v_{d(i)} = 2u_i$. Суммируя компоненты векторов, имеем $s_i - s_{d(i)} = 2t_i$. Пусть $A$ --- минимальный по включению элемент семейства $\{ X \subseteq \{ 1,\ldots,2^n \} : X \neq \varnothing,\, d(X) \subseteq X \}$. Тогда $d$ --- перестановка $A$ и
$$
2\sum_{i \in A} t_i = \sum_{i \in A} (s_i - s_{d(i)}) = \sum_{i \in A} s_i - \sum_{i \in A} s_{d(i)} = \sum_{i \in A} s_i - \sum_{i \in A} s_i = 0
$$

 Профиль  
                  
 
 Re: кортежи плюс-минус единиц
Сообщение24.01.2011, 12:08 


16/03/10
212
Под суммой строк я имел в виду векторную сумму. То есть (в ваших, Профессор Снэйп, обозначениях) нужно доказать, что для некоторого непустого $A \subseteq\{1,\ldots,2^n\}$ выполняется $\sum\limits_{i \in A} u_i = 0$. И этот 0 из ${\mathbb R^n$.
Но не смотря на это, остальное то как раз всё верно! Главное тут
Профессор Снэйп в сообщении #403662 писал(а):
... существует функция $d: \{ 1,\ldots,2^n \} \to \{ 1,\ldots,2^n \}$ такая, что $v_i - v_{d(i)} = 2u_i$.

А еще я знаю "олимпиадное" решение, считая приведенное "аналитическим" :-)

 Профиль  
                  
 
 Re: кортежи плюс-минус единиц
Сообщение24.01.2011, 13:05 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
VoloCh в сообщении #403709 писал(а):
А еще я знаю "олимпиадное" решение, считая приведенное "аналитическим"

Не уверен, что "олимпиадное" проще, ибо проще просто некуда!

 Профиль  
                  
 
 Re: кортежи плюс-минус единиц
Сообщение24.01.2011, 18:10 


16/03/10
212
Профессор Снэйп в сообщении #403729 писал(а):
Не уверен, что "олимпиадное" проще, ибо проще просто некуда!
Да, конечно, Да и вообще, имхо, "олимпиадное" решение часто не проще. И, как правило, сложнее, и длиннее. Зато "красивее". Но это субъективно. На вкус и цвет...

(немного истории)

Зато вот "олимпиадное" (в кавычках!) решение хоть и длинное, зато предельно устное. То есть его можно запросто изложить по телефону, не писяша формул.

(устное решение)


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

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



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

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


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

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