|
|
 |
Условие
Рассмотрим на клетчатой плоскости такие ломаные с началом в точке (0, 0) и вершинами в целых точках, что каждое очередное звено идёт по сторонам клеток либо вверх, либо вправо. Каждой такой ломаной соответствует червяк – фигура, состоящая из клеток плоскости, имеющих хотя бы одну общую точку с этой ломаной. Докажите, что червяков, которые можно разбить на двуклеточные доминошки ровно $n > 2$ различными способами, столько же, сколько натуральных чисел, меньших $n$ и взаимно простых с $n$. (Червяки разные, если состоят из разных наборов клеток.)
Решение
Разным ломаным соответствуют разные червяки: если две ломаные совпадают до точки $A$, а в ней расходятся, то соответствующие червяки содержат разные клетки (рис. 1) – синюю, если из $A$ сделан ход вправо, красную – если вверх, ни одной из них, если ломаная в $A$ окончилась.
Будем покрывать червяка доминошками с конца. Две последние клетки червяка можно покрыть двумя способами.
Операция А: положим доминошку перпендикулярно последнему звену ломаной (рис. 2); пусть есть $a$ способов покрыть оставшуюся часть червяка.
Операция $B$: положим две доминошки параллельно последнему звену ломаной (рис. 3); пусть есть $b$ способов покрыть оставшуюся часть червяка.
Будем говорить, что червяк (и соответствующая ломаная) имеет тип $(a, b)$. Например, простейший червяк, соответствующий ломаной из одного звена, имеет тип (2, 1) (рис. 4).
Число способов разбить червяк типа $(a, b)$ на доминошки равно $a + b$. Ясно, что $a > b$.
Лемма 1. Если ломаную типа $(a, b)$ продолжить звеном, параллельным её последнему звену, то получится ломаная типа $(a+b, a)$.
Доказательство. Если к новому червяку применить операцию А, то останется червяк, соответствующий исходной ломаной (рис. 5). А его можно покрыть $a+b$ способами. Если же применить операцию $B$, то останется то же самое, что при применении операции А к исходному червяку (рис. 6).
Лемма 2. Если ломаную типа $(a, b)$ продолжить звеном, перпендикулярным её последнему звену, то получится ломаная типа $(a+b, b)$.
Доказательство. Если к новому червяку применить операцию А, то, как и в лемме 1, останется червяк, соответствующий исходной ломаной (рис. 7). Если же применить операцию B, то следующую доминошку можно положить единственным способом, после чего останется то же самое, что при применении операции $B$ к исходному червяку (рис. 8).
Лемма 3. Если червяк имеет тип $(a, b)$, то $a$ и $b$ взаимно просты.
Доказательство. Все червяки получаются из простейшего типа (2, 1) добавлением звеньев, а при переходах, описанных в леммах 1 и 2, взаимная простота не нарушается.
Поскольку НОД($n, a$) = 1 тогда и только тогда, когда НОД($n, n-a$) = 1, то для решения задачи осталось доказать, что для каждого натурального $n \geqslant 3$ и взаимно простого с $n$ числа $a$, такого что n/2 < $a < n$, существует ровно два червяка типа $(a, n - a)$.
Достаточно рассмотреть червяков, у которых первое звено горизонтально (их вдвое меньше). Проведём индукцию по $n$. База ($n$ = 3) очевидна.
Шаг индукции. Пусть $n > 3, n-a = b, a - b = c$. Если $b > c$, то ломаную типа $(a, b)$ можно получить только добавлением звена к ломаной типа $(b, c)$ способом, описанным в лемме 1, а такая ломаная единственна по предположению индукции.
Если же $b < c$, то ломаную типа $(a, b)$ можно получить только добавлением звена к ломаной типа $(c, b)$ способом, описанным в лемме 2, а такая ломаная также единственна по предположению индукции.
Замечания
12 баллов
