Задание №177296: Турнир городов

4. На сборах теннисистов было 30 мастеров и 30 юниоров. Каждый мастер сыграл с одним мастером и
пятнадцатью юниорами, а каждый юниор — с одним юниором и пятнадцатью мастерами. Докажите, что
найдутся такие два мастера и два юниора, что эти мастера сыграли между собой, юниоры — между собой,
каждый из двух мастеров — хотя бы с одним из двух юниоров, а каждый из двух юниоров — хотя бы с одним
из двух мастеров.
А.Грибалко
Решение 1. Нарисуем таблицу 30 × 30; столбцы соответствуют мастерам, строки — юниорам, при этом пара
сыгравших друг с другом мастеров соответствует паре соседних столбцов (то же с юниорами). Закрасим клетку,
если соответствующие мастер и юниор сыграли друг с другом (всего закрашена половина клеток). Тогда таблица
разбивается на квадраты 2 × 2, и нужно найти такой квадрат, в котором закрашена одна из диагоналей.
Заметим сразу, что это выполнено, если в квадрате хотя бы 3 закрашенных клетки. Значит, если утверждение
неверно, то в каждом квадрате не более 2 закрашенных. Поскольку всего закрашена половина клеток, в каждмом
кварате тогда ровно по 2 закрашенных клетки, образующих «доминошку».
Рассмотрим вертикальный ряд из 15 квадратов. В его столбцах поровну закрашенных клеток, а значит —
поровну вертикальных доминошек. Значит, общее число вертикальных доминошек чётно; аналогично, общее
число горизонтальных доминошек чётно. Но общее число доминошек есть нечётное число 152; противоречие.

Решение 2. Предположим, что утверждение задачи неверно. Имеется 15 пар сыгравших между собой ма-
стеров и столько же пар сыгравших между собой юниоров. Далее опускаем слова "сыгравших между собой".
Пусть A,B — пара мастеров. Пусть есть k таких пар юниоров, что A сыграл с обоими игроками пары. Тогда B
ни с кем не играл в этих парах. Далее, в этом случае есть 15−2k пар юниоров, в которых есть один сыгравший
с A. Тогда B мог сыграть в этих парах только с теми 15 − 2k юниорами, с которыми сыграл A. На самом деле,
B сыграл с ними всеми, так как иначе он должен был сыграть более чем с 2k юниорами из оставшихся k пар.
Если же B сыграл с указанными 15 − 2k юниорами, то в оставшихся k парах он сыграл с обоими юниорами. В
этих парах A не сыграл ни с кем.
Таким образом, паре мастеров соответствует чётное количество (2k) пар юниоров, в которых один из этих
мастеров сыграл с обоими, а другой ни с одним, и нечётное количество (15 − 2k) пар юниоров, в которых,
наоборот, один из юниоров сыграл с обоими мастерами, а другой ни с одним. Будем говорить, что в первом
случае пара мастеров и пара юниоров образуют четвёрку первого типа, а во втором — четвёрку второго ти-
па. Просуммируем количество четвёрок каждого типа для всех пар мастеров. Поскольку количество этих пар
нечётно (равно 15), общее количество четвёрок второго типа нечётно. При этом общее количество четвёрок
первого типа чётно. Но в проведённом рассуждении можно поменять местами мастеров и юниоров и получить
противоположный результат! Противоречие.
Комментарий. Любое правильное решение этой задачи должно использовать нечётность числа 15. Если 15
и 30 заменить на 2n и 4n, где n натуральное, то утверждение задачи будет неверно. C