03:22 

Сумма цифр

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

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

Комментарии
2013-02-22 в 08:57 

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

2013-02-22 в 10:13 

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

читать дальше

2013-02-22 в 14:16 

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

2013-02-22 в 22:17 

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

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

2013-02-22 в 22:25 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
Как решать аналитически я не знаю... :upset: ...
Но мысли следующие...

Во-первых, не трудно показать, что от перестановки цифр числа `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 суммы одинаковы...

Отсюда можно сделать предположение читать дальше, что искомое число имеет вид `n = 5...56...67...78...89...9`... читать дальше

Из предложения Груша Вильямс читать дальше
`{(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 шестёрки и двух девяток...

2013-02-22 в 22:34 

Adjirranirr
Только дурак нуждается в порядке — гений господствует над хаосом.
Маткад выдаёт число из 21 шестёрки и двух девяток...
`56666666666666666666799 < 66666666666666666666699`, а для него условия тоже выполняются.

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

2013-02-22 в 22:39 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
Adjirranirr, Да, я уже сам нашёл в программке ошибку... :shuffle2:
У меня наименьшее получилось `n = 55555555555555569999999`. - да, после исправления у меня так же...

2013-02-22 в 22:52 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
Число, конечно, дикое... но вот вопрос, а как (если не перебором) его получить?...

2013-02-22 в 22:59 

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

2013-02-22 в 23:05 

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`) и число готово.

2013-02-22 в 23:09 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
Adjirranirr, красиво...

2013-02-22 в 23:44 

Мощно!
:wow2:

2013-02-22 в 23:56 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
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`... Ну, а дальше уже сказано...

     

Не решается алгебра/высшая математика?.. ПОМОЖЕМ!

главная