Задание 8. Позиционные системы счисления. Комбинаторика

Задание 8 демонстрационного варианта ЕГЭ-2027 (ФИПИ).

Все пятибуквенные слова, составленные из букв А, К, Ц, Е, Н, Т, записаны в алфавитном порядке и пронумерованы. Вот начало списка:

1. ААААА
2. ААААЕ
3. ААААК
4. ААААН
5. ААААТ
6. ААААЦ

……

Определите, под каким номером в этом списке стоит первое слово с чётным номером, которое не начинается с букв А, Е или К и при этом содержит в своей записи не менее одной буквы Т.

Примечание. Слово – последовательность идущих подряд букв, не обязательно осмысленная.

Смысл формулы - это просто перевод числа из 6-ричной системы счисления в десятичную со сдвигом на 1.В формуле $c_k$ – цифра $k$-й буквы, $n$ – длина слова, то есть число разрядов. Цифра буквы – её место в алфавите, считая с нуля; у набора из 6 букв цифры такие:

1. Расставьте буквы по алфавиту и раздайте им цифры. В условии буквы перечислены не по алфавиту (А, К, Ц, Е, Н, Т), а нумерация списка идёт именно по алфавиту. Сортируем: А, Е, К, Н, Т, Ц – и получаем цифры от 0 до 5.
2. Слово – это 5-значное шестеричное число, а номер – это число плюс единица. Список начинается с единицы, а числа – с нуля: ААААА – это $00000_6$, то есть ноль, а стоит оно под номером 1.
3. «Чётный номер» – это нечётное число. Номер чётный – значит, значение слова нечётное. Основание 6 чётное, поэтому все разряды, кроме последнего, дают чётный вклад: чётность числа решают только единицы. Значит последняя буква обязана быть нечётной цифрой – Е (1), Н (3) или Ц (5). Это главный шаг, на котором задание проваливают.
4. «Не начинается с А, Е, К» – первая цифра не меньше 3. Остаются Н (3), Т (4) и Ц (5).
5. «Первое слово» – значит наименьшее. Слова идут по алфавиту, то есть по возрастанию значения, поэтому первое подходящее – это наименьшее подходящее. Собираем его по разрядам слева направо, каждый раз беря самую младшую допустимую букву.
6. Первая буква – Н, самая младшая из разрешённых.
7. Куда поставить обязательную Т. Первая буква уже занята под Н, а последняя обязана быть нечётной – Т это цифра 4, чётная, значит на последнее место она не годится. Остаются 3 позиции: 2, 3 и 4. Чем правее стоит «дорогая» буква, тем меньше слово, поэтому Т ставим на 4-е место, а остальные позиции отдаём самой младшей букве – А.
8. Последняя буква – Е, наименьшая из нечётных цифр.
9. Итог: слово НААТЕ.

Слово НААТЕ – это шестеричная запись 30041. Считаем вклад каждого разряда:

Сумма: $3888 + 24 + 1 = 3913$. Это значение слова.

Номер в списке на единицу больше: $3913 + 1 = 3914$.

Ответ: 3914.
Быстрый перевод на экзамене лучше сделать в python:

Бывают задания 8, в которых спрашивают не номер, а количество. Перевод в десятичную систему здесь не нужен вовсе: нумерация понадобится ровно один раз – чтобы вытащить из неё чётность.

Условие. Все шестибуквенные слова, составленные из букв Ц, В, Е, Т, О, К, записаны в алфавитном порядке и пронумерованы. Вот начало списка:

1. ВВВВВВ
2. ВВВВВЕ
3. ВВВВВК
4. ВВВВВО
5. ВВВВВТ
6. ВВВВВЦ

……

Определите в этом списке количество слов с нечётными номерами, в записи которых не содержится ни одной из букв В, Е или К и при этом имеется ровно две буквы Т и ровно одна буква Ц.

1. Раздайте цифры по алфавиту. В, Е, К, О, Т, Ц – цифры от 0 до 5. Набор другой, правило то же.
2. «Нечётный номер» – это чётное значение. Тот же сдвиг на единицу, только в другую сторону: последняя цифра слова обязана быть чётной.
3. Чётная буква остаётся ровно одна. Букв В, Е и К в слове нет вовсе, в запасе только О (3), Т (4) и Ц (5). Чётная среди них одна – Т. Последнюю букву не выбирают, она уже известна.
4. Выпишите состав слова. Мест 6: две Т, одна Ц, всё остальное – О, то есть 3 буквы.
5. Одна Т уже потрачена на последнее место. На оставшихся 5 местах надо расставить одну Т, одну Ц и 3 буквы О.
6. Считайте места, а не слова. Место для Т выбирается 5 способами, после него место для Ц – 4 оставшимися, а О занимает всё, что осталось, единственным способом: $5 \cdot 4 = 20$.

Ответ: 20.

Комбинаторику во втором вопросе можно не разбирать вовсе. Список слов конечен, и он маленький: пройти его целиком и посчитать подходящие – десять строк. На экзамене это часто надёжнее, чем формула, выведенная в спешке.

Сколько всего слов? Столько же, сколько чисел той же длины в системе с основанием 6: $6^{6}$ – это 46 656. Перебор такого размера Python проходит за сотые доли секунды.

Порядок величин, чтобы оценить время проверки чисел

Главная ловушка перебора: буквы в product надо передаватьпо алфавиту. Номер слова – это его место в отсортированном списке. Передадите буквы в том порядке, в каком они выписаны в условии, – и enumerate пронумерует совсем другой список, а вместе с номерами уедет и чётность.

Тот же цикл отвечает и на первый вопрос разбора: убрать счётчик, поставить break на первом подходящем слове и напечатать number.

Скрипт короткий, но три его места стоит разобрать отдельно – они и делают всю работу.

itertools – стандартный модуль, ставить ничего не надо. product – это декартово произведение: все способы взять по одному элементу из каждого набора. Запись product(letters, repeat=6) означает «6 раз подряд возьми любую букву из letters», то есть все слова нужной длины.

Важно, в каком порядке они выдаются: быстрее всего меняется последняя позиция, медленнее всего первая.

product('АБ', repeat=2)  ->  ('А','А'), ('А','Б'), ('Б','А'), ('Б','Б')

Это в точности алфавитный порядок – но только если сами буквы переданы по алфавиту. Отсюда и letters = 'ВЕКОТЦ', а не 'ЦВЕТОК'.

enumerate(..., start=1)

enumerate нумерует то, что ему дают: на каждом витке цикла возвращает пару «номер, элемент». start=1 велит начинать счёт с единицы – ровно как в условии. Поэтому number и есть номер слова в списке, заводить свой счётчик не нужно.

chars – это кортеж из 6 букв, например ('В','В','В','В','В','Е'), а ''.join(chars) склеивает его в строку 'ВВВВВЕ' – со строкой дальше удобнее.

if set(word) & set('ВЕК')

set(строка) – множество различных букв строки: у 'ВВВВВЕ' это {'В','Е'}, повторы отбрасываются. Значок & – пересечение множеств, то есть то, что есть и там, и там.

Значит set(word) & set('ВЕК') – это буквы, которые есть и в слове, и среди запрещённых. Пустое множество Python считает ложью, непустое – истиной, поэтому сравнивать ни с чем не надо: if срабатывает ровно тогда, когда в слове нашлась хотя бы одна запрещённая буква. Читается как «если у слова есть общие буквы с ВЕК», а continue отправляет цикл к следующему слову, не проверяя остального.

Остальное проще:

Три проверки идут подряд и независимо друг от друга – в этом весь приём. Поменялось условие задачи – меняются только эти три строки, всё остальное остаётся как есть.

1. Забыли прибавить единицу. Посчитали значение слова и записали 3913. Список нумеруется с единицы, а числа начинаются с нуля – между значением и номером всегда сдвиг на 1.
2. Раздали цифры в том порядке, в каком буквы даны в условии. В условии написано «из букв А, К, Ц, Е, Н, Т», и это не алфавит. Цифры назначаются по алфавиту; сверяйтесь с началом списка, оно для того и приведено.
3. Перепутали чётность номера с чётностью последней цифры. «Чётный номер» – это нечётное значение, и наоборот. Один лишний или потерянный сдвиг на единицу здесь меняет и слово, и ответ.
4. Собрали слово, нарушив собственные же правила. Чаще ответ портит не арифметика, а сборка: начали с запрещённой буквы, поставили обязательную не туда, забыли, что последнее место закрыто под нечётную цифру. Ищем первое слово – значит наименьшее, и обязательную букву надо задвигать как можно правее: поставив Т сразу после Н, получим НТААЕ – условиям оно отвечает, но стоит под номером 4754, а не 3914, и первым не является. Собрали слово – пройдитесь по условию ещё раз, пункт за пунктом.
5. В подсчёте посчитали буквы, а не места. Одна Т уже ушла на последнее место, и расставлять на свободных местах надо то, что осталось, а не весь состав слова заново. Иначе выйдет 6 $\cdot$ 5 вместо 5 $\cdot$ 4.