ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 66704
Темы:    [ Примеры и контрпримеры. Конструкции ]
[ Числовые неравенства. Сравнения чисел. ]
[ Четность и нечетность ]
Сложность: 4
Классы: 8,9,10,11
В корзину
Прислать комментарий

Условие

Автор: Дидин М.

На улице дома стоят друг напротив друга, всего 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 баллов

Источники и прецеденты использования

олимпиада
Название Турнир городов
номер/год
Номер 39
Дата 2017/18
вариант
Вариант весенний тур, сложный вариант, 8-9 классы
задача
Номер 5

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .