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