ВсОШ 2023, 10 класс, задача 4

Решение. Будем изображать турнир в виде таблицы , в которой и столбцы, и строки пронумерованы числами от до . Столбцы будут соответствовать девочкам, а строки — мальчикам. Тогда каждая партия задаётся клеткой, координаты которой соответствуют номерам девочки и мальчика, играющих в этой партии. Поставим сначала фишку в клетку . После победы девочки фишка будет перемещаться вверх, а в случае победы мальчика — вправо. При этом если фишка доходит до края таблицы, то из последней строки при движении вверх она перемещается в первую строку, а из последнего столбца при движении вправо — в первый столбец. Тогда условие задачи равносильно тому, что фишка обошла все клетки таблицы, побывав в каждой ровно по одному разу. Раскрасим клетки таблицы в цветов по диагоналям, идущим вправо-вниз: первую диагональ — в первый цвет, вторую — во второй, , -ю диагональ — в -й цвет, а следующие диагонали — снова в цвета с первого по -й. Заметим, что после каждой партии номер цвета клетки, в которой находится фишка, увеличивается на по модулю . Так как всего в турнире было проведено партий, что кратно , то в конце фишка находится в клетке -го цвета, то есть на главной диагонали (далее, говоря «диагональ», мы будем иметь в виду именно эту диагональ). Пусть финальная клетка в маршруте фишки расположена в столбце с номером , тогда требуется доказать, что число нечётно. Из верхней клетки диагонали фишка не могла пойти вверх, так как уже была в клетке (1, 1). Значит, если эта клетка не финальная, то из неё фишка пошла вправо. Тогда и из следующей клетки диагонали она сделала ход вправо, и т.д. до клетки, расположенной в столбце с номером . Аналогично из клеток диагонали, находящихся в столбцах с номерами от до , фишка ходила вверх (см. рис. 3).

Пусть первая клетка диагонали, в которую попала фишка, находится в столбце с номером . Рассмотрим путь фишки от начальной клетки до неё. Все пути от клеток первого цвета до следующей клетки -го цвета должны быть такими же, как и рассматриваемый путь, а именно, каждый такой путь получается из другого смещением на вектор . Действительно, если бы фишка из клетки сделала ход вверх, а из клетки — вправо, то в клетку она бы не попала, а если из этих клеток она делала ходы вправо и вверх соответственно, то попала бы в одну клетку дважды; поэтому из каждых двух таких клеток фишка делала одинаковые ходы. Без ограничения общности будем считать, что . Клетки диагонали, находящиеся левее финальной клетки, будем называть левыми, а находящиеся правее — правыми. Пронумеруем левые клетки числами от до , а правые — от до (и те, и другие нумеруем, двигаясь вправо-вниз). Посмотрим, в каком порядке фишка обходила эти клетки. С левых клеток она смещалась на клеток вправо (поскольку с них в клетку первого цвета она делала ход вправо), а с правых клеток — на клетку вправо. Значит, для левых клеток нам важен лишь остаток от деления номера на , а для правых — от деления на . При этом, если правых клеток меньше , то можно увеличить на , добавив правых клеток; это не повлияет на дальнейшие рассуждения. Для удобства заменим все номера клеток на соответствующие остатки, причём для правых клеток вместо остатка 0 будем использовать число . Пусть число при делении на даёт остаток . Тогда первый переход с левых клеток на правые был с числа на число , и в этот момент все клетки с нулём в левой части были посещены. На диагонали остались только числа от до . Дальше цепочка переходов между правыми и левыми клетками выглядит так: . В этой цепочке каждое число от до встречается два раза, начинается она на правых клетках, а заканчивается на левых. Переходы с правых клеток на левые будем называть переходами первого типа, а с левых на правые — второго. Тогда в цепочке переход первого типа и перехода второго, и они чередуются. Докажем, что каждые два числа в цепочке, симметричные относительно её центра, дают в сумме . Для крайних чисел это верно. Каждые два симметричных перехода имеют один тип, поэтому в них по модулю (для переходов первого типа) или по модулю (для переходов второго типа) прибавляется одно и то же число. Значит, сумма следующих двух симметричных чисел (которые ближе к центру цепочки) снова равна либо по модулю , либо по модулю . Но сумма самих чисел не меньше и не больше , поэтому она может быть равна только . Предположим, что число чётно, и рассмотрим два случая. 1) Число нечётно. Тогда центральный переход в цепочке имеет второй тип. У правой нижней клетки диагонали нечётный номер, поскольку число нечётно, а чётно. Левая верхняя клетка диагонали тоже имеет нечётный номер, поэтому при переходе первого типа чётность числа меняется. Пусть с числа переход первого типа происходит на число . Тогда по модулю переходы первого типа выглядят так: , , , . Суммы чисел в этих парах являются последовательными нечётными числами, поэтому при делении на они дают все нечётные остатки по два раза. В частности, есть переход, в котором сумма чисел равна по модулю . Как показано выше, эта сумма равна . Но тогда для этого перехода симметричный ему тоже имеет первый тип и содержит те же самые числа, то есть один из переходов повторился, чего быть не должно. 2) Число чётно. Тогда у центрального перехода в цепочке первый тип. Последняя левая клетка имеет нечётный номер, так как число нечётно, а чётно. У первой правой клетки тоже нечётный номер, значит, при переходе второго типа чётность числа не меняется. Аналогично первому случаю можно показать, что среди них найдётся переход, пара чисел в котором даёт сумму , и получаем такое же противоречие.

Замечание. После описания того, в каком порядке фишка обходит клетки диагонали (с левых сдвигается вправо на клеток, а с правых — на ) решение можно завершить по-другому. Пронумеруем все клетки диагонали числами от до слева направо. Проведём стрелку из каждой клетки в клетку, в которой фишка появляется в следующий раз; эти стрелки образуют путь, начинающийся в клетке и заканчивающийся в клетке . Добавим стрелку, ведущую из клетки в клетку ; получим цикл, проходящий по всем клеткам диагонали. Этот цикл определяет перестановку чисел , где — это номер клетки, в которую ведёт стрелка из клетки . Эта перестановка — цикл на элементах. Напомним, что перестановка, являющаяся циклом на элементах, имеет чётность, отличную от чётности числа . Поэтому перестановка чётна. С другой стороны, получается как композиция (последовательное применение) двух перестановок: , которая отправляет , и , действующей как . Перестановка состоит из нескольких циклов одинаковой длины; поэтому эти циклы нечётной длины, и потому чётна. Значит, и чётна, что как раз и означает, что нечётно.