|
|
 |
Условие
Рассмотрим на клетчатой плоскости такие ломаные с началом в точке $(0,0)$ и вершинами в точках с целыми координатами, что каждое очередное звено идет по сторонам клеток либо вверх, либо вправо. Каждой такой ломаной соответствует червяк — фигура, состоящая из клеток плоскости, имеющих хотя бы одну общую точку с этой ломаной. Докажите, что червяков, которых можно разбить на двуклеточные доминошки ровно $n>2$ различными способами, столько же, сколько натуральных чисел, меньших $n$ и взаимно простых с $n$. (Червяки разные, если состоят из разных наборов клеток.)Решение
Каждой ломаной, звенья которой идут только вверх и вправо, соответствует слово — последовательность букв $U$ (вверх) и $R$ (вправо). Пусть $w$ — любое слово и пусть $W(w)$ — червяк, соответствующий ломаной, закодированной с помощью $w$. Также обозначим за $D(w)$ количество способов разбить червяка $W(w)$ на доминошки.
Лемма. Выполняются следующие реккурентные соотношения: \begin{alignat*}2 D(wUU) &= D(wU) + D(w), &\quad D(wRR) &= D(wR) + D(w),\\ D(wUR) &= 2D(wU) - D(w), &\quad D(wRU) &= 2D(wR) - D(w). \end{alignat*}
Доказательство.
Для доказательства первого соотношения рассмотрим доминошку, которая покрывает самую правую из самых верхних клеток $W(wUU)$. Если она горизонтальна, то оставшийся червяк совпадает с $W(wU)$. Если же она вертикальна, то клетка слева от нее также может быть покрыта только вертикальной доминошкой, и тогда червяк, который остался не покрыт, совпадает с $W(w)$.
Второе соотношение получается аналогично.
Для доказательства третьего соотношения снова рассмотрим доминошку, которая покрывает самую правую из самых верхних клеток в червяке $W(wUR)$. Если она вертикальна, то оставшийся червяк совпадает с $W(wU)$. Если же она горизонтальна, то под ней и слева от нее по одной доминошке определяются однозначно (горизонтально и вертикально соответственно).
Обозначим фигуру, остающуюся после удаления этих трех доминошек, через $\Phi$ (эта фигура может и не быть червяком). Количество способов разбить фигуру $\Phi$ на доминошки равно разности $D(wUR)-D(wU)$. Рассмотрим теперь червяка $W(wU)$ и его доминошку, которая покрывает самую правую из самых верхних клеток. Если она горизонтальна, то оставшийся червяк совпадает с $W(w)$. Если же она вертикальна, то слева от нее расположена еще одна вертикальная. Заметим, что если удалить эти две вертикальные доминошки, то остается в точности фигура $\Phi$. Таким образом, разность $D(wU)-D(w)$ тоже равна числу способов разбить фигуру $\Phi$ на доминошки.
Равенство $D(wUR)-D(wU)=D(wU)-D(w)$ равносильно третьему соотношению.
Четвертое соотношение доказывается аналогично.
Доказательство леммы закончено.
Теперь пусть $n$ — натуральное число, и пусть $W(w)$ — червяк, которого можно разбить на доминошки $n$ различными способами. Пусть $w = w_1w_2\ldots w_\ell$ — разбиение $w$ на буквы. Рассмотрим последовательность \begin{align*} D(‟”),\ D(w_1),\ D(w_1w_2),\ \ldots,\ D(w_1w_2\ldots w_{\ell - 1}) = m, \\ D(w_1w_2\ldots w_\ell) = D(w) = n. \end{align*} (Через ‟” обозначено пустое слово: соответствующий ему червяк является квадратом $2 \times 2$, для которого $D(‟”)= 2$.)
По лемме, если $a$ и $b$ — два последовательных члена этой последовательности, то следующий член равен или $a + b$, или $2b - a$. Давайте разберем некоторые свойства этой последовательности.
Так как $D(‟”) = 2$ и $D(U) = D(R) = 3$, два первых члена любой последовательности равны двум и трем соответственно. По индукции легко видеть, что любые два последовательных члена этой последовательности взаимно просты. Кроме того, для двух последовательных членов $a$, $b$ этой последовательности $a < b < 2a$.
С другой стороны, по данным взаимно простым $m$ и $n$ таким, что $m < n < 2m$, мы можем построить ровно одну такую последовательность, что $m$ и $n$ — ее последние члены.
В самом деле, если $3m < 2n$, то предыдущий член должен быть равен $n- m$, поскольку $2(2m - n) < m$, а если $3m > 2n$, то предыдущий член последовательности должен быть равен $2m - n$, поскольку $2(n - m) < m$. Продолжая этот процесс, в конечном счете мы придем к 3 и 2, завершая последовательность.
Для данной последовательности есть ровно два червяка, которые удовлетворяют ей. Первая буква $w_1$ слова $w$ может быть выбрана любой, но все следующие буквы восстанавливаются однозначно.
Таким образом, каждой паре взаимно простых чисел $m$ и~$n$, для которых выполнено $m < n < 2m$, соответствует ровно два червяка, которых можно разбить на доминошки ровно $n$ способами. При этом количество чисел, меньших $n$ и взаимно простых с $n$, также ровно вдвое больше количества пар $m$ и $n$, поскольку каждое такое число равно либо $m$, либо $n - m$. Значит, червяков, которые можно разбить на двуклеточные доминошки ровно $n$ различными способами, столько же, сколько натуральных чисел, меньших $n$ и взаимно простых с $n$.
Комментарий. Факт, который требовалось доказать в задаче, является побочным результатом научной статьи И. Чанакчи и Р. Шиффлера, в которой исследуется связь между кластерными алгебрами и цепными дробями.
