Бесконечная цепочка удвоений в перестановке чисел

[gipokrat]

Никита переставил натуральные числа, и они теперь стоят не по порядку. Можно ли зачеркнуть часть из них так, чтобы оставалось бесконечно много чисел и каждое следующее из них было вдвое больше предыдущего?

Источник задачи: https://mmmf.msu.ru/archive/20072008/z8b/15.html (задача №7).

Мне кажется, что в общем случае этого сделать нельзя.
Скажем, Никита переставляет числа следующим образом:
Сначала выписывает в порядке возрастания все двузначные числа, затем — все однозначные, затем — все 4-значные, затем — все 3-значные и так далее. То есть на каждом $2n-1$-ом шаге он выписывает все $2n$-значные числа, а на каждом $2n$-ом шаге — все $2n-1$-значные числа.

Такой порядок действительно убивает бесконечную цепочку удвоений, если я ничего не путаю. Причём порядок внутри каждого блока не важен — ключевым является именно взаимное расположение блоков «чётный раньше нечётного».

Верна ли моя идея? На правильном ли я пути к решению? Пожалуйста, помогите разобраться.

[dgwuqtj]

Ваша идея рабочая, остаётся додумать технические детали.

[wrest]

gipokrat в сообщении #1698488 писал(а):

Верна ли моя идея?

Да, в принципе можно не привязываться к конкретной системе счисления а перемешать блоки по границам степеней двойки (хотя это по сути та же идея в двоичной системе счисления, из неё видно обобщение: если требуется перемешать числа так чтобы не было бесконечной последовательности $an^k, k=1,2, \dots$ где в исходной задаче $n=2$ то границами блоков выбираем степени $n$, т.е. блоки $[n^k,n^{k+1}-1]$ и чередуем четные-нечетные).