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

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

Условие

На числовой оси отмечено бесконечно много точек с натуральными координатами. Когда по оси катится колесо, каждая отмеченная точка, по которой проехало колесо, оставляет на нём точечный след. Докажите, что можно выбрать такое действительное $R$, что если прокатить по оси, начиная из нуля, колесо радиуса $R$, то на каждой дуге колеса величиной в $1^\circ$ будет след хотя бы одной отмеченной точки.


Решение 1

  Разделим колесо на 360 дуг и занумеруем их, начиная с точки $O$ в порядке "прокатывания". Докажем индукцией по $k$, что можно выбрать окружность длины 360s, прокатив которую по прямой, мы получим следы внутри первых $k$ дуг.
  База  ($k = 1$).  Достаточно выбрать $s$, большее координаты первой отмеченной точки.
  Шаг индукции. По предположению индукции найдётся $s_k$, при котором следы оставлены на первых $k$ дугах. Пусть они оставлены точками с координатами $n_1, ..., n_k$.
  Заметим, что незначительное изменение $s$ не повлияет на ситуацию: те же точки оставят следы на тех же дугах. Пусть это происходит для всех  $s \in (s_k(1 - \varepsilon), s_k(1 + \varepsilon))$.  Рассмотрим отмеченную точку с координатой  $n_{k+1}$ > max {$n_1, ..., n_k, 360s_k(\varepsilon^{-1} + 1)$}.  Пусть  $m \leqslant \dfrac{n_{k+1}}{360s_k} < m+1$ ($m$ – целое число). Тогда  $m > \varepsilon^{-1}$.
  Найдём такое  $s_{k+1} \in (s_k(1 - \varepsilon),  s_k(1 + \varepsilon))$,  чтобы точка $n_{k+1}$ оставила след на данном расстоянии (по окружности) $360ts_{k+1}$ от $O$ (число  $t < 1$  выберем так, чтобы этот след оказался на ($k+1$)-й дуге окружности, соответствующей $s_{k+1}$). Иными словами,  $n_{k+1} = 360(ms_{k+1} + ts_{k+1})$,  откуда  $s_{k+1} = \dfrac{n_{k+1}}{360(m+t)} = \dfrac{r}{m+t}$,  где  $r = \dfrac{n_{k+1}}{360} < (m + 1)s_k$.   Это значение подходит, поскольку  $-\dfrac{r}{m(m+1)} < r\left(\dfrac{1}{m+1} - \dfrac{1}{m+t}\right) < s_k-s_{k+1} \leqslant r \left(\dfrac{1}{m}-\dfrac{1}{m+t}\right) < \dfrac{r}{m(m+1)},$   а  $\dfrac{r}{m(m+1)} < \dfrac{s_k}{m} < \varepsilon s_k$.


Решение 2

  Пусть на числовой прямой отмечено бесконечное число натуральных точек $t_1, t_2, t_3, ...$
  Докажем индукцией по $n$ такое утверждение: для любого набора положительных чисел $a_1, ..., a_n$ с суммой 1 найдётся колесо такой длины $S$, что разделив его на дуги длин $a_1S, ..., a_nS$ (именно в таком порядке) и запустив из 0 (поставив в 0 началом первой дуги), мы обязательно получим строго внутри каждой из дуг след какой-то отмеченной точки.
  Для наглядности покрасим каждую дугу в свой цвет и прокатим колесо по прямой, считая, что каждая точка прямой окрашивается в цвет дуги, которая по точке проезжает. Тогда прямая разобьётся на отрезки $n$ разных цветов, соответствующих дугам. Нам надо найти такую длину колеса, чтобы для каждого цвета нашлась отмеченная точка, попавшая внутрь отрезка этого цвета. Заметим, что если для данного набора нужное $S$ найдено, то подойдёт также любое колесо чуть меньшей или чуть большей длины.
  База  ($n = 1$)  очевидна: можно взять колесо иррациональной или просто достаточно большой длины.
  Шаг индукции. Пусть для всех наборов из $n$ чисел утверждение доказано. Докажем его для набора $a_1, ..., a_n, a_{n+1}$. Рассмотрим набор  $a_1, ..., a_{n-1}, a_n + a_{n+1}$.  Для него нужное $S$ найдётся. Рассмотрим момент, когда в каждой из дуг для этого набора образуется след от отмеченной точки.
  Это соответствует тому, что отмеченные точки $t_{i_1},\ldots,t_{i_n}$ лежат на прямой строго внутри отрезков n разных цветов, точка лежит на отрезке длины  $(a_n + a_{n+1})S$.  Если точка $t_{i_n}$ делит свой отрезок как раз в отношении  $a_n : a_{n+1}$,  увеличим немного $S$, чтобы все точки $t_{i_1},\ldots,t_{i_n}$ попали на свои же "растянутые" отрезки, но точка $t_{i_n}$ уже делила бы свой отрезок в другом отношении.
  Теперь вернёмся к набору $a_1, ..., a_n, a_{n+1}$, прокатим колесо найденной длины S по прямой.
  Точки $t_{i_1},...,t_{i_n}$ попадут в отрезки разных цветов, и только отрезки одного, скажем, зелёного цвета (соответствующие одной из дуг $a_nS, a_{n+1}S$, пусть дуге $a_{n +1}S$), возможно, не содержат ни одной отмеченной точки.
  Заметим, что есть сколь угодно большие отмеченные точки, на расстоянии не более чем $S$ слева от которых есть зелёный отрезок. Пусть мы можем делать гомотетию с коэффициентом, не большим  $1+\varepsilon$  так, чтобы точки $t_{i_1},\ldots,t_{i_n}$ остались внутри своих "растянутых" отрезков.
  Проедем колесом настолько большое расстояние $K$, чтобы колесо сделало целое число оборотов (последний окрашеный отрезок $Z$ зелёный), уже собрало отметки на все дуги, кроме последней, чтобы $K_{\varepsilon}$ было больше $S$, и чтобы на расстоянии не более $S$ после точки $K$ нашлась отмеченная точка $t_{i_{n+1}}$.
  Увеличим длину колеса, сделав гомотетию с коэффициентом  $1 + x$,  где  $x < \varepsilon$.  Тогда зелёный отрезок $Z$ растянется, его новыми концами будут точки  $K + xK - (1 + x)Sa_{n+1}$  и  $K + xK$  соответственно. Очевидно, можно подобрать  $x < \varepsilon$  так, чтобы  $K + Kx$  стало больше $t_{i_{n+1}}$ (ведь  $K\varepsilon > S$),  но при этом больше на величину, меньшую $Sa_{n+1}$. Тогда  $K + xK - (1 + x)Sa_{n+1}$  будет меньше $t_{i_{n+1}}$,то есть точка $t_{i_{n+1}}$ попадёт на "растянутый" зелёный отрезок $Z$.

Замечания

9 баллов

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

олимпиада
Название Турнир городов
номер/год
Дата 2018/19
Номер 40
вариант
Вариант осенний тур, сложный вариант, 10-11 класс
задача
Номер 6

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

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