Сколько 2013-значных чисел можно составить так, чтобы любое двузначное число, образованное парами соседних цифр, делилось на 17 или на 23?
Математика 11 класс Комбинаторика 2013-значные числа Двузначные числа делимость на 17 делимость на 23 пары соседних цифр комбинаторика математика 11 класс
Для решения задачи нам нужно выяснить, какие двузначные числа делятся на 17 или 23. Начнем с поиска всех таких чисел.
Шаг 1: Находим двузначные числа, делящиеся на 17.Теперь объединим эти два списка:
Теперь нам нужно выяснить, какие цифры могут следовать друг за другом, чтобы образовать допустимые двузначные числа. Для этого рассмотрим все найденные числа:
Теперь мы можем представить возможные переходы между цифрами в виде графа:
Обозначим количество возможных 2013-значных чисел как N. Каждая цифра может быть выбрана в зависимости от предыдущей цифры. Для этого удобно использовать динамическое программирование.
Обозначим dp[i][j] как количество чисел длиной i, заканчивающихся на цифру j. Начнем с инициализации dp[1][j] для всех j, где j — допустимые начальные цифры.
Шаг 7: Заполнение массива dp.В конце, сумма всех dp[2013][j] для всех j даст нам искомое количество 2013-значных чисел.
Таким образом, ответ на задачу будет найден в результате выполнения описанных шагов с учетом всех переходов и начальных условий.