Задача 4. Расстояния — степени двойки

Пример: хватит 101 точки

Сначала найдём, сколько точек точно хватит. Нужно получить сто расстояний: $2, 4, 8, \ldots, 2^{100}$. Проще всего взять одну «опорную» точку и от неё отложить все нужные расстояния.

Отметим точку $0$ и точки $2, 2^2, 2^3, \ldots, 2^{100}$. Это $1+100=101$ точка, все они разные. Для каждого $n$ от $1$ до $100$ расстояние от точки $0$ до точки $2^n$ равно $2^n$ — значит, все нужные расстояния есть.

Итак, $k=101$ годится. Осталось доказать, что при $k\le 100$ так сделать нельзя. Это главная часть задачи. Заметим: простой подсчёт пар здесь не помогает. Из $15$ точек можно составить $\frac{15\cdot 14}{2}=105$ пар — больше ста, поэтому «на каждую степень своя пара» ещё не запрещает $15$ точек. Нужно понять, чем мешают друг другу именно степени двойки.

Дуги и компании

Пусть отмечено $k$ точек и все нужные расстояния есть. Для каждого $n$ от $1$ до $100$ выберем одну пару отмеченных точек на расстоянии $2^n$ и соединим её дугой. Получится $100$ дуг, и все они разной длины: $2, 4, \ldots, 2^{100}$. Две разные дуги не могут соединять одну и ту же пару точек — у одной пары одно расстояние.

Назовём компанией группу точек, которые связаны цепочками дуг: из любой точки компании можно дойти до любой другой, шагая по дугам. Точка без дуг — сама себе компания.

План такой: будем проводить дуги по одной и следить, как меняется число компаний. Покажем, что каждая дуга уменьшает его ровно на $1$. Для этого нужен один факт про степени двойки — шаг 3.

Круг из дуг разной длины не замкнуть

Сначала про сами степени. Сложим $2+2=4$, $4+4=8$, $8+8=16$ и так далее: каждый раз удваиваем. Поэтому

Сумма всех меньших степеней двойки (каждая по одному разу) меньше следующей степени.

Теперь предположим, что несколько дуг разной длины образуют замкнутый круг: $A_1\to A_2\to\ldots\to A_r\to A_1$, каждая дуга круга пройдена один раз. Возьмём в нём самую длинную дугу, пусть её длина $2^M$, а концы $P$ и $Q$. Обойдём круг от $Q$ до $P$ по остальным дугам. Их длины — разные степени двойки, меньшие $2^M$, поэтому всего мы пройдём не больше $2+4+\ldots+2^{M-1}=2^M-2$. Но расстояние от $Q$ до $P$ равно $2^M$, а уйти по прямой дальше, чем прошёл, нельзя. Значит, до $P$ мы не доберёмся — противоречие.

Вывод: дуги разной длины никогда не замыкаются в круг. Важно, что длины разные: дуги $2$, $2$, $4$ между точками $0$, $2$, $4$ круг образуют — но там длина $2$ повторяется.

Каждая дуга сливает две компании

Начнём без дуг: тогда каждая точка — отдельная компания, их $k$. Проведём $100$ дуг по одной, в любом порядке.

Пусть очередная дуга соединяет точки $P$ и $Q$. Могут ли $P$ и $Q$ уже быть в одной компании? Тогда из $Q$ в $P$ ведёт цепочка уже проведённых дуг. Возьмём самую короткую такую цепочку: в ней точки не повторяются, значит, и дуги не повторяются. Цепочка $Q\to\ldots\to P$ вместе с новой дугой $P\to Q$ — замкнутый круг из разных дуг, то есть из дуг разной длины. По шагу 3 такого не бывает.

Значит, $P$ и $Q$ всегда в разных компаниях, и новая дуга сливает эти две компании в одну: компаний становится ровно на $1$ меньше.

После $100$ дуг компаний $k-100$. Но хотя бы одна компания всегда есть (точки же отмечены), поэтому $k-100\ge 1$, то есть $k\ge 101$.

Как это заметить: число компаний — величина, которая от каждой дуги уменьшается ровно на $1$ и не может стать меньше $1$. Поэтому дуг не больше, чем «точек минус одна». В модели это строка «дуг = точек − компаний».

Ответ

По шагу 1 хватает $101$ точки, по шагу 4 меньше $101$ точки не хватит. Наименьшее $k=101$.