Замена основания

[lena7]

Задача. Определим операцию "замены онования" с $k$ на $m$. Чтобы применить эту операцию к натуральному числу $n$, надо записать $n$ в $k$-ичной системе счисления, а затем прочесть эту запись в $m$-ичной системе. Возьмем произвольное натуральное $n$ и будем выполнять над ним такие операции: замена основания с $2$ на $3$, вычитание единицы, замена основания с $3$ на $4$, вычитание единицы и т.д. Докажите, что рано или поздно мы получим нуль.

[_Ivana]

Тривиально - рано или поздно мы придем к основаниям, большим того числа, которое у нас получится после конечного количества смены оснований до этого момента (вот это утверждение надо просто доказать аккуратнее), в которых это число будет записываться одной цифрой, и заменяя основания на следующее мы просто будем уменьшать эту цифру (точнее, значение числа, выражаемого этой цифрой) на единицу.

[lena7]

_Ivana в сообщении #729514 писал(а):

вот это утверждение надо просто доказать аккуратнее

Ну это-то как раз самое главное. Если число в данной системе счисления представляется более одной цифрой, то после замены основания оно увеличится.

Эта задача взята из учебника теории множест Верещагина и Шеня, она имеет интересное решение с использованием ординалов.

[lena7]

Можно рассмотреть более зверскую последовательность, если увеличивать не только основание, а все вхождения $k$ в "наследственной" записи числа по основанию $k$ (hereditary base-$k$ notation), когда мы берём обычную запись по основанию $k$ и раскладываем по этому основанию степени, степени в степенях и т. д. Удивительно, но эта последовательность тоже заканчивается нулём (теорема Гудстейна), а доказать это можно аналогично вышеуказанной задачке, если для данной последовательности рассмотреть последовательность ординалов, где все основания заменены на $\omega$.

[svv]

Зверскую -- в том смысле, что она вначале так быстро растёт, что кажется невероятным, что она когда нибудь достигнет нуля... Но теорема есть теорема.

[_Ivana]

По стартовой задаче - может с ординалами она решается красивее, но я не знаю что это такое, поэтому попробую на уровне средней школы. Есть у нас некое число, есть его запись в позиционной системе счисления с основанием $k_1$, она содержит $n$ разрядов, каждый из которых меньше $k_1$. При операции смены основания на любое большее основание значение числа увеличивается, а его запись в позиционной системе счисления с новым основанием остается прежней, не меняются ни сами разряды, ни их количество. Вычитание $1$ из числа сохраняет его запись, только значение младшего разряда уменьшается на $1$, но получившаяся цифра гарантированно присутствует в системе счисления с новым основанием. Таким образом, в результате конечного количества замен оснований на любое большее и последующим вычитанием из числа $1$, мы получим $0$ в младшем разряде позиционной записи, а количество разрядов записи не изменится. На следующем шаге при вычитании из числа $1$ у нас уменьшится на $1$ количество разрядов его записи в позиционной системе счисления с текущим основанием, а значения некоторых разрядов увеличатся до величины, на $1$ меньшей основания системы счисления (максимальной цифры в нем). И как в начале, рассмотрим это новое число и его запись в позиционной системе счисления с неким основанием, и продолжим наши шаги. Таким образом, за конечное число шагов мы постепенно уменьшим количество разрядов записи числа до $1$, а впоследствии и значение самого числа до $0$.