Задача 109965

Темы:    [ Математическая логика (прочее) ] [ Теория алгоритмов (прочее) ] [ Примеры и контрпримеры. Конструкции ] [ Объединение, пересечение и разность множеств ]

Сложность: 5- Классы: 8,9,10

Условие

Автор: Разборов А.

На выборах в городскую Думу каждый избиратель, если он приходит на выборы, отдает голос за себя (если он является кандидатом) и за тех кандидатов, которые являются его друзьями. Прогноз социологической службы мэрии считается хорошим, если в нем правильно предсказано количество голосов, поданных хотя бы за одного из кандидатов, и нехорошим в противном случае. Докажите, что при любом прогнозе избиратели могут так явиться на выборы, что этот прогноз окажется нехорошим.

Решение

Прогноз, в котором нет нулей, окажется нехорошим, если все избиратели не явятся на выборы. Поэтому в каждом хорошем прогнозе должны быть нули. Пусть в прогнозе П у кандидата A и некоторых из его друзей A₁,..,A_k 0 голосов. Тогда при явке A на выборы прогноз по A,A₁,..,A_k уже ошибочен. Исключим A,A₁,..,A_k из списков кандидатов, и уменьшим на 1 прогноз по остальным друзьям A . Тогда мы вернемся к исходной задаче, но с меньшим числом кандидатов и меньшим на одного человека ( A ) числом избирателей. Продолжая эту процедуру, мы приходим к несовпадению по каждому кандидату числа поданных голосов с прогнозируемым. Значит, исходный прогноз – нехороший.

Источники и прецеденты использования

олимпиада
Название	Всероссийская олимпиада по математике
год
Год	1998
Этап
Вариант	4
Класс
Класс	8
задача
Номер	98.4.8.8