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

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

Условие

Дано иррациональное число α,  0 < α < ½.  По нему определяется новое число α1 как меньшее из двух чисел 2α и  1 – 2α.  По этому числу аналогично определяется α2, и так далее.
  а) Докажите, что  αn < 3/16  для некоторого n .
  б) Может ли случиться, что  αn > 7/40  при всех натуральных n?


Решение 1

  а) Последовательно докажем существование такого n, что αn меньше ⅓, ¼, ⅕, 3/16.
  Если  α > ⅓,  то  α1 < ⅓.
  Если  ¼ < αk < ⅓,  то каждый шаг удваивает отклонение от ⅓: пусть  αk = ⅓ – ε  (где  ε < 1/12),  тогда  αk+1 = ⅓ + 2ε,  αk+2 = ⅓ – 4ε.  Если это число всё ещё больше ¼, повторим процедуру...
  Если  ⅕ < αk < ¼,  то уже  αk+2 < ⅕.
  Если  3/16 < αk < ⅕,  будем увеличивать отклонение от ⅕:  αk = ⅕ – ε  (ε < 1/80),  αk+2 = ⅕ + 4ε,  αk+4 = ⅕ – 16ε.  Если это число всё ещё больше 3/16, повторим процедуру...

  б) Для построения примера нам потребуются представление чисел в виде бесконечных двоичных дробей. Как обычно, иррациональные числа представляются бесконечными непериодическими дробями.
  Рассмотрим дробь  δ = 0,0000001000000010...,  где единички стоят в 7-м, 15-м, 23-м, ... разрядах. Она равна сумме бесконечной геометрической прогрессии  2−7 + 2−15 + 2−23 + ... = 2/255.  Если непериодически заменить часть единичек на нули и умножить результат на 3, получим иррациональное число, меньшее  6/255 = 2/85.  Назовём такое число удобным.
  Пусть  α = ⅕ – β,  где β удобно. Тогда  α > ⅕ – 2/85 > 7/40.  При получении β мы могли заменить в 7-м разряде дроби δ единичку на 0 или оставить. Рассмотрим оба случая.
  1) Если заменили, то  α = ⅕ – 2–8γ,  где γ удобно. Тогда  α1 = ⅖ – 2–7γ,  α2 = ⅕ + 2–6γ,  α3 = ⅖ + 2–5γ,  α4 = ⅕ – 2–4γ,  ...,  α8 = ⅕ – γ.
  2) Если оставили, то  α = ⅕ – 3·2–7 – 2–8γ = 113/640 – 2–8γ,  где γ удобно. Тогда  α1 = 113/320 – 2–7γ,  α2 = 47/160 + 2–6γ,  α3 = 33/80 – 2–5γ,
α4 = 7/40 + 2–4γ,  α5 = 7/20 + 2–3γ,  α6 = 3/10 – 2–2γ,  α7 = ⅖ + 2–1γ,  α8 = ⅕ – γ.
  В обоих случаях  α1, α2, ..., α7 > 7/40,  а α8 – число того же вида, что и γ. Значит, и дальше всё будет хорошо.


Решение 2

  Воспользуемся сокращённой записью двоичной дроби: вместо выписывания всех её знаков будем указывать сколько одинаковых знаков стоит подряд: сначала сколько-то нулей (все наши дроби меньше ½), потом сколько единиц и т.д. Так дроби  ⅕ = 0,00110011... = 0,(0011)  соответствует сокращённая запись 222222..., дроби  3/17 = 0,(00101101) – 211211...,  а дроби  7/40 = ⅛·(1 + ⅖) = 0,0010(1100) – 21122222...
  Числа в сокращённой записи нетрудно сравнивать: находим первое место, где записи отличаются; если это место чётное, то больше то число, у которого на этом месте стоит бóльшая "цифра", а если нечётное, то наоборот. (Например, при сравнении  ⅕ > 3/17  в сокращённой записи ⅕ на втором месте стоит бóльшая цифра, а при сравнении  3/17 > 7/40  в сокращённой записи 3/17 на пятом месте стоит меньшая цифра.)
  Указанная в условии задачи операция действует на сокращённую запись следующим образом: если первая "цифра" больше 1, то она уменьшается на единицу; единица же в начале просто стирается. Многократное же применение операции – это стирание нескольких первых цифр и (возможно) последующее уменьшение первой цифры. Полученную запись будем называть хвостом исходной.

  а) Дроби 3/16 соответствует сокращенная запись 22. Если в сокращённой записи числа α есть тройка, то когда-нибудь она встанет на первое место и поэтому соответствующее число αn будет меньше 3/16.
  Если же сокращённая запись числа α состоит только из единиц и двоек, то в силу бесконечности и непериодичности (обычной) двоичной записи числа в сокращённой записи есть место, где после двойки стоит единица. Когда фрагмент 21 встанет в начало записи, соответствующее число αn станет меньше 3/16.

  б) Для построения примера достаточно рассматривать только числа, в двоичной записи которых нет трёх знаков подряд (то есть их сокращённые записи состоят из единиц и двоек). Нам надо подобрать сокращённую запись, все хвосты которой больше 21122222... Такой, например, будет любая запись вида 112...2112...211..., где единицы стоят только попарно и между каждыми двумя соседними парами единиц находится нечётное число двоек.
  Действительно, если в начале сокращённой записи хвоста стоит 1 или 22, то все ясно.
  В противном случае она имеет вид 2112...211..., где третья единица стоит на нечётном месте. Поэтому это число больше чем 7/40, у которого на этом месте стоит двойка.

  Осталось проследить, чтобы дробь была непериодической.

Ответ

б) Может.

Замечания

1. Идеология. Указанное в условии отображение помимо неподвижной точки ⅓ имеет много периодических точек. Точки небольшого периода найти нетрудно. Например, у ⅕ период 2  (⅕ → ⅖ → ⅕),  а у 3/17 – период 3  (3/176/175/173/17).  Оба эти числа немного больше 7/40, а порождённые ими числа ещё больше. Но к сожалению, эти числа рациональны. Зато они представляются периодическими двоичными дробями:  ⅕ = 0,(0011),  3/17 = 0,(00101101).  Попробуем сконструировать искомое иррациональное число, смешивая фрагменты вышеуказанных дробей 00110011 и 00101101. Можно ожидать, что и оно породит последовательность, где все члены не меньше 7/40. Решение 1 – формальная проверка этой идеи:  ⅕ – 3/17 = 2/85,  при вычитании β из ⅕ замена в δ единицы на ноль не меняет соответствующего фрагмента 00110011 в разложении ⅕, а оставление единицы вычитает из него 00000110, то есть превращает в 00101101.

2. Баллы: 4 + 4.

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

олимпиада
Название Турнир городов
Турнир
Номер 28
Дата 2006/2007
вариант
Вариант весенний тур, основной вариант, 10-11 класс
задача
Номер 6

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

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