Задачи вступительного экзамена в ШАД 2014
Расстояние an от действительного числа a є R до ближайшего рационального числа вида m/2n, где m, n є Z можно легко свести к функции вида «расстояние до ближайшего целого» S (x), x є R:
Очевидно, что значения этой функции лежат в пределах от 0 до ½, кроме того она является периодической. Для тех кто не успел прикинуть это в уме, вот ссылка на wolfram alpha.
Вследствие периодичности функции, для поиска максимума нам достаточно рассматривать ее на одном периоде, а именно на интервале [0,1], вместо того чтобы делать это на всей числовой оси. Неплохая оптимизация для начала)
Итак, запишем выражение для an, приведем слагаемые внутри модуля к общему знаменателю и вынесем 1/2n, значение an при этом не изменится:
Таким образом, исходя из определения функции S (x), получаем новое выражение для an:
«Можно заметить», что искомый ряд представляет собой, как «очевидно» каждому читающему этот пост, функцию Бланманже (Такаги), похожую на одноименный десерт:
Функция (кривая) Бланманже, наряду с общеизвестной функцией Вейерштрасса, является непрерывной, но нигде не дифференцируемой функцией. Конечно, если решающий задачу знаком с ней, то он сразу может гордо писАть, что это функция Бланманже и для неё, согласно теореме Кахане (3.1), максимальное значение составляет 2/3. И это готовый ответ! Беда в том, что на экзамене хоть и разрешается пользоваться печатными справочниками, информации по упомянутой функции там может попросту не оказаться. Поэтому продолжим поиски «адекватного» решения.
Итак, нам необходимо найти максимально возможную сумму ряда:
Для наглядности, приведем здесь график функции S (x):
Распишем ряд для T (x):
Выделим в нем n-частичные суммы (фигурные скобки на рисунке выше), каждая из которых соответствует количеству итераций при построении кривой Такаги и задается выражением:
Распишем все частичные суммы и обратим внимание на суммы с четными номерами:
Обозначим T2(x) как S1(x) (это т.н. функция-«столешница») и заметим что для четных частичных сумм справедливо выражение:
и
Ну, а дальше нам на помощь приходит математическая индукция. Кахане в своем доказательстве провел аналогичные рассуждения, рассматривая четные частичные суммы, построил первые две из них T2(x) и T4(x) и по индукции пришел к выводу, что максимальное значение для T2n (x) равно:
Тогда максимальная сумма ряда M вычисляется как сумма ряда бесконечно убывающей геометрической прогрессии:
Ну и, собственно, сами графики для первых 6-ти итераций:
Даже если остановиться на четвертой итерации, построение этих графиков будет делом медленным. Здесь можно построить и для других итераций, кому интересно. Однако, хотелось бы найти способ побыстрее.
Как вариант, можно применить индукцию пораньше, обратив внимание на функцию-«столешницу» S1(x). Рассмотрим опять же частичные суммы T2(x) и T4(x), и построим графики для S1(x) и S1(4x):
Очевидно, что с каждым последующим увеличением «частоты» (S1(4x), S1(16x), S1(64x) …) 2 новых «столешницы» будут появляться внутри каждой, построенной на предыдущей итерации (с частотой в 4 раза меньше), а следовательно всегда найдется такой аргумент x, в котором значения S1(4x), S1(16x), S1(64x) … совпадут и будут равны ½. Т.е. мы доказали, что если разбить ряд на суммы 1-е и 2-е слагаемое S1(x), 3-е и 4-е слагаемое (¼)S1(4x), 5-е и 6-е (1/16)S1(16x) и т.д., то эти суммы не превосходят:
Ну и максимальная сумма ряда M:
Этот способ незначительно отличается от предыдущего, но объем построений в нем явно поменьше.
Можно решить задачу еще быстрее, применив индукцию еще раньше. Итак, вновь распишем сумму ряда:
Рассмотрим функции S (x), S (2x), S (4x) … и построим графики для них:
Видим, что все эти функции с дальнейшим увеличением частоты в 2 раза, всегда будут пересекаться в одной точке с аргуметом x=⅓ (значения функций при этом совпадут и будут равны ⅓), следовательно искомая сумма ряда будет принимать максимальное значение именно в этой точке:
Задача, бесспорно, красивая, но лучше не увлекаться ее красотой на экзамене, а решить побыстрее.
