Последние новости
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.24
Предварительные результаты
25.12.23
Отборочный этап завершён.
18.12.23
Отборочный этап продлён по 24 декабря включительно
В очереди на голосование стоят n человек. Известно, что рядом с каждым человеком (непосредственно впереди его в очереди или сзади) есть человек, голосующий «за». Докажите, что число человек в очереди, голосующих «за» не менее половины.
Доказательство. Для того, чтобы нулей было больше, чем единиц, требуется, чтобы всё выражение состояло из связок либо 010(что невозможно, так как для единицы, стоящей посередине, единицы-соседа нет), либо 001100. Однако, начинаться, равно как и заканчиваться(далее "равно как и заканчиваться" будет опускаться, но везде, где есть "начинаться", оно подразумевается), выражение с 00 не может - для крайнего нуля единицы-соседа не будет. Начинаться с 0100 выражение тоже не может - тогда будет недопустимая связка 010. Возможны начала и окончания - 110011...110011, тогда единиц будет стабильно больше на две(как минимум), либо 0110011...1100110, тогда единиц будет всегда столько же, сколько и нулей. Больше быть не может.