Олимпиадная задача по теории чисел: турнир с 15 командами, индукция, задача Шаповалова
Задача
В однокруговом турнире участвовали 15 команд.
а) Докажите, что хотя бы в одной игре встретились команды, которые перед этой игрой участвовали в сумме в нечётном числе игр этого турнира.
б) Могла ли такая игра быть единственной?
Решение
a) Первый способ. Сложим эти суммы для всех игр. Каждая из 15 команд вносит в результат нечётный вклад: 0 + 1 + 2 + ... + 13. Значит, в результате получится нечётное число. Следовательно, хотя бы одно из слагаемых-сумм было нечётным. Второй способ. Предположим противное: все игры делятся на чётные (к которым обе команды подошли с чётным "багажом") и нечётные. Каждая команда участвовала в семи чётных играх, значит, всего чётных игр 15·7 : 2 – нецелое число. Противоречие. б) Первый способ. Покажем, что если расписание турнира с одной "нечётной" игрой возможно для n команд, то оно возможно и для n + 4 команд. После проведения турнира n старых команд, добавим новые команды A, B, C и D. Проведём игры A-B, C-D, A-C, B-D и A-D. Команды A и B сыграли разное по чётности число игр (3 и 2), поэтому одна из старых команд S может сыграть с ними (в том или другом порядке). После этого S может сыграть с командами C и D. При этом все новые сыграют по разу, то есть разные чётности в парах A и B, C и D сохранятся. Поэтому можно повторять процедуру с каждой из остальных старых команд, а в конце провести заключительный матч B-C.
Поскольку в турнире трёх команд одна "нечётная" игра, то, как показано выше, можно провести такой турнир и для семи, а, значит, и для 11 и 15 команд. Второй способ. Предположим, что команда 15 прибывает с опозданием, а турнир начинают команды с номерами от 1 до 14. Они проводят первые 12 туров обычного однокругового турнира в 13 туров. В каждом туре играют между собой команды, сыгравшие до этого одинаковое количество игр, так что желаемая сумма всегда будет чётной. Пусть команда 15 прибывает после того, как сыграны первые три игры 13-го тура. На этот момент восемь команд (группа A) сыграли по 12 игр, а шесть (группа B) – по 13. Теперь команда 15 играет против команд из групп A и B поочередно, пока не сыграет с семью командами из A. Желаемая сумма в каждой из этих 13 игр чётна. Затем команда 14 играет с восьмой командой из A, при этом сумма нечётна. После этого проходят оставшиеся четыре игры 13-го тура, каждая с чётной суммой.
Ответ
б) Могла.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь