Последние новости
04.09.24
Объявление
09.06.24
Результаты Олимпиады
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.24
Предварительные результаты
В очереди на голосование стоят n человек. Известно, что рядом с каждым человеком (непосредственно впереди его в очереди или сзади) есть человек, голосующий «за». Докажите, что число человек в очереди, голосующих «за» не менее половины.
Очевидно, что очередь должна начинаться с того, кто голосует "за" либо с того, кто голосует "против", однако, следующий всегда "за". Рассмотрим следующую цепочку как совкупность очередей из 4-х человек. Далее в любом случае будет существовать 50+% людей, голосующих "за": рассмотрим несколько невозможных ситуаций для комбинаций из 4-х человек:(обозначим для удобства "за" как 1, "против" как 0);1000,0100,0010,0001,0000. Они невозможны, так как в них сущ-ют луди, не удовлетворяющие условию. В ином случае 1 всегда >= половине, плюс, удовлетворяющие условиям комбинации можно повторять бесконечное количество раз, так как всегда найдётся комбинация, подходящая к обоим случаям конца комбинации из 4 человек. Более того, если "обрезать" следующую комбинацию из 4 человек, то все тройки и пары не будут удовлетворять условию >= 50% едениц.