Я придумала такое решение, ошибки пока не вижу:
Ясно, что ряд чисел
будет таким:
Значит, нам нужно просто уметь делить весь ряд по какому-то признаку на непересекающиеся 4-ки.
Ясно, что можно сделать
,
, но надо ещё как-то уметь однозначно переводить
в
и наоборот
Сделаем так:
Нам дали
(как уже договорились,
), чтобы перевести его в
(
)
Рассмотрим
дерево Калкина-Уилфа, ясно, что если задавать число путём в этом дереве (0 — налево, 1 — направо), то всякое число <1 будет каким-то «…101001111001…0», тогда распределим пути по кол-ву 1ц перед последним нулём:0 — вставляем 1 (перед последним нулём)1 — убираем2 — вставляем3 — убираем …и т. д.Тогда путь 0 станет 10, 00 — 010, 000 — 0010, …0110 — …01110, …01110 — …0110Вроде всё на месте Обратимость обеспечили, скажем, что
, когда мы дадим
-у единичку и
, если наоборот, a
= число (не путь!), которое получится при помощи этих преобразований (ясно, что если до этого момента всё верно, то решение существует. Если я даже и ошиблась где-то, a решения не существует, то док-во его несуществования скорее всего будет как-то связано co счетностью и рациональностью, такая вот догадка наперёд)
Теперь рассмотрим тактику
:
1. Если
, то
2. Если
:
если
, то
если
, то
3. Если
:
если
, то
если
, то
Вот пример:
1. найдём
, путь по дереву будет 010, т.e.
, получили 3
2. найдём
, путь по дереву у
будет 00, т.e.
, получили
3. найдём
, путь по дереву у
будет 010, т.e.
, получили
4. найдём
, путь по дереву будет 00, т.e.
, получили
Сработало