кортежи плюс-минус единиц

[VoloCh]

(Оффтоп)

уже давал эту задачу, но затерялась

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

[Профессор Снэйп]

Пусть $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 $$

[VoloCh]

Под суммой строк я имел в виду векторную сумму. То есть (в ваших, Профессор Снэйп, обозначениях) нужно доказать, что для некоторого непустого $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$.

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

[Профессор Снэйп]

VoloCh в сообщении #403709 писал(а):

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

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

[VoloCh]

Профессор Снэйп в сообщении #403729 писал(а):

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

Да, конечно, Да и вообще, имхо, "олимпиадное" решение часто не проще. И, как правило, сложнее, и длиннее. Зато "красивее". Но это субъективно. На вкус и цвет...

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

Что касается этой задачи, то я придумал ее лет >20 назад. Тогда один мой знакомый (фанат работы со школьниками), не зная решения, послал ее в качестве олимпиадной на какой-то этап всесоюзной Олимпиады (Во! Это было еще в СССР!). Ему сказали, что в качестве олимпиадной она не годится, так как ее решение занимает несколько страниц. Так что ваше решение, уважаемый профессор, довольно неочевидно. Тут есть 2 важных момента. Паросочетания (существует функция $d$...) и принцип Дирихле (существует минимальный элемент $A$...).

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

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

Итак, будем интерпретировать строки начальной таблицы как направленные рёбра всех диагоналей единичного куба в $n$-мерном пространстве. Из каждой вершины куба выходит ровно одно (направленное) ребро. Испортить таблицу – это значит перенаправить ребро в другую вершину куба ("другая" может быть и той же, что и раньше, т.е. противоположной). Теперь рассмотрим всю эту ерунду как направленный граф. Из каждой его вершины что-то выходит. В силу конечности картинки тут есть замкнутый цикл. Он то нам и нужен!

Наблюдение. Можно так испортить таблицу, что такой цикл будет ровно один.