Олимпиадные задачи по математике

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

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