Изменения

|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 1$.}} {{Определение|definition = '''Медиана''' или '''функция большинства''' (англ. ''Majority function'') {{---}} функция (в данном случае) с нечетным числом входов, возвращающая $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_{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$,** $s_{m+3} = \langle x_0, x_1, x_2, \neg x_3, \neg x_4, \ldots, \neg x_m, \neg x_{m+1}, \neg x_{m+2}, x_{m+3}, \ldots, 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}, \ldots, x_{2m-1}, \neg x_{2m} \rangle$** $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}, \ldots, \neg x_{2m-1}, \neg x_{2m} \rangle$ И весь этот набор ${s_i}$, вместе с $\neg x_0$, передается на вход еще одной медиане: $\langle \neg x_0, s_1, s_2, \ldots, s_{2m} \rangle$Далее исключим на время из рассмотрения аргументов $s_i x_0$. == Общие соображения ==* В каждой $s_i$ ровно $m$ переменных с отрицанием и столько же без него* Каждой $s_i$ можно однозначно сопоставить пару $s_j$ такую, что все переменные с отрицанием из $s_i$ в $s_j$ будут без отрицания и наоборот. Это следует из того, как мы строим набор ${s_i}$ {{---}} циклически сдвигаем "крышу отрицания" над переменными, пока не получим все такие. Для нахождения нужно сдвинуть "крышу" ровно на $m$ позиций (вправо или влево, это не важно {{---}} получится одно и то же). Назовем такую пару $(s_i, s_j)$ двойственной, и пусть $s_j = \neg s_i$* Назовем '''самостоятельной единицей''' для $s_i$ любой ее единичный аргумент* Если самостоятельных единиц в $s_i$ "достаточно много" (а сколько именно, будет зависеть от $x_0$), то в $\neg s_i$ их будет "достаточно мало" {{Утверждение|statement=Если в $s_i n$ самостоятельных единиц, то в $\neg s_i (2m - n)$ самостоятельных единиц.|proof=Пусть $A$ - множество переменных $s_i$ с отрицанием, $B$ - без отрицания. Оба множества по условию мощности $m$.Пусть среди $A$ ровно $a$ переменных равны $1$. Тогда оставшиеся $(m - a)$ из них {{---}} нули. Пусть среди $B$ ровно $b$ переменных равны $1$. Тогда оставшиеся $(m - b)$ из них {{---}} нули.Самостоятельные единицы $s_i$ получаются из нулей среди $A$ и единиц среди $B$. Тогда в $s_i$ будет $(m - a) + b$ самостоятельных единиц.В двойственной $s_i$ переменные заменятся на их отрицания, поэтому самостоятельные единицы $\neg s_i$ получаются из единиц среди $A$ и нулей среди $B$.Поэтому количество самостоятельных единиц в $\neg s_i$ будет $a + (m - b)$.Нетрудно убедиться, что нужное соотношение выполняется: $(m - a) + b = 2m - (a + (m - b)) \Leftrightarrow m - a + b = 2m - a - m + b$}} {{Утверждение|statement=Среди ${x_i}$ четное число единиц \Leftrightarrow найдется двойственная пара с одинаковым количеством самостоятельных единиц, равным $m$.|proof=Импликация влево.