Question

С одной стороны теннисного стола стоит очередь из n девочек, а с другой — очередь из n мальчиков. И девочки, и мальчики пронумерованы от 1 до n в том порядке, в котором они стоят. В первую игру играют девочка и мальчик с номером 1, а затем, после каждой игры, проигравший уходит в конец своей очереди, а победитель остается за столом. Через некоторое время оказалось, что каждая девочка сыграла с каждым мальчиком ровно одну партию. Докажите, что если n нечетно, то в последней игре играли девочка и мальчик с нечетными числами.

Answer 1

Задачу можно переформулировать

Пусть $n$ — нечетное целое число. Рассмотрим путь Гамильтона на $(\mathbb{Z}/n\mathbb{Z})^2$, где я могу перейти к $(x+1,y)$ или $(x,y+1)$ только из $(x,y)$. Путь Гамильтона начинается с $(0,0)$. Докажите, что если оно заканчивается на $(a,b)$, где $0\le a,b < n$, то $a,b$ четны

Доказательство

Рассматривая $x+y$ в $\mathbb{Z}/n\mathbb{Z}$, мы видим, что квадрат назначения имеет $x+y=-1$. Скажем, что $(x,y)$ указывает направо, если $(x,y)$ переходит в $(x+1,y)$, и скажем, что в противном случае он указывает вверх. Если зафиксировать $j \in \{0,\cdots, n-2\}$, то все квадраты $(x,y)$ на прямой $x+y=j$ в $\mathbb{Z}/n\mathbb{Z}$, направлены в одну сторону (возможно, в зависимости от $j$).

Зафиксируем $j$. Предположим, что $x+y=j$ и $(x,y)$ указывает на $(x,y+1)$. Поскольку $(x-1, y+1)$ не является конечной точкой, она должна на что-то указывать, а именно на $(x-1,y+2)$, так как она не может указывать на $(x,y+1)$. Затем мы можем провести индукцию по $k$и убедиться, что $(x_e-k, y_e+k)$ указывает на $(x_e-k, y_e+k+1)$. Это работает, поскольку все точки на $x+y=j$ должны на что-то указывать, так как они не являются конечными

Теперь предположим, что $(x,y)$, где $x+y=n-1$ - конечная точка.  $x,y\ne 0$, или мы закончили. Следовательно, $(0,n-1)$ указывает направо, поскольку ничто не указывает на $(0,0)$. По индукции по $k$ мы видим, что $(k,n-1-k)$ указывает направо для $k=1,2,\cdots,x-1$. Также $(n-1,0)$ указывает вверх, так как ничто не указывает на $(0,0)$. По индукции по $k$ видно, что $(n-1-k,k)$ указывает вверх для $k=1,\cdots,y-1$

Отсюда вытекает следующая задача

Рассмотрим путь на $\mathbb{Z}/n\mathbb{Z}$, начинающийся в точке 0, и из $x$ переходящий в $x+a+1$, если $R(x+a,n) \ in \{0,\cdots,x_e-1\}$, и в $x+a$ иначе, если $x+a$ находится среди $\{x_e+1, \cdots, n-1\}$. Мне нужно убедиться, что этот путь посещает все элементы $\mathbb{Z}/n\mathbb{Z}$ за $n$ чисел (считая начальный 0)

Решение

Рассмотрим перестановку $\{0,1,\cdots,n-1\}$ с гамильтоновым путем и $x_e-a\to 0$. Поскольку эта перестановка является нечетным циклом, то она четная. Однако она также является $\pi_1 \circ \pi_2$, где $\pi_2(x)=x+a$ и $\pi_1 = (0 1 \cdots x_e)$. Отсюда $sgn(\pi_1) sgn(\pi_2) = 1$. Заметим, что $\pi_2$ разлагает $\mathbb{Z}/n\mathbb{Z}$ на циклы длины $\gcd(a,n)$, которая нечетна, поэтому $\pi_2$ является четной перестановкой. $\mathrm{sgn}(\pi_1) = (-1)^{x_e}$, поэтому $x_e$ - четная

Answer 2

Давайте рассмотрим ситуацию, когда n нечетно, и докажем, что в последней игре играли девочка и мальчик с нечетными номерами.

Пусть n = 2k + 1, где k - некоторое целое число. Это означает, что у нас есть 2k пар мальчиков и девочек с четными номерами (2, 4, 6, ..., 2k) и одна пара с нечетными номерами (1 и 2k + 1).

Давайте рассмотрим, что происходит после каждой игры:

1. После первой игры остаются пары (2, 1), (3, 4), (5, 6), ..., (2k, 2k-1), (2k+1, 2k+2).

2. После второй игры остаются пары (3, 2), (5, 4), ..., (2k+1, 2k), (2, 2k+2).

3. Продолжая таким образом, после (2k - 1)-й игры останутся пары (2k+1, 2), (3, 4), ..., (2k-3, 2k-2), (2k-1, 2k).

4. После 2k-й игры останутся пары (3, 2k+1), (4, 2), (5, 6), ..., (2k-3, 2k-2), (2k-1, 2k).

5. После (2k+1)-й игры останется только пара (3, 2k+1).

Мы видим, что после (2k+1)-й игры останется только одна пара, и это пара с номерами 3 и 2k+1, которые оба нечетные. Таким образом, мы доказали, что в последней игре играли девочка и мальчик с нечетными номерами, как и требовалось доказать.