Задача про пятизначное число

Постановка задачи

На неделе мне рассказали любопытную задачу. Отдалённо она напоминает задачки из ЕГЭ по информатике, но несколько сложнее.


Правильный ответ (его никто и не скрывает, так как суть - в решении):

Негодование и демагогия

Нет, ну Вы видели:


Какая система счисления? Подозреваю, что позиционная - с каким основанием? Для задачки по математике - непозволительная небрежность в формулировках.

Какое, кстати, большое число получается: (4000/2)/9≈222 цифры. Неудивительно, что в ответ надо записать лишь его часть. Почему в ответ пойдут именно "голова" и "хвост"? - об этом ниже.

Решение

Рассмотрим число K, запись которого в десятичной позиционной системе счисления представляет собой последовательность цифр k₁, k₂, k₃, ..., k_m:


Как это и бывает в задачах - многое сокрыто в мелочах: мы ищем наименьшее натуральное число. Нетрудно заметить, что при постоянном S(k), уменьшить число - значит переставить его цифры так, чтобы наименьшие шли при больших весах. Говоря иначе:


Например, Вас устраивает S числа 312, но хочется, чтобы число было меньше. Отсортируем цифры - получим число 123 с тем же значением S.

Вторая, ещё более очевидная мысль: натуральное число тем меньше, чем короче его запись в позиционной систем счисления. Отсюда следует, что получить искомую величину S нужно из числа, с наименьшим количеством цифр. А последнее, в свою очередь, говорит о том, что большая (в общем случае - не меньшая, если, конечно, S⩾9) часть цифр в этом числе - девятки.

Дополнительная мысль: сумма положительных чисел тем больше, чем больше каждое слагаемое. Таким образом, в нашей задаче надо стремится максимизировать и S(n), и S(n+61).

Рассмотрим число (n+61), а конкретно: как образуется его "хвост"


Помня о сказанном выше, рассмотрим: какие наилучшие значения могут быть у n_m-2, n_m-1, n_m.

Для разряда n_m, очевидно, лучшим значением будет 8:

В этом случае, и n_m, и n'_m имеют максимальные значения, не противоречащие тождеству. (n'_m=9.)

Перейдём к следующему разряду (рассмотрим возможные варианты):

nm-1	n'm-1	S
0	6	6
1	7	8
2	8	10
3	9	12
4	0	4
5	1	6
6	2	8
7	3	10
8	4	12
9	5	14

Наибольшему значению S соответствует n_m-1=9; при этом n'_m-1=5. Обратите внимание: так как 9+5=14>9, выражение для разряда n_m-2 принимает следующий вид:


Ещё одно слагаемое - результат переноса из младшего разряда. Аналогично ситуации с разрядом n_m, лучшим значением для n_m-2 будет 8. (n'_m-2=9.)

Исходя из произведённого анализа, исследуемые числа будут иметь вид:

• За исключением последних трёх цифр, числа n и (n+61) совпадают.
  
• Не считая последних трёх цифр, в числах присутствует не менее p девяток в каждом (они, будучи максимально сдвинуты вправо, образуют основную "массу" S, при сохранении минимальности n).
  
• Для обеспечения равенства S(n)+S(n+61)=const, в числах присутствует блок x, составленный из цифр, меньше 9. Для минимизации n, блок идёт в самом начале числа (до девяток). Так как остаток, не представимый в виде суммы девяток, не может превосходить или равняться девяти (иначе его можно записать как 9+y, что противоречит его определению), его запись занимает одну цифру.
  

Находим p как floor(1976/9)=219 (ищем количество девяток, сумма которых приближается к 1976). Тогда:


Итоговый вид чисел:


Ответ: "59"+"959"=59959.