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