|
|
 |
Условие
Назовём рассадку $N$ кузнечиков на прямой в различные её точки $k$-удачной, если кузнечики, сделав необходимое число ходов по правилам чехарды, могут добиться того, что сумма попарных расстояний между ними уменьшится хотя бы в $k$ раз. При каких $N\geqslant2$ существует рассадка, являющаяся $k$-удачной сразу для всех натуральных $k$? (В чехарде за ход один из кузнечиков прыгает в точку, симметричную ему относительно другого кузнечика.)Решение 1
При $N=2$ как бы кузнечики ни прыгали, расстояние между ними не меняется.Пусть $N\geqslant3$. Рассадим 1-го, 2-го и 3-го кузнечиков на прямой в точках с координатами 0, 1, $\sqrt2$, назовём этих кузнечиков $V$, $Q$, $R$. Остальные произвольно рассаживаются в другие попарно различные точки. Покажем, что для всякого $k$ кузнечики далее смогут прыгать так, чтобы сумма попарных расстояний уменьшилась хотя бы в $k$ раз (исходную сумму обозначим через $P$).
Лемма. Пусть три кузнечика сидят на прямой в попарно различных точках и отношение расстояний от одного из них до двух других иррационально. Тогда сколько бы они ни сделали прыжков друг через друга, они всё равно будут в попарно различных точках, и отношение расстояний от одного из них до двух других будет иррационально.
Доказательство леммы. Покажем, что эти условия сохраняются при прыжке. Предположим, для некоторого кузнечика отношение расстояний до двух других рационально, тогда эти расстояния имеют вид $a$ и $aq$, где $q$ рационально. Тогда расстояние между другими двумя кузнечиками ненулевое и имеет вид $|a \pm aq|$, тогда отношение любых двух расстояний между кузнечиками рационально, противоречие. Пусть какой-то кузнечик перепрыгнул через кузнечика $A,$ тогда расстояния от $A$ до обоих кузнечиков не изменились, а значит отношение этих расстояний осталось иррациональным, в частности расстояния различны, и потому кузнечики по-прежнему находятся в попарно-различных точках.
Перейдём к задаче. Пусть первые несколько ходов будут прыгать только кузнечики $V$, $Q$, $R$ и только через друг друга, согласно лемме при таких прыжках они всегда будут оставаться в попарно различных точках. Покажем, что спустя любое количество таких ходов они смогут далее прыгать так, чтобы текущее минимальное из попарных расстояний между ними уменьшилось не менее чем в два раза.
Пусть, не умаляя общности, в текущий момент минимально расстояние между кузнечиками $V$, $Q$ с координатами $a$ и $b$, а $R$ имеет координату $c$. Отметим на прямой все точки с координатами, отличающимися от $a$ на число, кратное $(a-b)$. Понятно, что прыгая друг через друга кузнечики $V$, $Q$ смогут занять любые две соседние отмеченные точки, тогда $R$ не находится в отмеченной точке (по лемме прыгая только через друг друга $V$, $Q$, $R$ остаются в попарно различных точках), тогда $V$, $Q$ могут занять две соседние отмеченные точки между которыми лежит $c$, и расстояние от $R$ до одного из кузнечиков будет не более $|a-b|/2$, то есть наименьшее расстояние уменьшилось хотя бы в 2 раза.
Тогда за несколько ходов кузнечики $V$, $Q$, $R$ могут уменьшить наименьшее расстояние между ними хотя бы в 2 раза, потом за несколько ходов ещё хотя бы в 2 раза, потом ещё, и т.д, могут за несколько ходов добиться того, чтобы расстояние между какими-то двумя из них было равно некоторому числу $t$, меньшему $P/(2N(N-1)\cdot k)$ – пусть они так и сделают. Назовём каких-нибудь двух кузнечиков, между которыми расстояние $t$, хорошими, и одного из них назовём $D$, далее эти кузнечики уже не прыгают.
Далее, любой кузнечик не из пары хороших может прыгая через пару хороших (в подходящем порядке) смещаться на $2t$ в любую сторону на прямой, и тогда может за несколько прыжков через них оказаться на расстоянии меньшем $2t$ от $D$, пусть все кузнечики кроме хороших сделают прыжки таким образом. Тогда расстояние от любого кузнечика до $D$ будет меньше $2t$, а значит, все попарные расстояния меньше $4t$, а значит, их сумма меньше $4t\cdot N(N-1)/2 < P/k$.
Решение 2
Для любого $N>2$ предъявим явно начальную рассадку, которая является $k$-удачной для любого натурального числа $k$.Сначала для данного $N>2$ построим конечную геометрическую прогрессию $1,q,\ldots, q^{N-1}$, со знаменателем $q\in (0,1)$, для которой выполнено условие $1=q+q^2+\ldots+q^{N-1}.$ Требуемый набор существует при любом целом $N>2$, поскольку уравнение $q+q^{2}+\ldots+q^{N-1} - 1 = 0$ имеет решение на интервале $(0,1)$, так как левая часть меняет знак на его концах.
Расположим теперь $N$ кузнечиков в следующих начальных точках:
$$ 0,\; 1,\; (1+q),\; (1+q+q^2),\; \ldots,\; (1+q+\ldots+q^{N-3}),\; (1 + q + \ldots + q^{N-2}).$$
Рассмотрим прыжок первого кузнечика через второго; тогда его новая координата будет равна $2 = 1 + 1 = 1 + q+q^2+\ldots+q^{N-1}$. Получилось, что прыгнувший кузнечик стал самым правым, а все кузнечики теперь расположены в точках
$$ 1,\; (1+q),\; \; (1+q+q^2),\; \ldots,\; (1+q+\ldots+q^{N-2}),\; (1 + q + \ldots + q^{N-1}).$$
Сдвинув начало координат на $1$ вправо, получим координаты кузнечиков
$$ 0,\; q,\; (q+q^2),\; \ldots,\; (q+\ldots+q^{N-2}),\; (q + \ldots + q^{N-1}).$$
Таким образом, кузнечики уменьшили свои координаты ровно в $q$ раз. Если указанный шаг (прыжок самого левого кузнечика через ближайшего соседа) повторять $r$ раз, то попарные расстояния изменятся в $q^r$ раз, что позволит достичь любого нужного уменьшения $1/k$.
