Задача № 1667588 класс9 класс10 класс11 класс3 / 5
Рассмотрим на клетчатой плоскости такие ломаные с началом в точке (0, 0) и вершинами в целых точках, что каждое очередное звено идёт по сторонам клеток либо вверх, либо вправо. Каждой такой ломаной соответствует червяк – фигура, состоящая из клеток плоскости, имеющих хотя бы одну общую точку с этой ломаной. Докажите, что червяков, которые можно разбить на двуклеточные доминошки ровно n>2 различными способами, столько же, сколько натуральных чисел, меньших n и взаимно простых с n. (Червяки разные, если состоят из разных наборов клеток.)
Задача № 1666089 класс10 класс11 класс5 / 5
Рассмотрим на клетчатой плоскости такие ломаные с началом в точке (0,0) и вершинами в точках с целыми координатами, что каждое очередное звено идет по сторонам клеток либо вверх, либо вправо. Каждой такой ломаной соответствуетчервяк — фигура, состоящая из клеток плоскости, имеющих хотя бы одну общую точку с этой ломаной. Докажите, что червяков, которых можно разбить на двуклеточные доминошки ровно n>2 различными способами, столько же, сколько натуральных чисел, меньших n и взаимно простых с n.
(Червяки разные, если состоят из разных наборов клеток.)