Выражение функции XOR через медианы

Теорема:

Докажите, что $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 \geqslant 1$.

Разберемся с условием. Нам предлагается выразить $\mathrm {XOR}$ с $2m+1$ аргументами с помощью медианы с $2m+1$ аргументом. Ей на вход подается набор $\{s_i\}$, получаемый следующим образом:

Выпишем последовательность $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_{1} = \langle x_0, x_1, x_2, x_3, \ldots, x_{m-1}, x_m, \neg x_{m+1}, \neg x_{m+2}, \neg x_{m+3}, \ldots, \neg x_{2m-1}, \neg x_{2m} \rangle$
- $s_{m} = \langle x_0, \neg x_1, \neg x_2, \neg x_3, \ldots, \neg x_{m-1}, x_m, x_{m+1}, x_{m+2}, x_{m+3} \ldots, x_{2m-1}, \neg x_{2m} \rangle$
- $s_{m+2} = \langle x_0, x_1, \neg x_2, \neg x_3, \ldots, \neg x_{m-1}, \neg x_m, \neg x_{m+1}, x_{m+2}, x_{m+3} \ldots, x_{2m-1}, x_{2m} \rangle$,
- $s_{m+3} = \langle x_0, x_1, x_2, \neg x_3, \ldots, \neg x_{m-1}, \neg x_m, \neg x_{m+1}, \neg x_{m+2}, x_{m+3}, \ldots, x_{2m-1}, x_{2m} \rangle$,

И весь этот набор ${s_i}$ (а их будет ровно $2m$ штук) передается (вместе с $\neg x_0$), на вход еще одной медиане: $\langle \neg x_0, s_1, s_2, \ldots, s_{2m} \rangle$

Вспомогательные утверждения

Далее исключим $x_0$ из рассмотрения аргументов $s_i$.

Лемма:

В каждой $s_i$ ровно $m$ переменных с отрицанием и столько же без него.

Доказательство:

Различных чисел-индексов от $j$ до $j + m - 1$ (с учетом того, что $x_{2m+k}$ = $x_k$) ровно $((j + m - 1) - j + 1 + 2m) \bmod 2m = m$. Поэтому с отрицанием будет ровно $m$ переменных.

А так как всего $2m$ переменных, то без отрицания будет тоже ровно $m$.

Лемма:

Каждой $s_i$ можно однозначно сопоставить в пару такую $s_j$, что все переменные с отрицанием из $s_i$ в $s_j$ будут без отрицания и наоборот.

Доказательство:

Мы строим набор ${s_i}$, циклически сдвигая отрезок отрицания переменных, пока не получим все возможные. Совершив ровно $m$ таких шагов, мы сдвинем начала отрезка отрицания на следующую позицию после его конца. Таким образом, там, где был отрезок отрицания, будет отрезок без отрицания, и наоборот.

Назовем такую пару $(s_i, s_j)$ двойственной, и будем обозначать через $\neg s_i$ двойственную $s_i$ пару.

Назовем самостоятельной единицей для $s_i$ любой ее единичный аргумент (с учетом возможных отрицаний). $s_i$ имеет самостоятельную единицу на месте $j$, если $j$-ый аргумент имеет значение $1$.

Утверждение:

Если в $s_i$ ровно $n$ самостоятельных единиц, то в $\neg s_i$ их будет $(2m - n)$.

Пусть $A_i$ — множество аргументов $s_i$ с отрицанием, $B_i$ — без отрицания. Оба множества по условию мощности $m$. Пусть среди $A_i$ ровно $a_i$ переменных равны $1$, тогда оставшиеся $(m - a_i)$ из них — нули. Аналогично среди $B_i$ ровно $b_i$ единиц и $(m - b_i)$ нулей. Самостоятельные единицы $s_i$ получаются из нулей среди $A_i$ и единиц среди $B_i$. Тогда в $s_i$ будет $(m - a_i) + b_i$ самостоятельных единиц. В $\neg s_i$ переменные заменятся на их отрицания, поэтому самостоятельные единицы в ней получаются из единиц среди $A_i$ и нулей среди $B_i$. Поэтому количество самостоятельных единиц в $\neg s_i$ будет $a_i + (m - b_i)$.

Нетрудно убедиться, что нужное соотношение выполняется: $(m - a_i) + b_i = 2m - (a_i + (m - b_i)) \Leftrightarrow m - a_i + b_i = 2m - a_i - m + b_i$

Утверждение:

Среди ${x_i}$ четное число единиц $\Leftrightarrow$ найдется двойственная пара с одинаковым количеством самостоятельных единиц, равным $m$.

$\Leftarrow$

Выше мы поняли структуру аргументов $s_i$. Нужно приравнять количества (в обозначениях выше): $(m - a_i) + b_i = a_i + (m - b_i) \Leftrightarrow a_i = b_i$

А $a_i$ и $b_i$ — количества единиц в $A_i$ и в $B_i$ соответственно, и, так как множество всех аргументов $s_i$ это $A_i \cup B_i$, то $(a_i+b_i)$ и есть количество единиц среди ее аргументов. Но $a_i = b_i$, значит $a_i + b_i$ четное.

Вообще, утверждения "нашлась двойственная пара с одинаковым числом самостоятельных единиц" (1) и "нашлась $s_i$ с количеством самостоятельных единиц, равным $m$" (2) равносильны.

И правда, выше мы поняли, что (1) $\Leftrightarrow a_i = b_i$. Посчитаем количество самостоятельных единиц в $s_i$. $((m - a_i) + b_i) = m \Leftrightarrow a_i = b_i$.

$\Rightarrow$

Пусть среди ${x_i}$ будет $2t$ единиц. Давайте найдем $s_j$, в которой среди $A_j$ единиц столько же, сколько и среди $B_j$. Тогда в ней будет $a_j = b_j$, из чего и будет следовать требуемое. Рассмотрим любую $s_k$. Будем считать, что в $A_k$ меньше половины единиц ($a_k < t$), иначе рассмотрим двойственную ей, в ней будет меньше половины, или, если равенство, то мы уже нашли такую. Будем последовательно сдвигать отрицания вправо на одну позицию, переходя от $s_l$ к $s_{l+1}$. За каждый сдвиг количество единиц в $A_l$ может измениться только на 1. Действительно, если в $A_l$ добавились и ушли разные числа, то количество единиц изменилось на $1$ (увеличилось или уменьшилось), а если одинаковые — то не поменялось. Таким образом, сделав $m$ шагов, мы дойдем от $s_l$ до $\neg s_l$, причем количество единиц в $A_l$ будет изменяться не более, чем на $1$. Изначально оно было $a_l$, а станет — $2t - a_l$. Тогда выполняются неравенства: $a_k \leqslant t \leqslant 2t - a_k$. Левый знак верен просто потому, что мы так выбрали $s_k$, а правый, очевидно, равносилен первому. Таким образом, мы, изменяя $a_l$ не больше, чем на единицу, пришли из $a_k$ в $2t - a_k$, причем число $t$ было между ними. Поэтому мы обязательно на каком-то шаге оказались с $a_{l'} = t$, то есть ровно половина единиц попала в $A_{l'}$, чего мы и хотели.

Заметим также, что мы доказали наличие одной пары, но на самом деле таких может быть больше. Давайте такие пары назовем особенными, а остальные — обычными.

Доказательство теоремы

Теорема:

$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$

Доказательство:

Пусть $k_i$ — количество самостоятельных единиц у $s_i$.

Рассмотрим два случая.

$x_0 = 0$.
- Тогда в каждой $s_i$ будет стоять вместо него $0$, то есть количество аргументов-единиц в точности равно количеству самостоятельных единиц.
- Пусть $k_i \geqslant m + 1 \Rightarrow k_{i + m} \leqslant m - 1$ (и аналогично с противоположным знаком) $\Rightarrow$ в обычных парах одна $s_i$ будет равна $1$, а вторая $0$.
- При нечетном количестве единиц особенных пар не будет, будет только ровно $m$ обычных пар, из каждой ровно одна $s_i$ даст единицу. Тогда среди всех $s_i$ будет ровно $m$ единиц, и, подставив их в конечную медиану, вместе с $\neg x_0 = 1$, получим ровно $m + 1$ аргумент, равный $1$. Тогда медиана вернет $1$, чего и должен вернуть $\oplus$ нечетного числа единиц.
- При четном количестве у нас найдется особенная пара, а в этих $s_i$ и $\neg s_{i}$ ровно по $m$ самостоятельных единиц, а значит, они обе будут равны $0$. Тогда всего среди $s_i$ будет $\leqslant m - 1$ $s_i = 1$, значит, конечная медиана вернет $0$, что и нужно при $\oplus$ четного числа единиц.
$x_0 = 1$
- Тогда в каждой $s_i$ будет стоять вместо него $1$, то есть количество аргументов-единиц для $s_i$ на один больше количества самостоятельных единиц.
- Пусть $k_i \geqslant m + 1 \Rightarrow k_{i + m} \leqslant m - 1$ (и аналогично с противоположным знаком) $\Rightarrow$ по-прежнему (тут с учетом $x_0 = 1$) в обычных парах одна $s_i$ будет равна $1$, а вторая $0$.
- При нечетном количестве единиц особенных пар нет, будет снова только ровно $m$ обычных пар, из каждой ровно одна $s_i$ даст единицу. Тогда среди всех $s_i$ будет ровно $m$ единиц, и, подставив их в конечную медиану, вместе с $\neg x_0 = 0$, получим ровно $m$ аргументов, равных $1$. Тогда медиана вернет $0$, чего и должен вернуть $\oplus$ четного числа единиц.
- При четном количестве у нас найдется особенная пара, а в этих $s_i$ и $\neg s_{i}$ ровно по $m$ самостоятельных единиц, а значит, они обе будут равны $1$, ведь вместе с $x_0 = 1$ среди аргументах медиан будет по $m + 1$ единиц. Тогда всего среди $s_i$ будет $\geqslant m + 1$ $s_i = 1$, значит, конечная медиана вернет $1$, что и нужно при $\oplus$ четного числа единиц.

См. также

Источники информации

Выражение функции XOR через медианы

Содержание

Вспомогательные утверждения

Доказательство теоремы

См. также

Источники информации

Навигация

Персональные инструменты

Пространства имён

Варианты

Просмотры

Ещё

Поиск

Навигация

Инструменты