С одной стороны теннисного стола выстроилась очередь из n девочек, а с другой — из n мальчиков. И девочки, и мальчики пронумерованы числами от 1 до n в том порядке, как они стоят. Первую партию играют девочка и мальчик с номерами 1, а далее после каждой партии проигравший встаёт в конец своей очереди, а победивший играет со следующим. Через некоторое время оказалось, что каждая девочка сыграла ровно одну партию с каждым мальчиком. Докажите, что если n нечётно, то в последней партии играли девочка и мальчик с нечётными номерами.
1 Ответ
Решение.
Предположим, что число m чётно, и рассмотрим два случая.
1) Число k нечётно. Тогда центральный переход в цепочке имеет второй тип. У правой нижней клетки диагонали нечётный номер, поскольку число n−m нечётно, а k−1 чётно. Левая верхняя клетка диагонали тоже имеет нечётный номер, поэтому при переходе первого типа чётность числа меняется. Пусть с числа 1 переход первого типа происходит на число 2s. Тогда по модулю k − 1 переходы первого типа выглядят так: 1 → 2s, 2 → 2s + 1,
. ., k − 1 → 2s + k − 2. Суммы чисел в этих парах являются последовательными нечётными числами, поэтому при делении на k − 1 они дают все нечётные остатки по два раза. В частности, есть переход, в котором сумма чисел равна 1 по модулю k − 1. Как показано выше, эта сумма равна k. Но тогда для этого перехода симметричный ему тоже имеет первый тип и содержит те же самые числа, то есть один из переходов повторился, чего быть не должно.
2) Число k чётно. Тогда у центрального перехода в цепочке первый тип. Последняя левая клетка имеет нечётный номер, так как число m − 1 нечётно, а k чётно. У первой правой клетки тоже нечётный номер, значит, при переходе второго типа чётность числа не меняется. Аналогично первому случаю можно доказать, что среди них найдётся переход, пара чисел в котором даёт сумму k, и получаем такое же противоречие.