Задание 8

Знание основных понятий и методов, используемых при измерении количества информации · 27 заданий

Задание №8
№8
Все пятибуквенные слова, в составе которых могут быть только русские буквы П, А, Р, У, С, записаны в алфавитном порядке и пронумерованы начиная с 1. Н…
Количество информации
Задание №8
№8
Определите количество пятизначных чисел, записанных в восьмеричной системе счисления, в записи которых только одна цифра 6, при этом никакая нечётная…
Количество информации
Задание №8
№8
Все четырёхбуквенные слова, в составе которых могут быть только буквы Л, Е, М, У, Р, записаны в алфавитном порядке и пронумерованы, начиная с 1. Ниже…
Количество информации
Задание №8
№8
Игорь составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Игорь исполь…
Количество информации
Задание №8
№8
Шифр кодового замка представляет собой последовательность из пяти символов, каждый из которых является цифрой от 1 до 4. Сколько различных вариантов ш…
Количество информации
Задание №8
№8
Шифр кодового замка представляет собой последовательность из пяти символов, каждый из которых является цифрой от 1 до 6. Сколько различных вариантов ш…
Количество информации
Задание №8
№8
Сколько существует различных четырёхзначных чисел, записанных в десятичной системе счисления, в записи которых есть ровно две одинаковые цифры, причём…
Количество информации
Задание №8
№8
Сколько существует различных четырёхзначных чисел, записанных в восьмеричной системе счисления, в записи которых есть ровно две одинаковые цифры, прич…
Количество информации
Задание №8
№8
Все шестибуквенные слова, в составе которых могут быть только русские буквы С, О, Р, Н, Я, К, записаны в алфавитном порядке и пронумерованы начиная с…
Количество информации
Задание №8
№8
Все 4-буквенные слова, в составе которых могут быть только буквы А, Т, О, М, записаны в алфавитном порядке и пронумерованы, начиная с 1. Ниже приведен…
Количество информации
Задание №8
№8
Все пятибуквенные слова, составленные из букв И, Н, Т, Е, Г, Р, А, Л, записаны в алфавитном порядке и пронумерованы. 1. ААААА 2. ААААГ 3. ААААЕ 4. ААА…
Количество информации
Задание №8
№8
Все шестибуквенные слова, в составе которых могут быть только русские буквы П, О, Л, Ь, З, А, записаны в алфавитном порядке и пронумерованы начиная с…
Количество информации

Задание №8 — Комбинаторика

Все пятибуквенные слова, в составе которых могут быть только русские буквы П, А, Р, У, С, записаны в алфавитном порядке и пронумерованы начиная с 1. Ниже приведено начало списка.
1. ААААА
2. ААААП
3. ААААР
4. ААААС
5. ААААУ
6. АААПА
…

Под каким номером в списке идёт последнее слово, которое содержит не более одной буквы У и не содержит букв А, стоящих рядом?

Правильный ответ

2969

Пояснение

Решение:

Выпишем используемые буквы в алфавитном порядке: А, П, Р, С, У. Нужно последнее подходящее слово списка, то есть самое «старшее» по алфавиту слово, в котором буква У встречается не более одного раза и нет двух букв А подряд.

Строим его жадно, слева направо, беря на каждом месте максимально возможную букву. На первое место ставим У — это допустимо, ведь одна У разрешена. После этого У использовать уже нельзя, и старшая из оставшихся букв — С. Букв С подряд может стоять сколько угодно (ограничение касается только буквы А), поэтому остальные четыре места заполняем буквой С. Получаем слово УСССС: в нём одна У и нет сочетания АА.

Теперь найдём его номер. Занумеруем буквы по алфавиту: А — 0, П — 1, Р — 2, С — 3, У — 4. Тогда пятибуквенное слово превращается в пятизначное число в пятеричной системе счисления, а номер слова в списке на единицу больше значения этого числа (первому слову ААААА соответствует число 0).

Слову УСССС отвечает набор цифр 4, 3, 3, 3, 3:

$4 \cdot 5^4 + 3 \cdot 5^3 + 3 \cdot 5^2 + 3 \cdot 5 + 3 = 2500 + 375 + 75 + 15 + 3 = 2968.$

Значит, слово УСССС стоит под номером $2968 + 1 = 2969$ .

from itertools import product

alpha = 'АПРСУ'          # буквы уже в алфавитном порядке
answer = 0
for i, w in enumerate(product(alpha, repeat=5), 1):
    s = ''.join(w)
    if s.count('У') <= 1 and 'АА' not in s:
        answer = i        # запоминаем последнее подходящее слово
print(answer)   # 2969

Ответ: 2969