Задача 78144

Темы:    [ Индукция в геометрии ] [ Процессы и операции ]

Сложность: 4 Классы: 9,10,11

Условие

Отрезок длиной 3ⁿ разбивается на три равные части. Первая и третья из них называются отмеченными. Каждый из отмеченных отрезков разбивается на три части, из которых первая и третья снова называются отмеченными и т.д. до тех пор, пока не получатся отрезки длиной 1. Концы всех отмеченных отрезков называются отмеченными точками. Доказать, что для любого целого k(1k3ⁿ) можно найти две отмеченные точки, расстояние между которыми равно k.

Решение

Назовём отрезок, у которого оба конца являются отмеченными точками, псевдоотмеченным. Докажем утверждение задачи индукцией по n. Для n = 1 утверждение очевидно. Предположим, что для n = m утверждение задачи верно, тогда докажем его для n = m + 1. Заметим, что в отрезке длины 3^{m + 1}, разбитом на три равные части, первая и третья части являются отрезками длины 3^m и удовлетворяют предположению индукции. Поэтому для любого k такого, что 1k3ⁿ существует псевдоотмеченный отрезок длины k. Теперь заметим, что если в отрезке длины 3^m существует псевдоотмеченный отрезок длины l, то дополнением к нему будут два псевдоотмеченных отрезка (возможно, один из них имеет нулевую длину), прилегающие к концам большого отрезка и имеющие суммарную длину 3^m - l. Тогда если 3^m < k < 2 ^. 3^m, то псевдоотмеченный отрезок длины k существует и состоит из центрального отрезка длины 3^m, а также прилегающих к его концам двух псевдоотмеченных отрезков суммарной длиной k - 3^m, 0k - 3^m3^m. Если же 2 ^. 3^mk3^{m + 1}, то искомый псевдоотмеченный отрезок существует, поскольку существуют два псевдоотмеченных отрезка, прилегающих к концам отрезка длины 3^{m + 1}, суммарной длиной 03^{m + 1} - k3^m, а значит, дополнением к ним является псевдоотмеченный отрезок длины k.

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Номер	21
Год	1958
вариант
Класс	9
Тур	1
задача
Номер	5