Сколько 2013-значных чисел можно составить так, чтобы любое двузначное число, образованное парами соседних цифр, делилось на 17 или на 23?

Математика 11 класс Комбинаторика 2013-значные числа Двузначные числа делимость на 17 делимость на 23 пары соседних цифр комбинаторика математика 11 класс Новый

Для решения задачи нам нужно выяснить, какие двузначные числа делятся на 17 или 23. Начнем с поиска всех таких чисел.

Шаг 1: Находим двузначные числа, делящиеся на 17.

• Первое двузначное число, делящееся на 17, это 17.
• Последнее двузначное число, делящееся на 17, это 85.
• Теперь перечислим все такие числа: 17, 34, 51, 68, 85.

Шаг 2: Находим двузначные числа, делящиеся на 23.

• Первое двузначное число, делящееся на 23, это 23.
• Последнее двузначное число, делящееся на 23, это 92.
• Перечислим все такие числа: 23, 46, 69, 92.

Шаг 3: Объединяем все найденные числа.

• Числа, делящиеся на 17: 17, 34, 51, 68, 85.
• Числа, делящиеся на 23: 23, 46, 69, 92.

Теперь объединим эти два списка:

• 17, 23, 34, 46, 51, 68, 69, 85, 92.

Шаг 4: Определяем возможные пары цифр.

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

• 17: цифры 1 и 7
• 23: цифры 2 и 3
• 34: цифры 3 и 4
• 46: цифры 4 и 6
• 51: цифры 5 и 1
• 68: цифры 6 и 8
• 69: цифры 6 и 9
• 85: цифры 8 и 5
• 92: цифры 9 и 2

Шаг 5: Строим граф переходов.

Теперь мы можем представить возможные переходы между цифрами в виде графа:

• 1 → 7
• 2 → 3
• 3 → 4
• 4 → 6
• 5 → 1
• 6 → 8
• 6 → 9
• 8 → 5
• 9 → 2

Шаг 6: Подсчет возможных 2013-значных чисел.

Обозначим количество возможных 2013-значных чисел как N. Каждая цифра может быть выбрана в зависимости от предыдущей цифры. Для этого удобно использовать динамическое программирование.

Обозначим dp[i][j] как количество чисел длиной i, заканчивающихся на цифру j. Начнем с инициализации dp[1][j] для всех j, где j — допустимые начальные цифры.

Шаг 7: Заполнение массива dp.

1. Для каждой цифры j от 0 до 9:
2. Для каждого i от 2 до 2013:
3. Считаем dp[i][j] как сумму dp[i-1][k] для всех k, которые могут переходить в j.

В конце, сумма всех dp[2013][j] для всех j даст нам искомое количество 2013-значных чисел.

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