№ 6998 (Уровень: Средний) Генератор паролей составляет пароль длиной 7 символов из набора букв {Q, W, E, R, T, Y, N, O}. При генерации пароля отбрасываются пароли, в которых содержится подстрока QWERTY и все пароли, в которых один и тот же символ встречается более чем 2 раза. PASHTOS Сколько всего различных паролей может составить данный генератор?

Решение:

1. Найдем общее количество паролей длиной 7 символов из 8 возможных. Так как каждый символ может быть любым из 8, то общее количество паролей равно: $$8^7 = 2097152$$

2. Исключим пароли, содержащие подстроку QWERTY. Длина подстроки 6, следовательно, подстрока может начинаться с позиции 1 или 2. Т.е. существует два варианта QWERTYх и хQWERTY, где x - любая из 8 букв. Значит количество таких паролей равно: $$2 \cdot 8 = 16$$.

3. Исключим пароли, в которых один и тот же символ встречается более 2 раз. Имеем 8 символов. Разберем этот пункт методом перебора и исключения вариантов.

Рассмотрим максимальное количество повторений символа в пароле: 7, 6, 5, 4, 3. Случаи 7, 6, 5, 4 повторений проще посчитать, так как количество вариантов не большое. Случай 3 повторений сложнее.

Если 7 одинаковых символов, то вариантов 8 (QQQQQQQ, WWWWWWW, ...). Т.е. количество паролей равно 8.

Если 6 одинаковых символов, то таких паролей $$8 \cdot 7 = 56$$. На 7 позиций можно поставить любую из 8 букв 6 раз, а на оставшуюся позицию любую из оставшихся 7 букв.

Если 5 одинаковых символов, то таких паролей $$8 \cdot \frac{7 \cdot 6}{2} \cdot 7 \cdot 7 = 8232$$. На 7 позиций можно поставить любую из 8 букв 5 раз, выбираем 2 позиции из 7 для оставшихся двух символов, и на каждую позицию можно поставить любую из оставшихся 7 букв. .

Если 4 одинаковых символов, то таких паролей $$8 \cdot \frac{7 \cdot 6 \cdot 5}{3 \cdot 2} \cdot 7 \cdot 7 \cdot 7 = 144060$$. На 7 позиций можно поставить любую из 8 букв 4 раза, выбираем 3 позиции из 7 для оставшихся 3 символов, и на каждую позицию можно поставить любую из оставшихся 7 букв. .

Если 3 одинаковых символа. Разберем подробнее. Выбираем какой из 8 символов повторяется. Выбираем 3 позиции из 7. Осталось 4 позиции. На них не должно быть повторяющихся символов. Первый символ не должен совпадать с выбранным, т.е. 7 вариантов. Второй символ не должен совпадать с первым, т.е. 6 вариантов. Третий символ не должен совпадать с первыми двумя, т.е. 5 вариантов. Четвертый символ не должен совпадать с первыми тремя, т.е. 4 варианта. Итого $$8 \cdot \frac{7 \cdot 6 \cdot 5}{3 \cdot 2} \cdot 7 \cdot 6 \cdot 5 \cdot 4 = 235200$$.

Итак, общее количество паролей с повторениями (7,6,5,4,3) равно: $$8 + 56 + 8232 + 144060 + 235200 = 387556$$.

Вывод:

Общее количество паролей минус пароли с подстрокой QWERTY, минус пароли с повторениями равно:$$2097152 - 16 - 387556 = 1709580$$.

Ответ: 1709580