Насколько точен ваш компьютер?

Мы привыкли доверять в расчётах компьютеру. Но иногда - чересчур полагаемся на него. А сейчас я покажу один поучительный пример, позволяющий оценить точность вычислений.

Откроем новый документ Excel. В ячейку А1 введём число 0

Переставляем цифры и складываем

Возьмём некоторое натуральное число. Переставим как-нибудь его цифры и прибавим новое число к исходному. Какой минимальный результат может получиться, если сделать несколько таких шагов?

Например, если начать с единицы, то наименьшим числом, которое можно получить за 10 шагов, будет число 466.

Всё вполне интуитивно: переставляем цифры в восходящем порядке, чтобы каждое сложение  как можно меньше увеличивало результат. Однако если найти наименьшее число, которое можно получить за 11 шагов, им окажется не 932 = 466 + 466, а 896, находящееся в совершенно иной ветке:

Как видите, во второй ветви четырежды цифры сортировались не в строго возрастающем порядке, что позволило получить два числа с нулями. Эти нули, будучи выведенными вперёд в слагаемых, помогли сократить конечный результат.

А теперь вопрос. Какое наибольшее число шагов можно успеть сделать, пока число не станет пятизначным?

Загадка числа 196

Возьмём любое натуральное число, например, 12. Переставим в нём цифры в обратном порядке и сложим с исходным.
12 + 21 = 33.

Мы получили число-палиндром, одинаково читающееся как справа налево, так и слева направо.

Иногда, чтобы получить палиндром, требуется больше шагов. Вот, например, для числа 192:
192 + 291 = 483
483 + 384 = 867
867 +768 = 1545
1545 + 5451 = 6996

Сделано 4 шага и палиндром, 6996, получен.

И так происходит почти с любым числом, с какого бы ни начать процесс. А вот с числом 196 что-то странное. Сколько ни продолжали переставлять цифры и складывать - палиндрома не выходило!

196 + 691 = 887
887 + 788 = 1675
1675 + 5761 = 7436
7436 + 6347 = 13783
13783 + 38731 = 52514
52514 + 41525 = 94039
94039 + 93049 = 187088
187088 + 880781 = 1067869
Само число уже превышает миллион, а палиндром не получен!

И до сих пор не найдено ни на каком шагу из числа 196 получится палиндром (а таких шагов разными исследователями с помощью компьютера сделано более семисот миллионов), ни строгого доказательства, что палиндром не будет получен никогда.

Ещё способ

Ещё один простой способ генерации кода Грея связан со следующим процессом:

Начинаем с буквы А. Далее поступаем по следующем правилу: приписываем справа следующую букву, а после неё - повторяем все ранее записанные символы. После первого шага получим строку
АВА
После второго: АВАСАВА
После третьего:
АВАСАВАDАВАСАВА

Теперь возьмём двоичное число 0000 и обозначим его цифры как DCBA. Пробежимся по строке и будем менять на противоположную ту цифру, которая соответствует текущему символу в строке:
А: 0001
В: 0011
А: 0010
С: 0110
А: 0111
В: 0101
А: 0100
D: 1100
А: 1101
В: 1111
А: 1110
С: 1010
А: 1011
В: 1001
А: 1000

Как отметил наш читатель Вадим, есть ещё один рекурсивный способ: сначала получаем код Грея длины 3, записываем его сначала в прямом порядке, а потом в обратном. И дописываем перед первой половиной 0, а перед второй — 1.

495

Как мы уже писали, число 6174 является неподвижной точкой преобразования Капрекара для четырёхзначных чисел.

Для трёхзначных же таковым является число 495. Берём любое 3-значное число и из его цифр составляем 2 числа: с цифрами, идущими по возрастанию и идущими по убыванию. Затем вычитаем из первого второе.

512:

521-125=396

963-369=594

954-459=495

А вот для преобразований 5-значных чисел неподвижных точек нет.

Перекладывание карт

Рассмотрим колоду из N карт с номерами от 1 до N. если номер верхней карты равен K, поменяем порядок K верхних карт на обратный. Будем поступать так, пока на верх не выйдет единица.

Для 5 карт дольше всего перекладываний (7) будет для колоды 3, 1, 4, 5, 2

31452
41352
53142
24135
42135
31245
21345
12345

6174

Число 6174 называется постоянной Капрекара и обладает интересным свойством.
Возьмём любое четырёхзначное число, не состоящее из одинаковых цифр. Сформируем из него два четырёхзначных числа, чтобы в первом цифры шли в убывающем порядке, а во втором - в возрастающем, и вычтем из первого числа второе.

Тогда не более, чем за 7 итераций мы придём к числу 6174. Например, если начать с числа 1001:

1100-0011=1089
9810-0189=9621
9621-1269=8352
8532-2358=6174
7641-1467=6174 и процесс зациклится