Последние новости
04.09.24
Объявление
09.06.24
Результаты Олимпиады
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.24
Предварительные результаты
В очереди на голосование стоят n человек. Известно, что рядом с каждым человеком (непосредственно впереди его в очереди или сзади) есть человек, голосующий «за». Докажите, что число человек в очереди, голосующих «за» не менее половины.
Попробуем доказать обратное, что кол-во 1 < половины. Максимизируем кол-во 0: Пусть 1-й элемент = 0, 2-й в любом случае 1 (Чтобы у первого был сосед 1), тогда 3-й элемент = 1 (Т.к. 1-й = 0, если 1-й = 1, то 3-й может=0). Т.е. начало либо (1,1), либо (0,1,1); (кол-во 0 < кол-ва 1) Тогда рассмотрим цепочку с первого эл.(k) = 0 (перед которым была 1): Если последующий за ним(k+1) = 0, то след. (k+2) и (k+3) = 1, (k+4) может быть каким угодно, т.е. значение 0 скомпенсировалось.(0,0,1,1) (кол-во 0 = кол-ву 1) При (k+1) = 1 получается, что (k+2) = 1. Следущий (k+3) может быть каким угодно. (0,1,1) - (кол-во 0 < кол-ва 1). Заметим также, 1 могут повторяться друг за другом бесконечное кол-во раз(что не выгодно). Также заметим, что если после k нет других символов, то (кол-во 0