Последние новости
04.09.24
Объявление
09.06.24
Результаты Олимпиады
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.24
Предварительные результаты
В очереди на голосование стоят n человек. Известно, что рядом с каждым человеком (непосредственно впереди его в очереди или сзади) есть человек, голосующий «за». Докажите, что число человек в очереди, голосующих «за» не менее половины.
Рассмотрим самый худший вариант - если все люди, рядом с которыми стоят те, которые голосуют "За", голосуют против, тогда мы получим бесконечную цепочку 101010... или 01010101... В которых n элементов. Если голосует против x человек, то рядом с ними стоит x человек, которые голосуют за. Из этого следует, что "За" никогда не будет голосовать меньше половины