Условие
Каждый из голосующих на выборах
вносит в избирательный бюллетень фамилии
10 кандидатов. На избирательном участке
находится 11 урн. После выборов выяснилось,
что в каждой урне лежит хотя бы один бюллетень и при всяком
выборе 11 бюллетеней по одному из каждой урны найдется кандидат,
фамилия которого встречается в каждом из выбранных бюллетеней.
Докажите, что по крайней мере в одной урне
все бюллетени содержат фамилию одного и того же кандидата.
Подсказка
Возьмите произвольный бюллетень из 11-й урны и рассуждайте от
противного.
Решение
Возьмем произвольный бюллетень из 11-й урны.
Пронумеруем кандидатов, фамилии которых
встречаются в этом бюллетене. Предположим,
что требуемое в задаче не выполнено. Тогда в k-й урне (k=1,2,...10)
найдется бюллетень, не содержащий фамилии k-го кандидата.
Набор этих
бюллетеней вместе со взятым вначале
бюллетенем из 11-й урны противоречит условию задачи.
Источники и прецеденты использования
