66
правок
Изменения
Нет описания правки
{{Задача
|definition = Докажите, что $x_0 \oplus x_1 \oplus \ldots \oplus x_{2m} = \langle \neg x_0, s_1, s_2, \ldots, s_{2m} \rangle$, $s_j = \langle x_0, x_j, x_{j+1}, \ldots, x_{j+m-1}, \neg x_{j+m}, \neg x_{j+m+1}, \ldots, \neg x_{j+2m-1} \rangle$, где $x_{2m+k}$ обозначает то же, что и $x_k$, при $k \ge geqslant 1$.}} {{Определение|definition = '''Медиана''' или '''функция большинства''' $\langle x_1, x_2, \ldots, x_n \rangle $(англ. ''Majority function'') {{---}} функция (в данном случае) с нечетным числом входов, возвращающая $1$ тогда и только тогда, когда среди ее аргументов не меньше половины единиц.
}}
* Выпишем последовательность $x_1, x_2, \ldots, x_{2m}$
* Первую половину аргументов (а их ровно $m$) возьмем с отрицанием ($\neg x_1, \neg x_2, \ldots, \neg x_m, x_{m+1}, x_{m+2}, \ldots, x_{2m}$)
* Слева к этой последовательности припишем $x_0$ и дадим на вход медиане: $\langle x_0, \neg x_1, \neg x_2, \ldots, \neg x_m, x_{m+1}, x_{m+2}, \ldots, x_{2m} \rangle$ {{- --}} так мы получили $s_{m+1}$
* Остальные $s_i$ получаются циклическим сдвигом отрицания (без учета $x_0$), например, вправо (так мы получим все циклические сдвиги отрицаний):
** $s_{m+2} = \langle x_0, x_1, \neg x_2, \neg x_3, \ldots, \neg x_m, \neg x_{m+1}, x_{m+2}, \ldots, x_{2m} \rangle$,
{{Утверждение
|statement=Если в $s_i$ ровно $n$ самостоятельных единиц, то в $\neg s_i$ их будет $(2m - n)$.
|proof=Пусть $A_i$ {{- --}} множество аргументов $s_i$ с отрицанием, $B_i$ {{--- }} без отрицания. Оба множества по условию мощности $m$.
Пусть среди $A_i$ ровно $a_i$ переменных равны $1$, тогда оставшиеся $(m - a_i)$ из них {{---}} нули.
Аналогично среди $B_i$ ровно $b_i$ единиц и $(m - b_i)$ нулей.
{{Утверждение
|statement=Среди ${x_i}$ четное число единиц $\Leftrightarrow$ найдется двойственная пара с одинаковым количеством самостоятельных единиц, равным $m$.
|proof=Импликация влево.$\Leftarrow$
Выше мы поняли структуру аргументов $s_i$. Нужно приравнять количества (в обозначениях выше): $(m - a_i) + b_i = a_i + (m - b_i) \Leftrightarrow a_i = b_i$
И правда, выше мы поняли, что (1) $\Leftrightarrow a_i = b_i$. Посчитаем количество самостоятельных единиц в $s_i$. $((m - a_i) + b_i) = m \Leftrightarrow a_i = b_i$. Таким образом, равносильность доказана.
Пусть среди ${x_i}$ будет $2t$ единиц.
Давайте найдем $s_j$, в которой среди $A_j$ единиц столько же, сколько и среди $B_j$. Тогда в ней будет $a_j = b_j$, из чего и будет следовать требуемое.
Действительно, если в $A_l$ добавились и ушли разные числа, то количество единиц изменилось на $1$ (увеличилось или уменьшилось), а если одинаковые {{---}} то не поменялось.
Таким образом, сделав $m$ шагов, мы дойдем от $s_l$ до $\neg s_l$, причем количество единиц в $A_l$ будет изменяться не более, чем на $1$. Изначально оно было $a_l$, а станет {{---}} $2t - a_l$.
Тогда выполняются неравенства: $a_k \le leqslant t \le leqslant 2t - a_k$. Левый знак верен просто потому, что мы так выбрали $s_k$, а правый, очевидно, равносилен первому.
Таким образом, мы, изменяя $a_l$ не больше, чем на единицу, пришли из $a_k$ в $2t - a_k$, причем число $t$ было между ними. Поэтому мы обязательно на каком-то шаге оказались с $a_{l'} = t$, то есть ровно половина единиц попала в $A_{l'}$, чего мы и хотели.
Заметим также, что мы доказали наличие '''одной пары''', но на самом деле таких может быть больше. Давайте такие пары назовем '''особенными''', а остальные {{---}} обычными.
}}
== А теперь решение Решение ==
Пусть $k_i$ {{---}} количество самостоятельных единиц у $s_i$.
Рассмотрим два случая.
# $x_0 = 0$.
* [[Представление функции формулой, полные системы функций]]
* [[Представление функции класса DM с помощью медианы]]
