|
|
 |
Условие
На улице дома стоят друг напротив друга, всего 50 пар. На правой стороне улицы расположены дома с чётными натуральными номерами, на левой – с нечётными натуральными номерами, номера возрастают от начала улицы к концу на каждой стороне, но идут не обязательно подряд (возможны пропуски). Для каждого дома на правой стороне улицы нашли разность между его номером и номером дома напротив, и оказалось, что все найденные числа различны. Наибольший номер дома на улице равен $n$. Найдите наименьшее возможное значение $n$.
Решение
Пример. Пусть на каждой стороне улицы номера образуют арифметическую прогрессию: на правой – 2, 4, ..., 100, а на левой – 1, 5, ..., 197. Тогда разности образуют арифметическую прогрессию с шагом $2$, то есть будут различны.
Оценка. Заметим, что все эти разности нечётны.
Первый способ. Подойдём к первому дому на какой-то стороне. Пойдём вдоль улицы, потом около некоторого дома перейдём к противоположному дому, потом продолжим идти вдоль улицы, потом опять у некоторого дома перейдём к противоположному и дойдём до конца. Пока мы шли вдоль улицы, номер каждого следующего дома был хотя бы на 2 больше предыдущего. Значит, разница номеров домов в начале и в конце улицы не меньше, чем $2\cdot 49$ плюс разности номеров в двух парах домов, у которых мы перешли улицу. Покажем, что можно выбрать начальную сторону улицы и две пары домов так, чтобы эти две разности в сумме давали не меньше 98. Тогда мы получим, что у последнего дома номер не меньше 1 + 98 + 98 = 197.
Действительно, все разности различны, поэтому найдутся две, которые отличаются хотя бы на 98. Улицу нужно пересекать как раз у пар домов с этими разностями. Если меньшая из двух разность расположена ближе к началу улицы, чем бόльшая, то нужно начинать обход с чётной стороны. Тогда при переходе улицы она войдёт в сумму с минусом, а бόльшая – с плюсом. Если меньшая разность дальше от начала, то нужно начинать с нечётной стороны.
Второй способ. Пусть $b_1 < ... < b_{50}$ – чётные номера, $a_1 < ... < a_{50}$ – нечётные номера, $d_k = b_k - a_k$. Пусть наименьшая разность $d_i = d$, а наибольшая $d_j = D$. Тогда $D \geqslant d + 2\cdot 49$. Если $i > j$, то $a_i = b_i - d \geqslant b_j + 2(i - j) - d$, а $a_i - a_j \geqslant D - d + 2(j - i) \geqslant 2 (j - i) + 2\cdot 49$. Поэтому $a_{50} - a_1 \geqslant 2\cdot 49 + 2\cdot 49 = 196$, откуда $a_{50}\geqslant 197$. Если $i < j$, то аналогично $b_{50}\geqslant 198$.
Ответ
197.
Замечания
8 баллов
