Чанакчи И. — олимпиадные задачи по математике - сложность 5 с решениями

Задача № 166608

Рассмотрим на клетчатой плоскости такие ломаные с началом в точке $(0,0)$ и вершинами в точках с целыми координатами, что каждое очередное звено идет по сторонам клеток либо вверх, либо вправо. Каждой такой ломаной соответствуетчервяк — фигура, состоящая из клеток плоскости, имеющих хотя бы одну общую точку с этой ломаной. Докажите, что червяков, которых можно разбить на двуклеточные доминошки ровно $n>2$ различными способами, столько же, сколько натуральных чисел, меньших $n$ и взаимно простых с $n$. (Червяки разные, если состоят из разных наборов клеток.)