66
правок
Изменения
Нет описания правки
** $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}$, (а их будет ровно $2m$ штук) передается (вместе с $\neg x_0$), передается на вход еще одной медиане: $\langle \neg x_0, s_1, s_2, \ldots, s_{2m} \rangle$
Далее на время исключим $x_0$ из рассмотрения аргументов $s_i$.
* В каждой $s_i$ ровно $m$ переменных с отрицанием и столько же без него.
* Каждой $s_i$ можно однозначно сопоставить пару $s_j$ такую, что все переменные с отрицанием из $s_i$ в $s_j$ будут без отрицания и наоборот. Это следует из того, как мы строим набор ${s_i}$ {{---}} циклически сдвигаем "крышу отрицания" над переменными, пока не получим все такие. Для нахождения нужно сдвинуть "крышу" ровно на $m$ позиций (вправо или влево, это не важно {{---}} получится одно и то же). Назовем такую пару $(s_i, s_j)$ двойственной, и пусть $s_j = \neg s_i$ (на самом деле $\neg s_i = s_{i+m}$).
* Назовем '''самостоятельной единицей''' для $s_i$ любой ее единичный аргумент(с учетом возможных отрицаний). То есть если $x_j = 1$ и в $s_i$ он стоит без отрицания, то это будет самостоятельная единица. Также $a_j$ будет самостоятельной единицей, если $a_j = 0$ и в $s_i$ он стоит с отрицанием. В остальных случаях $a_j$ не является самостоятельной единицей.
* Если самостоятельных единиц в $s_i$ "достаточно много" (а сколько именно, будет зависеть от $x_0$), то в $\neg s_i$ их будет "достаточно мало".
{{Утверждение
|statement=Если в $s_i$ ровно $n$ самостоятельных единиц, то в $\neg s_i$ их будет $(2m - n)$.
|proof=Пусть $AA_i$ - множество аргументов $s_i$ с отрицанием, $BB_i$ - без отрицания. Оба множества по условию мощности $m$.Пусть среди $AA_i$ ровно $aa_i$ переменных равны $1$, тогда оставшиеся $(m - aa_i)$ из них {{---}} нули. Аналогично среди $BB_i$ ровно $bb_i$ единиц и $(m - bb_i)$ нулей.Самостоятельные единицы $s_i$ получаются из нулей среди $AA_i$ и единиц среди $BB_i$. Тогда в $s_i$ будет $(m - aa_i) + bb_i$ самостоятельных единиц.В двойственной $\neg s_i$ переменные заменятся на их отрицания, поэтому самостоятельные единицы $\neg s_i$ в ней получаются из единиц среди $AA_i$ и нулей среди $BB_i$.Поэтому количество самостоятельных единиц в $\neg s_i$ будет $a a_i + (m - bb_i)$.Нетрудно убедиться, что нужное соотношение выполняется: $(m - aa_i) + b b_i = 2m - (a a_i + (m - bb_i)) \Leftrightarrow m - a a_i + b b_i = 2m - a a_i - m + bb_i$
}}
|proof=Импликация влево.
А $aa_i$ и $bb_i$ {{---}} количества единиц в $AA_i$ и в $BB_i$ соответственно, и, так как множество всех аргументов $s_i$ это $A A_i \cup BB_i$, то $(aa_i+bb_i)$ и есть количество единиц среди ее аргументов.Но $a a_i = bb_i$, значит $a a_i + bb_i$ четное.
Вообще, утверждения "нашлась двойственная пара с одинаковым числом самостоятельных единиц" (1) и "нашлась $s_i$ с количеством самостоятельных единиц, равным $m$" (2) равносильны.
И правда, выше мы поняли, что (1) $\Leftrightarrow a a_i = bb_i$. Посчитаем количества количество самостоятельных единиц в $s_i$. $((m - aa_i) + bb_i) = m \Leftrightarrow a a_i = bb_i$. Таким образом, равносильность доказана.
Импликация вправо.
Пусть среди ${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 \le t \le 2t - a_k$. Левый знак верен просто потому, что мы так выбрали $s_k$, а правый, очевидно, равносилен первому.
Таким образом, мы, изменяя a_l не больше, чем на единицу, пришли из $a_k$ в $2t - a_k$, причем число $t$ было между ними. Поэтому мы обязательно на каком-то шаге оказались с $a_{l'} = t$, то есть ровно половина единиц попала в $A_{l'}$, чего мы и хотели.
Заметим также, что мы доказали наличие '''одной пары''', но на самом деле таких может быть больше. Давайте такие пары назовем '''особенными''', а остальные {{---}} обычными.
}}
== А теперь решение ==Пусть $k_i$ {{---}}количество самостоятельных единиц у $s_i$.Наконец вспомним про $x_0$.Рассмотрим два случая.# $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$ четного числа единиц.
