Найти количество чисел, сумма цифр которых делится на 11...

[Unconnected]

У меня есть несколько заданий, над которыми уже долго бьюсь, но левела видать не хватает, тяготят долгими зимними вечерами..

Одна: найти количество 4хзначных чисел, сумма цифр которых делится на 11.
И как я её не пробовал.. максимум, что придумал - это если зафиксировать одну цифру, то сумма остальных 3х будет равна чему-то конкретному, на эту сумму есть ограничения, её можно тоже разбить на какие-то суммы с ограничениями.. и потом всё это перебрать\скомбинировать. Нужный ответ (818, кажется, программой проверял) так и не получился. Знаю, что можно как-то вычетами..

[Joker_vD]

Unconnected в сообщении #505507 писал(а):

найти количество 4хзначных чисел, сумма которых делится на 11.

Сумма цифр, наверное? Максимально возможная сумма цифр у 4-значного числа равна 36. Значит, вашу задачу можно разбить на три подзадачи: все четырехзначные числа, сумма цифр которых равна 11, 22 или 33. Далее, пожалуй, действительно можно фиксировать по очереди цифры и считать. Нудно, но надежно. Возможно, есть способ поостроумнее.

[ИСН]

Да что там фиксировать. В лоб перебрать - и только.
Вот если бы цифр было хотя бы этак 12, то там - - -

[Unconnected]

Да, сумма цифр.
Кажется, это более чем нудно, очень много перебирать (у меня так выходило, по крайней мере).

[ИСН]

foreach(1000..9999){$n++ if(eval join"+",split//)%11==0} print $n

Да, действительно нудно (думал, уложусь символов в 50, да где там!..)

[Unconnected]

Ну так я тоже умею)

[Sonic86]

Рекуррентная формула:
$N(x_1+\dots+x_k=n) = \sum\limits_{x_k=0}^9 N(x_1+\dots+x_{k-1}=n-x_k)$.
Используя ее, выведите формулу в общем виде для $k=4$ (ну или так подсчитайте), используя формулу для $k=1$: $N(x_1=n)=[n \leqslant 9]$.

[Unconnected]

А что значит N в этой формуле?

[Whitaker]

количество $k$-значных чисел с суммой цифр $n$

[Shadow]

Можно поделить сумму на 2 пары. Первые 2 и последние 2. Распределение суммы для 2 цифр елементарно

00,01,02,03,04,05,06,07,08,09,10,11,12,13,14,15,16,17,18
01,02,03,04,05,06,07,08,09,10,09,08,07,06,05,04,03,02,01

И там как получить 11,22,33. Неприятно, но решимо.

[Sonic86]

Unconnected в сообщении #505667 писал(а):

А что значит N в этой формуле?

$N(F(x_1,\dots ,x_k)=0)$ - число решений уравнения $F(x_1,\dots ,x_k)=0$. Очень удобная штука.

[Joker_vD]

(Оффтоп)

Вообще говоря, смахивает на задачу динамического программирования...

[ИСН]

(Оффтоп)

да, похоже. но

ИСН в сообщении #505509 писал(а):

Вот если бы цифр было хотя бы этак 12, то там - - -

[Unconnected]

Цитата:

Используя ее, выведите формулу в общем виде

А можно указание, с чего это начинать? Как бы смысл понял, но неужели для этого большого перебора есть просто эквивалентная формула?

[Sonic86]

Unconnected в сообщении #508169 писал(а):

А можно указание, с чего это начинать?

Ну вот так и начинайте:
$k=2$:
$N(x_1+x_2=n)= \sum\limits_{x_2=0}^9 N(x_1=n-x_2)= \sum\limits_{x_2=0}^9 [0 \leqslant n-x_2 \leqslant 9] = $
$[0 \leqslant n \leqslant 9]\sum\limits_{x_2=0}^9 [x_2 \leqslant n][x_2 \geqslant n-9]+[10 \leqslant n \leqslant 18]\sum\limits_{x_2=0}^9 [x_2 \leqslant n][x_2 \geqslant n-9]=$
$[0 \leqslant n \leqslant 9]\sum\limits_{x_2=0}^9 [x_2 \leqslant n]+[10 \leqslant n \leqslant 18]\sum\limits_{x_2=0}^9 [x_2 \geqslant n-9]=$
$[0 \leqslant n \leqslant 9]\sum\limits_{x_2=0}^n 1 +[10 \leqslant n \leqslant 18]\sum\limits_{x_2=n-9}^9 1 = $
$[0 \leqslant n \leqslant 9](n+1) +[10 \leqslant n \leqslant 18](9-(n-9)+1)$

(в формуле выше исправил индекс суммирования)

Unconnected в сообщении #508169 писал(а):

Как бы смысл понял, но неужели для этого большого перебора есть просто эквивалентная формула?

Ну да, просто ее выводить трудно.
Я, кстати, не утверждаю, что у меня самое простое решение, наверняка нет. Просто так можно решать. У меня не красиво получается