Задача
Отрезок длиной 3nразбивается на три равные части. Первая и третья из них называются отмеченными. Каждый из отмеченных отрезков разбивается на три части, из которых первая и третья снова называются отмеченными и т.д. до тех пор, пока не получатся отрезки длиной 1. Концы всех отмеченных отрезков называются отмеченными точками. Доказать, что для любого целогоk(1$\le$k$\le$3n) можно найти две отмеченные точки, расстояние между которыми равноk.
Решение
Назовём отрезок, у которого оба конца являются отмеченными точками, псевдоотмеченным.
Докажем утверждение задачи индукцией поn. Дляn= 1 утверждение очевидно. Предположим, что дляn=mутверждение задачи верно, тогда докажем его дляn=m+ 1.
Заметим, что в отрезке длины 3m + 1, разбитом на три равные части, первая и третья части являются отрезками длины 3mи удовлетворяют предположению индукции. Поэтому для любогоkтакого, что1$\le$k$\le$3nсуществует псевдоотмеченный отрезок длиныk.
Теперь заметим, что если в отрезке длины 3mсуществует псевдоотмеченный отрезок длиныl, то дополнением к нему будут два псевдоотмеченных отрезка (возможно, один из них имеет нулевую длину), прилегающие к концам большого отрезка и имеющие суммарную длину 3m-l. Тогда если3m<k< 2 . 3m, то псевдоотмеченный отрезок длиныkсуществует и состоит из центрального отрезка длины 3m, а также прилегающих к его концам двух псевдоотмеченных отрезков суммарной длинойk- 3m,0$\le$k- 3m$\le$3m. Если же2 . 3m$\le$k$\le$3m + 1, то искомый псевдоотмеченный отрезок существует, поскольку существуют два псевдоотмеченных отрезка, прилегающих к концам отрезка длины 3m + 1, суммарной длиной0$\le$3m + 1-k$\le$3m, а значит, дополнением к ним является псевдоотмеченный отрезок длиныk.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь