Делимость на 11

[m_victor]

Сколько существует пятизначных чисел, состоящих из цифр 2, 4, 5, 6 и 9, делящихся на 11?

[bot]

Олимпиада для пятиклассников?

[Deggial]

Тема перемещена из форума «Олимпиадные задачи (М)» в форум «Помогите решить / разобраться (М)»
m_victor, приведите попытки решения, укажите конкретные затруднения.

[bot]

Вот, теперь другое дело. Признак делимости на 11 знаете?

[m_victor]

Если разность суммы цифр на четных и нечетных позициях делится на 11, то число тоже делится на 11.

[provincialka]

А насколько большой может быть эта разность в данном случае? И какой четности?

[m_victor]

Самая большая разность - $27-4=23$, а четность вроде любая. Т.е. надо проверить случаи $a_1+a_3+a_5=a_2+a_4$, $a_1+a_3+a_5=a_2+a_4+11$ и $a_1+a_3+a_5=a_2+a_4+22$? Как-то многовато перебора.

[Sonic86]

Чего-то у меня тоже ничего умнее перебора не получается
Зато он у меня оптимизированный и его можно выполнить ручками:
Мы ищем число решений сравнения $a+c+e\equiv b+d\pmod{11}$ для $a,b,c,d,e\in M=\{2,4,5,6,9\}$. Вычислим число решений $v_k=N(b+d\equiv k\pmod{11}, b,d\in M)$. Тогда исходное число решений равно $\sum\limits_{e\in M}\sum\limits_{k\in\mathbb{Z}_{11}}v_kv_{k-e}$
З.Ы.: ИМХО, четность не причем.
Еще я заметил, что $6\equiv -5\pmod{11}, 9\equiv -2\pmod{11}$, но можно ли это использовать? Только если для того, чтобы в предлагаемой сумме считать только для $e=2;4;5$...

[VAL]

m_victor в сообщении #791693 писал(а):

Самая большая разность - $27-4=23$

Откуда взялось 27?

Цитата:

а четность вроде любая. Т.е. надо проверить случаи $a_1+a_3+a_5=a_2+a_4$, $a_1+a_3+a_5=a_2+a_4+11$ и $a_1+a_3+a_5=a_2+a_4+22$? Как-то многовато перебора.

Перебор совсем короткий. Суммы цифр, стоящих на четных и нечетных местах, должны либо отличаться на 22, либо быть равны.
Для первого случая не получается, а для второго мгновенно получаем всего один вариант разбиения цифр. Все решения получаются перестановкой цифр найденного варианта.
(И никаких сравнений с пятью переменными )

[Sonic86]

VAL в сообщении #791701 писал(а):

Суммы цифр, стоящих на четных и нечетных местах, должны либо отличаться на 22, либо быть равны.

Почему? Например, $2+4+11=9+4+4$.
Кстати, у меня вышло $282$. Проверю сейчас заодно... Если программа правильная, то $270$...
А, понял, я у себя коэффициенты перепутал, теперь и у меня $270$ тоже...

VAL в сообщении #791701 писал(а):

И никаких сравнений с пятью переменными

Мое рассуждение можно и без сравнений переписать. Вру - у меня классы вычетов нужны. А вот как без перебора - неясно.

[VAL]

Sonic86 в сообщении #791705 писал(а):

VAL в сообщении #791701 писал(а):

Суммы цифр, стоящих на четных и нечетных местах, должны либо отличаться на 22, либо быть равны.

Почему? Например, $2+4+11=9+4+4$.
Кстати, у меня вышло $282$. Проверю сейчас заодно... Если программа правильная, то $270$...
А, понял, я у себя коэффициенты перепутал, теперь и у меня $270$ тоже...

А-а! Так мы разные задачи решаем!
Я все все цифры по разу задействовал. Внимательно перечитав условие, пришел к выводу, что это ограничение, скорее всего, придумал я сам

Зато насколько проще стала задача!

[provincialka]

Откуда 11 и 22? Сумма трех наибольших цифр $9+6+5=20$, двух меньших - $2+4=6$, так что наибольшая разность $20-6=14$. Остаются возможности 0 и 11. Но сумма всех чисел четная, следовательно, и разность двух групп будет четная, 11 не подходит.

[svv]

Я понял условие, как VAL, хотя на двусмысленность обратил внимание. Не случайно число пятизначное, и цифр пять.

[m_victor]

provincialka в сообщении #791715 писал(а):

Откуда 11 и 22? Сумма трех наибольших цифр $9+6+5=20$, двух меньших - $2+4=6$, так что наибольшая разность $20-6=14$. Остаются возможности 0 и 11. Но сумма всех чисел четная, следовательно, и разность двух групп будет четная, 11 не подходит.

Дело в том, что цифры могут повторяться.

Хотя интересно, что получится, если они не повторяются.

[provincialka]

В условии не сказано точно, повторяются или нет. Поэтому я исходила из критерия "красоты". Решение задачи для неповторяющихся цифр содержит некоторые идеи. Решение для повторяющихся - просто повторение того же несколько раз, что скучно. Тем более задача декларировалась как олимпиадная.