Олимпиадная задача Френкина: Арбитры на турнире, участники Иванов, Петров и Сидоров
Задача
В турнире каждый участник встретился с каждым из остальных один раз. Каждую встречу судил один арбитр, и все арбитры судили разное количество встреч. Игрок Иванов утверждает, что все его встречи судили разные арбитры. То же самое утверждают о себе игроки Петров и Сидоров. Может ли быть, что никто из них не ошибается?
Решение
Пусть никто из трёх игроков не ошибся. Обозначим количество игроков через 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, а все встречи Иванова судили разные арбитры, этот арбитр судил одну из встреч Иванова. По тем же причинам он судил одну из встреч Петрова, а также Сидорова. Но в единственной встрече, которую он судил, участвовали только два игрока. Противоречие.
Ответ
Не может.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь