2022-11-02
Жюри областной олимпиады первоначально состояло из 30-ти человек. Каждый член жюри считал, что некоторые из его коллег компетентны, а остальные - нет, и своего твердого мнения не изменял. Каждый день проводилось голосование, и те члены жюри, которые были признаны некомпетентными более чем половиной голосовавших, из состава жюри исключались. Докажите, что не более чем через 15 голосований исключенных больше не было, (По поводу собственной компетентности никто не голосовал. Каждый раз голосовали все оставшиеся в жюри, никто не воздерживался).
Решение:
Предположим, что были выбывшие и при 16-том голосовании. Заметим, что если при некотором голосовании выбывших не было, то их не было и при всех последующих голосованиях. Допустим, что после первого голосования осталось 29 человек: остались только те члены жюри, у которых было не более 14-ти голосов против. Если осталось 29 человек, то 14 голосов против недостаточно для исключения. Тогда при следующем голосовании выбывших не было, что ведет к противоречию с нашим предположением.
Итак, после первого голосования осталось не более 28-ми человек. Совершенно аналогично, после второго голосования осталось не более 26-ти человек, после третьего - не более 24-х и т.д. Но тогда после 15-го голосования (или даже ранее) никого не осталось, что противоречит нашему предположению о том, что были исключенные и при 16-том голосовании.
Комментарий. Возможна ситуация, при которой после нескольких голосований в жюри не остается ни одного человека. Например, если все считают всех своих коллег некомпетентными.