Последние новости
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.24
Предварительные результаты
25.12.23
Отборочный этап завершён.
18.12.23
Отборочный этап продлён по 24 декабря включительно
В очереди на голосование стоят n человек. Известно, что рядом с каждым человеком (непосредственно впереди его в очереди или сзади) есть человек, голосующий «за». Докажите, что число человек в очереди, голосующих «за» не менее половины.
Обозначим человека, голосующего "за" -- 1, голосующего "против" -- 0 Допустим, в очереди стоят n=2k человек. Пусть "за" проголосовали ровно k человек. Тогда людей можно расставить так: (01)*... При этом условие не выполняется. Переставим людей следующим образом: (0110)*=01100110... Условие выполняется. Если "за" проголосовало (k-1) человек, см. далее. При (k-1) проголосовавших "за" исходная цепочка примет вид (01)*0=010101010...0. Если переставлять цифры так, как в прошлом номере, получится 011001100 -- условие не выполняется для последнего нуля, т.е. k -- минимальное число проголосовавших "за". Допустим, в очереди стоят n=2k+1 человек. Пусть "за" проголосовали ровно k человек. Тогда людей можно расставить аналогично предыдущему случаю с (k-1) проголосовавшими: (01)*0 -- условие не будет выполняться. Если "за" проголосовали (k+1) человек, то исходная цепочка примет вид (01)*1=0101...1, ее можно преобразовать к 01100110...01101. Условие выполняется. То есть и для n=2k, и для n=2k+1 голосовать "за" должны не менее половины людей.