8 Задание ЕГЭ 2021 | Комбинаторика

Лада Есакова, преподаватель информатики и математики, автор книги "Информатика. Полный курс подготовки к ЕГЭ".

Добрый день, дорогие друзья! С вами я, Есакова Лада, преподаватель информатики с 20-летним стажем.
Сегодня разберем основы комбинаторики и буквенные цепочки.

Задача:
«Все 4-буквенные слова, составленные из букв В, Н, Р, Т, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
1. ВВВВ
2. ВВВН
3. ВВВР
4. ВВВТ
5. ВВНВ
………
Запишите слово, которое стоит под номером 251.»

Обозначим В = 0, Н = 1, Р = 2, Т = 3 и получим вот такой ряд:

1. 0000
2. 0001
3. 0002
4. 0003
5. 0010

Это числовой ряд в четверичной системе исчисления. Нам нужно найти слово, которое стоит под номером 251.

Здесь важный нюанс, на котором часто ребята теряют балл. На первом месте стоит 0, то есть номер строчки на единицу больше самого числа. Поэтому на 251 месте у нас будет стоять число на единицу меньше – 250, но только в четверичной системе исчисления.

Переведем 250 в четверичную систему. Будем делить столбиком. У нас получается 250 = 3322₄. Теперь переводим цифры в буквы - ТТРР. Вот такой ответ должен получиться.
Вот такие буквенные цепочки – это, по сути, числовые ряды.

Следующая задача:
«Все 6-буквенные слова, составленные из букв С, В, Е, Т, записаны в алфавитном порядке и пронумерованы. Вот начало списка:

1. ВВВВВВ
2. ВВВВВЕ
3. ВВВВВС
4. ВВВВВТ
5. ВВВВЕВ
………
Под каким номером стоит первое из слов, которое начинается с буквы Т?»

Здесь есть еще одна ловушка: нам сказали, что все 6-буквенные слова составлены из этих букв, и очень хочется пронумеровать букву в том же порядке, в котором они представлены – С = 0, В = 1, Е = 2, Т = 3. Вот здесь-то и ошибка.

Если посмотрим на числовой ряд, то увидим, что на первой строчке у нас стоит В, значит, она будет равна 0. Далее появляется Е, значит, она равна 1, С = 2 и Т = 3.

И снова у нас четверичная система исчисления. Необходимо определить, под каким номером стоит первое из слов, которое начинается с буквы Т. Перефразирую вопрос: под каким номером стоит четверичное число, которое начинается на 3? Значит, оно должно выглядеть как 300000. Это число стоит на месте, которое на единицу больше, чем оно само, но в десятичной записи. Необходимо это число, 300000, из четверичной системы перевести в десятичную.

300000₄=3*4⁵=3*1024=3072

У нас получается число 3072, а номер строки на единицу больше, то есть номер строки будет 3073. Это и есть ответ задачи.

С такими цифровыми цепочками на сегодня мы закончим. Перейдем к более интересной теме, к элементам комбинаторики, хотя это громко сказано, потому что там от комбинаторики только одна маленькая формула.

Чтобы понять, о чем я сейчас буду говорить, давайте представим такую ситуацию: допустим, надоело нам жить в Москве и решили переехать на необитаемый остров. Для связи с внешним миром мы запасли некоторое количество цветных флажков, которые мы можем прикрепить к флагштокам и при необходимости подать сигнал. У нас есть два флагштока и флажки только двух цветов: красные и синие. Что же при помощи этого мы можем сообщить во внешний мир?

Мы можем составить 4 комбинации:

Если нам этого не хватает, мы можем добавить флажки еще одного цвета. Допустим, у нас еще есть зеленые флажки, и мы можем составить следующие комбинации:

У нас получилось 9 комбинаций.

Если же все-таки у нас флажки только двух цветов, третьего нет, у нас есть другой путь увеличить количество комбинаций, увеличив количество флагштоков. Получаем следующие комбинации:

и их получилось 8 штук.

Мы видим, что количество сообщений, которые мы можем передать внешнему миру, зависит от двух параметров: от количества букв в нашем алфавите (или, в нашем случае, от разных цветов флажков) и от длины слова (или от количества флагштоков).

Количество слов, которые мы можем закодировать, равно количеству букв в нашем алфавите (еще это называется мощностью алфавита) в степени «длина слова» A=aⁱ

«Сколько различных символов можно закодировать, используя код азбуки Морзе длиной не менее четырех и не более пяти сигналов (точек и тире)?»

Если я делаю слово из четырех сигналов, то таких слов я могу сделать 2⁴, если я делаю из пяти сигналов, то таких слов я могу придумать 2⁵. А в задаче как раз этот интервал, то есть и те, и те мне подойдут. Вот столько разных слов я могу составить 2⁴ + 2⁵ = 48.

«Коля составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует свое кодовое слово. В качестве кодовых слов Коля использует 4-буквенные слова, в которых есть буквы А, Б, В, Г, Д, причем буква Д появляется ровно 1 раз. Каждая из других допустимых букв может встречаться в кодовом слове любое количество раз или не встречаться совсем. Сколько различных кодовых слов может использовать Коля?»

Не буду мудрить, придумывать какие-то сложные формулы, а просто распишу, как буква Д может встречаться ровно один раз. Это выглядит так

Д - - -
- Д - -
- - Д -
- - - Д

то есть она может встретиться на каком-то из четырех мест. На остальных трех местах может стоять все, кроме Д, то есть 4 любые буквы по трем позициям, 4³. И так в каждом ряду. Все это сложим и получим 4*4³=4⁴=256

«Паша составляет таблицу кодовых слов для передачи сообщений. В качестве кодовых слов Паша использует 4-буквенные слова, в которых есть только буквы А, Б, В, Г, Д, Е, Ж. При этом первая буква кодового слова – это буква Д, Е или Ж, а далее в кодовом слове буквы Д, Е и Ж не встречаются. Сколько различных кодов может использовать Паша?»

У нас получается такой вид

Д - - -
Е - - -
Ж - - -

А в остальных местах используются остальные буквы, кроме Д, Е и Ж. Получаем 3*4³=3*64=192

«Герасим составляет 7-буквенные коды из букв Г, Е, Р, А, С, И, М. Каждую букву нужно использовать ровно 1 раз, при этом нельзя ставить подряд две гласные или две согласные. Сколько различных кодов может составить Герасим?»

Тут немного схитрим. Необходимо обязательно чередовать гласные и согласные, а для этого посмотрим, сколько у нас гласных. 3. А согласных 4. Поэтому на гласную начать слово я не могу, иначе их не хватит на все слово, и согласные где-то обязательно повторятся. Поэтому слово будет выглядеть таким образом: согласная – гласная – согласная – гласная – согласная – гласная – согласная.

Далее каждую букву я должна использовать ровно один раз.

Вначале состава слова согласных у нас 4, гласных – 3, далее согласных остается 3, т.к. одну я уже использовала, а согласных – 2, затем согласных 2, гласных – одна и согласная осталась одна. Теперь мы перемножаем все эти цифры

и получаем 144.

«Ольга составляет 5-буквенные коды из букв О, Л, Ь, Г, А. Каждую букву нужно использовать ровно 1 раз, при этом Ь нельзя ставить первым и нельзя ставить после гласной. Сколько различных кодов может составить Ольга?»

Давайте пойдем от противного: посчитаем все варианты, а потом выбросим те, которые нам запретили, но сразу выкинем вариант с мягким знаком на первом месте. То есть на первом месте мы можем поставить 4 различные буквы. На втором месте могу поставить все, кроме этой буквы, но зато мы можем добавить Ь, то есть тоже 4. Две буквы уже использовали. Осталось 3, 2 и 1. Все это перемножаю и получаю 96. То есть это все возможные слова, где используется буквы по одному разу, но только не начинающиеся на Ь.

Теперь из этого числа нужно выбросить ситуации, когда Ь стоит после гласной. Это, например, вот так

О Ь - - -
- О Ь - -
- - О Ь -
- - - О Ь

Таких слов 24

О Ь - - - 3*2*1
- О Ь - - 3*2*1
- - О Ь - 3*2*1
- - - О Ь 3*2*1
-----
24

Абсолютно такая же ситуация с буквой А

А Ь - - -
- А Ь - -
- - А Ь -
- - - А Ь
---------
24

И их тоже 24. То есть 96-48=48.

На этом прощаемся. Если вопросов нет, пока!

Все видео по информатике