ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 109965
Темы:    [ Математическая логика (прочее) ]
[ Теория алгоритмов (прочее) ]
[ Примеры и контрпримеры. Конструкции ]
[ Объединение, пересечение и разность множеств ]
Сложность: 5-
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

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

Решение

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

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

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

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .