Конструктивы в алгебре
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
Дана прямолинейная дорога, выложенная из зелёных и красных дощечек (дорога — отрезок, разбитый на отрезки-дощечки). Цвета дощечек чередуются; первая и последняя дощечки — зелёные. Известно, что длины всех дощечек больше сантиметра и меньше метра, а также что длина каждой следующей дощечки больше предыдущей. Кузнечик хочет пропрыгать вперёд по дороге по этим дощечкам, наступив на каждую зелёную дощечку (или границу между соседними дощечками). Докажите, что кузнечик может сделать это так, чтобы среди длин его прыжков встретилось не более 8 различных значений.
Источники:
Подсказка 1
Заметим, что кузнечику нужно точно попадать на зелёные дощечки. Для этого полезно иметь прыжок очень маленькой длины. Представьте, что кузнечик двигается по зелёной дощечке небольшими шагами. Какой минимальный размер прыжка может понадобиться, чтобы достичь границы с красной дощечкой?
Подсказка 2
Чтобы перепрыгнуть красную дощечку длины L (где 1 < L < 100 см), потребуется прыжок длиннее L. Учитывая, что длины дощечек строго возрастают, подумайте: если мы перепрыгнули красную дощечку прыжком длины D, то для следующей (ещё более длинной) красной дощечки потребуется прыжок примерно вдвое больше. Как можно организовать набор прыжков, чтобы покрыть весь диапазон от 1 до >100 см, используя мало различных длин?
Подсказка 3
Рассмотрим прогрессию длин прыжков: l, 2l, 4l, 8l, 16l, 32l, 64l. Будет ли такая последовательность эффективна? Какие ограничения надо наложить на l?
Подсказка 4
Как выбрать l и ε? Самый большой прыжок (64l) должен быть > 100 см (чтобы перепрыгнуть самую длинную красную дощечку), но не сильно. Возьмём l < 2 см (чтобы ε = l/N было достаточно мало при большом N), ε < 0.01 см. Существует ли такое l?
Считаем, что дощечки выложены на числовой прямой. Примем 
Возьмем 
такое, что разность длин любой пары соседних дощечек больше 
Отметим на прямой бесконечную в обе
стороны арифметическую прогрессию с разностью 
так, чтобы концы дощечек не были отмечены. Кузнечик будет прыгать только по
отмеченным точкам, и длины его прыжков будут из множества
где 
а натуральное 
подберём так, что 
и 
Стратегия кузнечика будет такой: прыгать вправо по зелёной дощечке на 
пока возможно, и далее перепрыгивать
очередную красную дощечку прыжком минимальной возможной длины (такая длина найдётся, поскольку длина самого
длинного прыжка больше 
). Итак, пусть сделан прыжок длины 
из зелёного отрезка через очередной красный
отрезок ![[a,b].](/api/latex-service/v1/GetSession/270271/index-4f6d2f2308e9f7234f2f2da3104998dd.svg)
Нам остаётся убедиться, что после этого прыжка кузнечик окажется в следующем зелёном отрезке ![[b,c].](/api/latex-service/v1/GetSession/270271/index-ef999cf6b0a7ff6adeae0e29bc6e40e0.svg)
Предположим, что это не так, и кузнечик из точки 
где 
перепрыгнул в точку 
Видим,
что
значит, в множестве длин прыжков кузнечика есть длина 
Далее, по выбору 
имеем
поэтому можем оценить
Видим, что 
а значит, кузнечик мог из точки 
перепрыгнуть красный отрезок ![[a,b]](/api/latex-service/v1/GetSession/270271/index-0479e9d2672e15009176266790dee44d.svg)
прыжком более коротким,
чем 
Противоречие.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
