1632
правки
Изменения
м
rollbackEdits.php mass rollback
Но $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$.
Давайте найдем $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_k$ до $\neg s_k$, причем количество единиц в $A_l$ будет изменяться не более, чем на $1$. Изначально оно было $a_l$, а станет {{---}} $2t - a_l$.
