Требуется обновление браузера.

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


Просмотров: 1077
25 февраля 2017 года

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


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

На заметку
Обозначим через S(k) сумму цифр числа k. Пусть n - наименьшее натуральное число такое, что S(n)+S(n+61)=4000. В ответ запишите пятизначное число, первые две цифры которого совпадают с первыми двумя цифрами числа n+61, а последние три - с последними тремя цифрами числа n+61. Например, если n+61=1234567890, то в ответ нужно записать число 12890.

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

На заметку
59959


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


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

Цитата
... сумму цифр числа ...

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

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

Решение


Рассмотрим число K, запись которого в десятичной позиционной системе счисления представляет собой последовательность цифр k1, k2, k3, ..., km:

K = {k1, k2, k3, ..., km} = k1*10m-1+k2*10m-2+...+km*10m-m.

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


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

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

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

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


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

Для разряда nm, очевидно, лучшим значением будет 8:
8+1=9.

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

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

nm-1n'm-1S
066
178
2810
3912
404
516
628
7310
8412
9514

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

nm-2+1+0=n'm-2.

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

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

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

S(n)+S(n+61)=4000
2*x+2*p*9+8+9+8+9+5+9=4000
2*x+18*p+48=4000
x+9*p+24=2000
x+9*p=1976.

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

x+9*219=1976
x=1976-1971
x=5.

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


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


Запись опубликована в категориях:

ЕГЭ и прочие радости Цифры и числа  
 

Комментарии

Инкогнито
  Загружаем captcha