Алгоритм Бома

Вот какую задачку по информатике (начальная школа) мне вчера дали посмотреть:



Вторая часть задания не взывает вопросов: формально прогнать числа через алгоритм, выписывая промежуточные значения.
Что по-настоящему заняло меня: почему фокус удаётся? Нетрудно заметить, что на выходе алгоритма всегда будет "9", но почему?

Рассмотрим число A, поступающее на вход алгоритма. Так как далее я буду оперировать как самой величиной, так и её представлением, то сразу оговорюсь: все числа в решении записываются в десятичной позиционной системе счисления.

Число A может быть представлено тройкой цифр a₁, a₂, a₃ - запишем этот факт следующим образом: A={a₁ a₂ a₃}. Например: 123={1 2 3}.

Итак, дано некоторое число A={a₁ a₂ a₃}, причём a₁≠a₃.

Записываем число наоборот. Пусть это будет A'={a₃ a₂ a₁}.

Пусть a₁>a₃. Эта конкретика не повлияет на решение, так как в алгоритме указано, что в противном случае - порядок операндов меняется. Данное условие нужно только для того, чтобы не получить в результате отрицательное число, однако самому алгоритму важен только модуль числа.

При a₁>a₃, необходимо найти разность: A-A'.

Вот тут необходимо вспомнить принцип кодирования чисел в позиционных системах счисления. Этот принцип зазубривается в младших классах и забывается к старшим (так как используется формально, на автомате).


Фух! Так как a₁>a₃, и a₁, a₃ числа (то есть: не меньше 0 и не больше 9) то:


Обозначим, для удобства, получившийся результат новой буквой: B = 99*(a₁ - a₃) = {b₁ b₂ b₃}.

Что делать дальше - непонятно. Я обнаружил, что у окружающих уже пропал интерес к задаче, а у меня - только подогрелся.

Судя по известному нам результату работы алгоритма, необходимо доказать, что b₂ = 9, для всех возможных значений a₁ и a₃.

Учитывая конечность множества допустимых значений, задачу можно было бы свести к брутфорсу (полному перебору), но это "не спортивно". К этому моменту я уже понял, что правильный ответ, на поставленный в задаче вопрос: "алгоритм всегда даёт 9 в результате". Я отхлебнул чая из кружки и продолжил решение.

Предположим, что мы производим операцию умножения над числами U и V, получая C. Слегка конкретизируем под данную ситуацию, чтобы совсем не закопаться:


Чему равно c₂? Если представить себе умножение в столбик, выполняемое над нашими коэффициентами, то:


где floor - округление в меньшую сторону (взятие целой части), а mod 10 - остаток от деления на 10. Обе операции нелинейны, а значит дальше упростить выражение не получится. Всё стало ещё "лучше", чем было.

Подумав ещё, и вспомнив семантику операций, я понял, что удобнее переписать выражение для c₂ следующим образом:


Выглядит страшно, но легко понять на примере: допустим Вы умножаете 65 на 8 - в ответе получится 520. Цифра 2 получилась из результата умножения 6*8 (u₁*v₁) к которому вы прибавили 4 (q₁, перенос, от умножения 5*8 (u₂*v₁)), притом Вы оставили только последнюю цифру (w₂).

Запомним пока этот результат и отвлечёмся на одно свойство, позволяющее легко запомнить таблицу умножения на 9.



По мере увеличения множителя при 9, цифра в разряде десятков в ответе увеличивается, а цифра в разряде единиц - убывает. Иными словами:


Возвращаемся к B = 99*(a₁ - a₃):


Используем рассмотренное свойство:


тогда


Так как a₁, a₃ - цифры , то 10*(a₁ - a₃) является числом кратным десяти. При вычитании из такого числа единицы, последний разряд становится равным 9:


Последнее усилие:


что и требовалось доказать.

Ужас. Пожалуй, лучше ограничиться ответом: "результат работы алгоритма всегда равен девяти".

Простое решение

Стоило только поделиться своими сомнениями, как мне подсказали более простое решение.

Суть в том, чтобы даже и не начинать расписывать выражение (A-A'), а сразу вывести формулу для b₂ - это, к тому же, проще, чем заниматься аналогичным для умножения. Итак:


Так как по условию вычитать надо из большего меньшее, мы приняли a₁>a₃, а отсюда логично вытекает, что: a₃<a₁. Из этого факта можно сделать вывод, что при вычислении разности a₃ и a₁ (в процессе подсчёта младшего разряда результата A-A'), мы займём десяток из второго разряда. Как раз формулу для второго разряда мы и ищем (запишем только её):


Занятый десяток выливается в вычитание единицы из разряда десятков в числе A. Теперь, очевидно, наступает ситуация, когда из меньшего ( a₂ - 1 ) вычитают большее ( a₂ ). Займём десяток в следующем разряде (по-прежнему, рассматриваем формулу для b₂):


Если раскрыть скобки, то:


Всё.