Последние новости
04.09.24
Объявление
09.06.24
Результаты Олимпиады
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.24
Предварительные результаты
В очереди на голосование стоят n человек. Известно, что рядом с каждым человеком (непосредственно впереди его в очереди или сзади) есть человек, голосующий «за». Докажите, что число человек в очереди, голосующих «за» не менее половины.
Пусть: n - число человек в очереди 0 - голосующий "против" 1 - голосующий "за" Попробуем минимизировать число голосующих "за". Для этого пусть в начале и конце очереди будут стоять голосующие против: 0......0 По условию, рядом с 0 обязательно должен стоять 1. 01.....10 Также, поскольку у обоих 1 рядом стоит только 0, то рядом с ними также нужно добавить 1. 011....110 Далее мы можем поставить 0. 0110...0110 Далее, если мы добавим 0, то после должны сразу добавить две 1. 0110011...1100110. Если мы далее продолжим составлять последовательность с минимальным числом 1, то заметим закономерность: после первоначального нуля всегда идет одна и та же последовательность: 110011.. Также заметим, что на каждом шагу составления последовательности количество 1 больше или равно количеству 0, т.е количество 1 никогда не становиться меньше чем половина n.