13
правок
Изменения
→Доказательство
# <tex>count = 0</tex><p>Очевидно, что на подмассиве <tex>a[0..k]</tex> мажорирующего элемента не существует, так как все элементы разбились на пары. Тогда только <tex>a[k+1]</tex> может быть мажорирующим элементом.</p>
# <tex>count > 0</tex> и <tex>a[k+1] = candidate</tex><p>Если на подмассиве <tex>a[0..k]</tex> существует мажорирующий элемент, то он находится в <tex>candidate</tex>. Тогда, в силу равенства <tex>a[k+1]</tex> и <tex>candidate</tex>, если на подмассиве <tex>a[0..(k+1)]</tex> существует мажорирующий элемент, то он тоже будет равен <tex>candidate</tex>.</p>
# <tex>count > 0</tex> и <tex>a[k+1] != \ne candidate</tex><p>Если на подмассиве <tex>a[0..k]</tex> существует мажорирующий элемент, то он находится в <tex>candidate</tex>. Тогда, в силу неравенства <tex>a[k+1]</tex> и <tex>candidate</tex>, образовалась новая пара. Если <tex>count</tex> не станет равным нулю, то, опять же, мажорирующим элементом может быть только <tex>candidate</tex>, так как для всех остальных мы нашли пару, а, значит, встречаются они не более <tex>N/2</tex> раз.</p>
