Последние новости
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.24
Предварительные результаты
25.12.23
Отборочный этап завершён.
18.12.23
Отборочный этап продлён по 24 декабря включительно
В очереди на голосование стоят n человек. Известно, что рядом с каждым человеком (непосредственно впереди его в очереди или сзади) есть человек, голосующий «за». Докажите, что число человек в очереди, голосующих «за» не менее половины.
Очередь можно представить так: (11((1*+(011*)+(0011*))1)*)+(01((11*0)+(11*001)+1*)*). Рассмотрим первый вариант ИЛИ: сначала идут 2 единицы, потом либо х1, либо х01+у1, либо х001+у1 и всегда еще х1. Итого либо 2х+2 единиц и 0 нолей, либо 2х+у+2 единиц и х нолей, либо 2х+у+2 единиц и 2х нолей. Единиц в любом случае больше или равно чем нолей, следовательно их >= половины. Рассмотрим второй вариант ИЛИ: сначала идут 0+1, потом 1+0+х1, либо 2 единицы, 2 ноля и х1, либо х1. В первом случае будет х+2 единиц и 1 ноль, во втором х+3 единиц и 3 ноля и в третьем х+1 единиц и 1 ноль. В любом случае единиц >= нолей, следовательно их >= половины.