Задание 8 ЕГЭ по информатике. Комбинаторика

🅰 Задание 1. Составление кодовых слов

Условие:
Игорь использует трёхбуквенные слова из букв Ш, К, О, Л, А, причём буква К встречается ровно 1 раз.
Остальные буквы могут повторяться.

Решение:

• Буква К может стоять на одной из трёх позиций → 3 варианта.
• Две другие буквы выбираются из 4 возможных (Ш, О, Л, А):
  4² = 16.
• Итого: 3 × 16 = 48.

Python-код:

from itertools import product
words = [x for x in product('ШКОЛА', repeat=3) if x.count('К') == 1]
print(len(words))  # 48

Ответ: 48.

🅱 Задание 2. Перестановки с ограничениями

Условие:
Маша составляет шестибуквенные слова из букв слова КАПКАН, избегая двух подряд одинаковых букв.

Решение:

Используем itertools.permutations, отбрасывая слова с АА или КК.

from itertools import permutations
words = {p for p in permutations('КАПКАН') 
         if 'АА' not in ''.join(p) and 'КК' not in ''.join(p)}
print(len(words))

Ответ: 96.

🆎 Задание 3. Условия для мягкого знака

Условие:
Маша составляет 5-буквенные коды из букв В, У, А, Л, Ь.
Каждую букву нужно использовать один раз. Буква Ь не может быть на первом месте и стоять перед гласной.

Python-решение:

from itertools import permutations
w = {x for x in permutations('ВУАЛЬ', 5)
     if 'ЬА' not in ''.join(x)
     and 'ЬУ' not in ''.join(x)
     and ''.join(x)[0] != 'Ь'}
print(len(w))  # 36

Ответ: 36 кодов.

🧩 Задание 4. Слова без запрещённого сочетания

Условие:
Вася составляет 4-буквенные коды из букв У, Л, Е, Й.
Код не может начинаться с Й и содержать сочетание ЕУ.

from itertools import permutations
w = {x for x in permutations('УЛЕЙ', 4)
     if 'ЕУ' not in ''.join(x)
     and ''.join(x)[0] != 'Й'}
print(len(w))

Ответ: 12.

🧮 Задание 5. Алфавит и обязательная буква

Условие:
Вася составляет 3-буквенные слова из букв В, Е, С, Н, А, причём буква А встречается хотя бы один раз.

Решение:

from itertools import product
words = [x for x in product('ВЕСНА', repeat=3) if x.count('А') >= 1]
print(len(words))  # 61

Ответ: 61.

💾 Задание 6. Подсчёт по условию

Условие:
Сколько существует последовательностей длиной 5 из букв A, C, G, T, содержащих ровно две буквы A?

from itertools import product
w = [x for x in product('ACGT', repeat=5) if x.count('A') == 2]
print(len(w))  # 60

Ответ: 60.

🔢 Задание 7. Позиция слова в списке

Все 4-буквенные слова из К, Л, Р, Т упорядочены алфавитно. Найти 67-е слово.

from itertools import product
w = list(product('КЛРТ', repeat=4))
print(''.join(w[67 - 1]))  # КЛТК

🧠 Задание 8. Обратный алфавитный порядок

Все 5-буквенные слова из А, О, У расположены в обратном алфавитном порядке (У → О → А). Найти 240-е слово.

from itertools import product
w = list(product('УОА', repeat=5))
print(''.join(w[240 - 1]))  # УОААО

💡 Задание 9. Комбинаторика

Алфавит из 4 символов. Сколько трёхбуквенных слов можно составить, если символы могут повторяться?

from itertools import product
w = list(product('ABCD', repeat=3))
print(len(w))  # 4³ = 64

Ответ: 64.

💡 Задание 10. Световое табло

Каждый индикатор имеет 4 цвета (белый, синий, жёлтый, красный).
Найти минимальное количество лампочек для передачи ≥300 сигналов.

for n in range(1, 10):
    if 4**n >= 300:
        print(n)
        break  # 5

Ответ: 5 лампочек.

🧾 Задание 11. Шахматная клетка

Необходимо закодировать координаты (x, y), каждая из которых может принимать 8 значений.

Количество бит на одну координату: log₂(8) = 3.

Итого для двух координат: 3 + 3 = 6 бит.

📻 Задание 12. Азбука Морзе

Коды длиной от 2 до 4 сигналов (точка/тире). Найти количество возможных комбинаций.

from itertools import product
cnt = 0
for i in range(2, 5):
    cnt += len(list(product('01', repeat=i)))
print(cnt)  # 28

Ответ: 28 символов.