Сумма цифр

[wpoms.]

Пусть` S(x)` — сумма цифр натурального числа x. Найти наименьшее натуральное `n`, такое, что `9*S(n) = 16*S(2n)`.

@темы: Олимпиадные задачи

Comments

[Груша Вильямс]

Ааа...как её делать-то...

[Груша Вильямс]

Удалось показать, что `n>144`.

`s(2n)` делится на 9, тогда по признаку делимости на 9 следует, что `2n` делится на 9, то есть `n` делится на 9, тогда опять же по этому признаку получаем, что `s(n)` делится на 9.
Система
`s(2n)-s(n)=9a`,
`9s(n)=16s(2n)`
из которой `s(n)=(144a)/7`, где `a in N`.
Наимеьшее значение `s(n)` при `a=7`, но `n>s(n)`. Следовательно `n>144`.

[Trotill]

Груша Вильямс, а найти наименьшее число, сумма которого 144 очень просто:
1) у него должно быть мало разрядов (значит, большинство цифр - девятки)
2) меньшие цифры должны идти в старших разрядах.
Это число 999..9 (144/9 раз)

[Груша Вильямс]

Trotill, спасибо, действительно очень просто
Я было хотел попробовать поискать, но у меня сразу мысль возникла, что неизвестно при наименьшем `n` `s(n)=144` или `s(n)=288` например...и в итоге не туда пошел.

Ответ: `n=10^16-1`.

[All_ex]

Как решать аналитически я не знаю... ...
Но мысли следующие...

Во-первых, не трудно показать, что от перестановки цифр числа `n` сумма `s(2n)` не зависит... следовательно, для минимальности числа цифры должны располагаться в порядке убывания (то есть нулей не будет)...

Во-вторых, так как `9*s(n)=16*s(2n)`, то `s(n) > s(2n)`...
Теперь умножаем цифры на два и смотрим на результат... Видим, что для цифр от 1 до 4 `s(2n) = 2*s(n)`, то есть сумма увеличивается...
А для цифр от 5 до 8 `s(2n)` уменьшается по сравнению с `s(n)`...
Для 9 суммы одинаковы...

Отсюда можно сделать предположение (более строго доказывать, что цифр 1-4 не стал...), что искомое число имеет вид `n = 5...56...67...78...89...9`... (тут вывод подобен предложению Trotill... разве, что из одних девяток число состоять не может, так как не будет удовлетворять исходному равенству...)

Из предложения Груша Вильямс (а именно из системы, где первое уравнение имеет другой знак в силу неравенства `s(n) > s(2n)`)
`{(s(n) - s(2n)=9*N),(9*s(n)=16*s(2n) ):}`
Получается, что `s(n) = 144*N` и `s(2n) = 81*N`...

Дальше, если число `n` содержит `a` пятёрок, `b` шестёрок, `c` семёрок, `d` восьмёрок и `e` девяток, то имеем, что
`{(s(n) = 5a + 6b + 7c + 8d + 9e = 144N),( s(2n) = a + 3b + 5c + 7d + 9e = 81N):}`...

Что дальше делать не знаю... но провёл численный эксперимент...
Маткад выдаёт число из 21 шестёрки и двух девяток...

[Adjirranirr]

Маткад выдаёт число из 21 шестёрки и двух девяток...

`56666666666666666666799 < 66666666666666666666699`, а для него условия тоже выполняются.

У меня наименьшее получилось `n = 55555555555555569999999`.

[All_ex]

Adjirranirr, Да, я уже сам нашёл в программке ошибку...
У меня наименьшее получилось `n = 55555555555555569999999`. - да, после исправления у меня так же...

[All_ex]

Число, конечно, дикое... но вот вопрос, а как (если не перебором) его получить?...

[Adjirranirr]

Находим (с помощью черной магии, конечно) любое число `n` такое, что `s(n) = 144` и `s(2n) = 81`. А потом замечаем, что если от одной цифры отнять единичку и прибавить её к другой цифре, то если не произойдет переполнения и первая из цифр останется большей 4, то полученное число так же будет удовлетворять условиям.

[Adjirranirr]

Кстати. Если как-нибудь строго доказать, что в искомом числе не встречаются цифры 0, 1, 2, 3, 4, то можно это число представить в виде `n = 5\cdot \frac {10^k - 1}{9} + p`, где `k` — длина числа `n`, а в числе `p` встречаются только цифры 0, 1, 2, 3, 4. Тогда `s(n) = 5k + s(p)`, а `s(2n) = k + s(2p) = k + 2s(p)`. Дальше простая система `{ (5k + s(p) = 144), (k + 2s(p) = 81) :}`, откуда `k = 23, s(p) = 29`. Дальше среди всех возможных `p` с `s(p) = 29` находим наименьшее (это, очевидно, `14444444`) и число готово.

[All_ex]

Adjirranirr, красиво...

[Груша Вильямс]

Мощно!

[All_ex]

Adjirranirr, Ваше последнее предложение можно развить... что-то я горазд сегодня на это... ...

по этому поводу даже анекдот вспоминается

Я науку двигаю... но вперёд - мозгов не хватает... назад - начальство не позволяет... так я её в бок двигаю...

То что для минимальности цифры стоят в порядке невозрастания уже говорилось... то есть нулей быть в искомом числе не может...
Представим искомое `k`-значное число в виде `n = (5-a_1)...(5-a_m)5...5(5+b_1)...(5+b_r)`, где `a_i, b_j in {1; 2; 3; 4}`...
Тогда `s(n) = -s(a) + 5*k + s(b) = 144*N` и `s(2n) = 10*m - 2*s(a) + (k - m) + 2*s(b) = 81*N`...
Общее решение системы имеет вид `s(b) - s(a) = 29*N - 5*m` и ` k = 23*N + m`... для минимальности выбираем наименьшее `k`, для чего `m = 0` и `N = 1`... Ну, а дальше уже сказано...