Question

Найдите количество 5-значных чисел, составленных из цифр 8 и 9, в которых никакие две девятки не стоят рядом. Необходимо привести развёрнутое решение.

Answer 1

ответ: 13

объяснение:

у нас для длины n = 1 может получиться только 8 и 9 - 2 числа

для n = 2 может получиться только 89, 88, 98 - 3 числа

что мы можем сделать для n = 3?

к предыдущим числам длиной 2 добавить 8

898

888

988

а также мы можем добавить 9 тогда, если последняя цифра числа не 9. Это получается только тогда, когда мы для чисел длиной 1 добавляли 8(

88, 98).

колво чисел для 3 = колво чисел для 2 + колво чисел для 1 = 2 + 3 = 5.

Получаем рекусивное соотношение

то есть чтобы узнать сколько получится чисел длиной n, нам надо добавить  к кол-ву чисел длиной n - 1 добавить 8(эти числа могут гарантированно быть т.к. 9 нету) и прибавить количество чисел длиной n - 2 (то есть мы к ним добавили 8 и их длина получилась n - 1  и к ним еще добавили девятку (их длина стала n), чтобы гарантированно не было двух девяток подряд)

и так для 4 получается = кол-во 3 + кол-во 2 = 3 + 5 = 8

для 5 получается = кол-во 4 + кол-во3 = 8 + 5 = 13

ну кароче что то вроде последовательности Фибоначчи

и так можно написать программу которая вычислит колво для любой длины

Answer 2

Для нахождения количества 5-значных чисел, составленных из цифр 8 и 9, в которых никакие две девятки не стоят рядом, мы можем воспользоваться методом перебора и правилом включения-исключения.

Правило включения-исключения гласит, что для нахождения общего количества объектов, которые подчиняются некоторым ограничениям, мы вычитаем из общего числа объектов количество объектов, которые не подходят под эти ограничения, а затем добавляем количество объектов, которые одновременно нарушают несколько ограничений. В данном случае, общее количество 5-значных чисел, составленных из цифр 8 и 9, равно 2^5, так как для каждой позиции (5 позиций) мы можем выбрать одну из двух цифр (8 или 9).

Теперь давайте найдем количество чисел, в которых две девятки стоят рядом. Для этого сначала представим, что две девятки объединены в одну "99", и у нас остаются 4 позиции для цифр 8 и 9. Мы можем выбрать либо 8, либо 9 для каждой из этих 4 позиций, поэтому количество таких чисел равно 2^4. Теперь у нас есть 2 возможных местоположения для этой "99" внутри числа, поэтому общее количество чисел, в которых две девятки стоят рядом, равно 2^4 * 2 = 32.

Теперь мы можем использовать правило включения-исключения, чтобы найти количество чисел, в которых никакие две девятки не стоят рядом:

Общее количество подходящих чисел - Количество чисел с двумя девятками рядом = 2^5 - 32 = 32 - 32 = 0

Таким образом, количество 5-значных чисел, составленных из цифр 8 и 9, в которых никакие две девятки не стоят рядом, равно 0.