Сумма цифр 5 ▶ №223 (Блок - интересные задачи)

Разбор интересной задачи.

[grigoryborisov]

41000. Решал через таблицу, где элементами являются a(s, n)–количество n-значных чисел, сумма цифр которых равна s. Для суммы цифр 5 количество n_значных чисел 1, 5, 15, 35, 70 и т.д. 126-е число== 50000, значит 125-е = 41000.

[romank.]

Вроде 41000 получается. Берем 5 разрядов. Пятёрку можно поставить на любое из пяти мест, остальные нули. Получаем 5 чисел. Наборы (1, 4) и (2, 3) с тремя нулями дают по 20 чисел каждый, всего 40. Наборы (1, 1, 3) и (1, 2, 2) дают по 5*4*3/2=30 чисел, всего 60. Набор (1, 1, 1, 2) даёт 5*4=20 чисел. И одно число Всего получаем 5+40+60+20+1=126 чисел из максимум пяти цифр, удовлетворяющих условию. Надо взять второе по величине. Максимальное - это 50000, следующее - 41000.

Ну-с, заценим решение профессионала.

[Snuryus]

Если бы не знал заранее метода с использованием воображаемых коробок - то понять рассуждение было бы сложно. :)
И можно было сразу записать, что x1+x2+x3+x4+x5 = 5 имеет ровно (5+4)!/(5! * 4!) = 126 решений в неотрицательных числах.

[pojuellavid]

рассмотрел все пятизначные "числа" от 00005 до 50000, поскольку от шестизначных чисел (и "чисел") и выше -- идет повтор с прибавлением нулей.
получил 5 = 1, 4-1 = 20, 3-2 = 20, 3-1-1 = 30, 2-2-1 = 30, 2-1-1-1 = 20, 1-1-1-1-1 = 1. Итого 126
самое большое 50000, а за ним -- 4100
Ответ: 41000

[dmitrygurban]

Нужно будет еще раз пересмотреть, не понял просто решения.
П.С. Будет ли разбор той задачи, что я отправлял (про группировку чисел в 2 группы с одинаковым произведением)? Просто, как мне кажется, тоже очень симпатичная задача.

[leretekapi]

В этой задаче "перегородки" были лишние (крутой приём, но не для этой задачи). Просто 4 шарика по n местам уже и есть (n+4)!/(4!*n!) как число сочетаний. Перегородки только запутают: около 4 минут из 13 заняли эти ненужные пояснения (с 4:00 по 8:00 примерно).
Но суть, конечно же не меняется.