Еще одна школьная задачка

coteico

Требуется посчитать количество десятизначных чисел, состоящих из различных цифр таких, что их удвоение -так же состоит из 10 различных цифр.
Ну... без компьютера, в смысле, посчитать)

griz_a

Заметим, что из предыдущего разряда может переноситься или один или ноль. Поэтому у удвоенного числа каждая цифра или удвоенная цифра обычного, либо удвоенная цифра + 1.
Назовем цифру "накрытой", если в ее разряд единица переносится. Справа от каждой накрытой стоит одна из цифр 5, 6, 7, 8, 9.
Рассмотрим 5 пар 0, 5; 1, 6; 2, 7; 3, 8; 4, 9. В каждой паре оба при удвоении дают одинаковую последнюю цифру, поэтому в нашем исходном числе для каждой такой пары одна цифра должна быть накрыта, а вторая нет. Назовем такие числа правильно накрывающимися.
Любое подходящее число должно быть правильно накрывающимся с первой цифрой не более 4.
С другой стороны любое такое число будет подходящим, поскольку совпадение цифр может возникнуть только при удвоении двух цифр из одной пары.
Значит надо подсчитать число правильно накрывающихся чисел с первой цифрой 4 или менее.
Найдем 5 мест для цифр 5, 6, 7, 8, 9 из 9 возможных. При этом слева от них будут накрытые цифры. Для каждой ненакрытой из них должна найтись накрытая парная цифра.
Значит если мы выберем 5 мест для этих 5 цифр и при этом k из них окажутся накрытыми, то расставить их можно будет 5! способами, а остальные 5 цифр k! (5-k)! способами.
Итого надо посчитать число выбора 5 мест из 9 с k накрытиями, умножить на 5! k! (5-k)! и сложить по k от 0 до 4.
Выборы 5 мест с k накрытиями можно считать руками.
0 накрытий это всего один способ.
1 накрытие - это одна пара и 3 одиночных числа на 9 позициях, т.е. выбираем 4 позиции из 8 и выбираем одну, на которой будет пара. 4С^4_8
2 накрытия - это одна тройка и две одиночных (3 С^3_7) или две пары и одна одиночная (3 С^3_7)
3 накрытия - это четверка и одиночный (2 С^2_6) или тройка и двойка (2 C^2_6)
4 накрытия - это пятерка (C^1_5)
Итого нам необходимо выбрать для 5 6 7 8 9 пять мест из девяти возможных позиций. Для каждой такой расстановки если k из этих цифр

coteico

Таки рутина :-( мне просто кажется, что есть какая-то красивая переформулировка, перевести, скажем на двудольные графы или что-то вроде этого. Было бы здорово натолкнуться на нее.

naami_moloko

Если с компьютером, то 372486.

myxa87

У меня с компьютером получилось 184320. Это если считать, что десятизначное число не может начинаться с нуля. Если считать, что может, то 230400. Решение видимо никак не запрещает начинать числа с нуля. Мне не понятно, как в нём получаются комбинаторные коэффициенты, поэтому считал вручную на бумажке. После пары пересчётов получились такие коэффициенты:





k X(k)
0 1
1 20
2 60
3 40
4 5


и дальше суммируя по k X(k)*5!*K!*(5-k)! вроде получается 230400

naami_moloko

Да, верно, у меня была ошибка.
Оставить комментарий
Имя или ник:
Комментарий: