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

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

Условие

В турнире каждый участник встретился с каждым из остальных один раз. Каждую встречу судил один арбитр, и все арбитры судили разное количество встреч. Игрок Иванов утверждает, что все его встречи судили разные арбитры. То же самое утверждают о себе игроки Петров и Сидоров. Может ли быть, что никто из них не ошибается?


Решение

  Пусть никто из трёх игроков не ошибся. Обозначим количество игроков через n, а количество арбитров через m. Упорядочим арбитров по количеству встреч, которые они судили. Тогда первый арбитр судил не менее одной встречи, второй – не менее двух, ..., последний – не менее m. Следовательно, общее количество встреч не менее  1 + 2 + ... + m.  С другой стороны, общее количество встреч равно  1 + 2 + ... + (n – 1).  Поэтому  m ≤ n – 1.
  Поскольку все  n – 1  встреч с участием Иванова судили разные арбитры,  m ≥ n – 1.  Значит,   m = n – 1,  и все выписанные выше неравенства обязаны быть равенствами, то есть первый арбитр судил ровно одну встречу, второй – ровно две, ...,  (n–1)-й – ровно  n – 1.
  Рассмотрим арбитра, который судил ровно одну встречу. Поскольку арбитров  n – 1,  а все встречи Иванова судили разные арбитры, этот арбитр судил одну из встреч Иванова. По тем же причинам он судил одну из встреч Петрова, а также Сидорова. Но в единственной встрече, которую он судил, участвовали только два игрока. Противоречие.


Ответ

Не может.

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

олимпиада
Название Московская математическая олимпиада
год
Год 2011
Номер 74
класс
Класс 9
задача
Номер 2

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

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