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