Задание №175405: Задание 4

4. При каком наименьшем k на числовой прямой можно отметить k точек таким образом, чтобы для
каждого натурального числа n от 1 до 100 нашлись две отмеченные точки, расстояние между которыми
равно 2n? (И. Рубанов)
Ответ. При k = 101.
Первое решение. Пример. При k = 101 можно отметить точки 2, 22, …, 2101: для каждого n от 1 до 100
расстояние от 2n до 2n+1 равно 2n. Оценка. Пусть отмечено k < 101 точек. Для каждого n от 1 до 100 соединим
ниткой две точки на расстоянии 2n. Если есть точка, из которой выходит ровно одна нитка, удалим ее вместе
с ниткой и будем делать так до тех пор, пока это возможно. Таким путем мы сможем удалить не больше 99
вершин, а, значит, и ниток. Поэтому, когда процесс удаления закончится, из каждой точки либо не будет
выходить ниток, либо будет выходить не меньше двух ниток. Возьмем точку, из которой выходит хотя бы
две нитки, и пойдем из нее по ниткам, идя каждый раз в точку, где мы еще не были, пока это возможно.
Когда мы попадаем в еще не пройденную точку, мы можем идти дальше, так как из нее выходит еще хотя бы
одна нитка. Так как точек конечное число, когда-то мы придем в точку, где уже были, и получим замкнутый
маршрут. Возьмем в нем самую длинную нитку. Так как 2k > 2k–1+2k–2+…+21, эта нитка длиннее суммы всех
остальных пройденных. Но тогда мы, выйдя из одного ее конца, не сможем прийти по остальным ниткам
маршрута в другой. Получили противоречие с замкнутостью маршрута, доказывающее, что k  101.
Замечание. Те, кто знаком с понятием графа, конечно, поняли, что рассуждение про веревочки — это
доказательство, что если в графе ребер не меньше, чем вершин, то в нем есть цикл.
Второе решение. Докажем по индукции, что если среди расстояний между несколькими точками на числовой
прямой встречаются n разных степеней двойки, то точек хотя бы n+1. При n = 1 это очевидно. Предположим,
что это доказано для любых m < n степеней двойки, и рассмотрим точки, среди расстояний между которыми
есть n разных степеней двойки. Выберем из этих степеней наибольшую 2c — пусть это расстояние между

точками A и B — а для каждой меньшей степени двойки 2t отметим ровно одну пару точек на таком
расстоянии. Назовём ближними точку A и все точки, в которые можно попасть из A, перемещаясь (возможно,
несколько раз) из одной точки отмеченной пары в другую. Остальные точки назовем дальними. Точка B —
дальняя, так как расстояние до неё, равное 2c, больше любой суммы меньших степеней двойки. Если среди
расстояний между ближними точками встречаются a степеней двойки, ближних точек (по предположению)
не менее a+1. Все остальные n–1–a степеней двойки среди наших расстояний, меньших 2c, встречаются
среди дальних точек. Следовательно, дальних точек не менее n–a, а всего точек не менее, чем
(a+1)+(n–a) = n+1, что и требовалось.