8. Перебор слов и комбинаторика

Игорь составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Игорь использует трёхбуквенные слова, в которых могут быть только буквы Ш, К, О, Л, А, причём буква К появляется ровно 1 раз. Каждая из других допустимых букв может встречаться в кодовом слове любое количество раз или не встречаться совсем. Сколько различных кодовых слов может использовать Игорь?

Решение:

трёхбуквенные слова

буква К появляется ровно 1 раз

К _ _ 1*4*4 = 16 _ К _ 1*4*4 = 16 _ _ К 1*4*4 = 16

Ответ: 48

Демонстрационный вариант ЕГЭ 2019 г. – задание №10

Вася составляет 5-буквенные слова, в которых есть только буквы З, И, М, А, причём в каждом слове есть ровно одна гласная буква и она встречается ровно 1 раз. Каждая из допустимых согласных букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?

2 2 2 2 2 =2 5 = 32

Ответ: 160

Демонстрационный вариант ЕГЭ 2018 г. – задание №10

Все 4-буквенные слова, составленные из букв Д, Е, К, О, Р, записаны в алфавитном порядке и пронумерованы, начиная с 1. Ниже приведено начало списка. 1. ДДДД 2. ДДДЕ 3. ДДДК 4. ДДДО 5. ДДДР 6. ДДЕД … Под каким номером в списке идёт первое слово, которое начинается с буквы K?

Д Е К О Р 0 1 2 3 4

20015 = 2*5 3 +0+0+1 = 251

Ответ: 251

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

Демонстрационный вариант ЕГЭ 2017 г. – задание №10

По условию, буква А встречается в слове ровно 1 раз. Вася составляет 5-буквенные слова, следовательно буква А может стоять на одном из 5 мест.Таким образом, на все остальные буквы (Б, В и Г) приходится 4 свободных места.:

Число возможных 4-буквенных слов, в которых есть только 3 буквы Б, В, Г, равно 3 4 =81.

Умножаем полученные 81 вариантов на 5 возможных вариантов с буквой А и получаем правильный ответ. 81×5=405

Ответ: 405

Демонстрационный вариант ЕГЭ 2016 г. – задание №10

Игорь составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Игорь использует 5-буквенные слова, в которых есть только буквы П, И, Р, причём буква П появляется ровно 1 раз. Каждая из других допустимых букв может встречаться в кодовом слове любое количество раз или не встречаться совсем. Сколько различных кодовых слов может использовать Игорь?

По условию, буква П встречается в слове ровно 1 раз. Вася составляет 5-буквенные слова, следовательно буква А может стоять на одном из 5 мест.Таким образом, на все остальные буквы (И и Р) приходится 4 свободных места.:

Число возможных 4-буквенных слов, в которых есть только 2 буквы И, Р. Следовательно 2 4 = 16

Умножаем полученные 16 вариантов на 5 возможных вариантов с буквой П и получаем правильный ответ. 16×5=80

Ответ: 80

Запишите слово, которое стоит на 101-м месте от начала списка.

Все 5-буквенные слова, составленные из букв А, O, Y, записаны в алфавитном порядке. Вот начало списка:

ААААА
ААААO
ААААY
АААOА

Запишите слово, которое стоит на 101-м месте от начала списка.

Так как мощность алфавита равна 3(А, O, Y), то мы имеем дело с 5-буквенными словами троичной системы. Давайте преобразуем данные следующим образом:

A O Y 0 1 2

Так как первое слово принимает нулевое значение в троичной системе, а отсчет по-порядку начинается с единицы, то слово, которое стоит на 101 месте принимает значение числа 100 в троичной системе.

Ответ: OAYАО

Запишите слово, которое стоит на 150-м месте от начала списка.

Все 5-буквенные слова, составленные из букв А, К, Р, У, записаны в алфавитном порядке. Вот начало списка:

ААААА
ААААК
ААААР
ААААУ
АААКА

Запишите слово, которое стоит на 150-м месте от начала списка.

Так как мощность алфавита равна 4 (А, К, Р, У), то мы имеем дело с 5-буквенными словами четверичной системы. Давайте преобразуем данные следующим образом:

A К Р У 0 1 2 3

1. 00000 2. 00001 3. 00002 4. 00003 …

Так как первое слово принимает нулевое значение в четверичной системе, а отсчет по-порядку начинается с единицы, то слово, которое стоит на 150 месте принимает значение числа 149 в четверичной системе.

Ответ: АРККК

Сколько существует таких слов, которые м ожет на писать Алия?

Алия составляет 4-буквенные слова, в которых есть только буквы Б, А, Л, К, О, Н, причём буква Б используется в каждом слове хотя бы 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Алия?

Данная задача отличается от первой тем, что в первой определенная буква должна встретится в слове ровно 1 раз, в то время как в нашей задаче буква Б должна встретится в слове хотя бы 1 раз. Вот, что мы имеем:

После сдвига буквы Б на одну позицию вправо, на позиции, в которой стояла наша буква, количество возможных букв равно не 6, а 5, так как мы уже рассмотрели случай, когда на той позиции стояла буква Б:

1.6.6.6 + 5.1.6.6 + 5.5.1.6 + 5.5.5.1 = 671

Ответ: 671

Укажите номер первого слова, которое начинается с буквы У.

Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка:

ААААА
ААААО
ААААУ
АААОА

Укажите номер первого слова, которое начинается с буквы У.

Решение:

A O Y 0 1 2

Нам нужно найти номер первого слова, начинающееся с буквы У — 200003, после чего перевести его в десятичную систему и прибавить к нему единицу(так как наши числа в троичной системе начинаются с нуля, а отсчет номеров начинается с единицы):

Ответ: 163

Укажите номер первого слова, которое начинается с буквы К.

Все 5-буквенные слова, составленные из букв А, К, Р, У, записаны в алфавитном порядке. Вот начало списка:

ААААА
ААААК
ААААР
ААААУ
АААКА

Укажите номер первого слова, которое начинается с буквы К.

Решение:

Так как мощность алфавита равна 4 (А, К, Р, У,), то мы имеем дело с 5-буквенными словами четверичной системы. Давайте преобразуем данные следующим образом:

A К Р У 0 1 2 3

1. 00000 2. 00001 3. 00002 4. 00003 …

Нам нужно найти номер первого слова, начинающееся с буквы К — 100004, после чего перевести его в десятичную систему и прибавить к нему единицу(так как наши числа в четверичной системе начинаются с нуля, а отсчет номеров начинается с единицы):

Ответ: 257

Укажите номер слова ОАОАО.

Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка:

ААААА
ААААО
ААААУ
АААОА

Укажите номер слова ОАОАО.

Решение:

A O Y 0 1 2

Давайте переведем слово ОАОАО в троичную систему по данным нашей таблицы:

Переведем получившееся число в десятичную систему:

101013=1*3 4 +1*3 2 +1*3 0 =81+9+1=91

Нужно к числу 91 прибавить единицу(так как наши числа в троичной системе начинаются с нуля, а отсчет номеров начинается с единицы):

Ответ: 92

Какое количество слов находятся между словами САЗАН и ЗАНАС.

Все 5-буквенные слова, составленные из букв А, З, Н, С, записаны в алфавитном порядке и пронумерованы. Вот начало списка:

ААААА
ААААЗ
ААААН
ААААС
АААЗА

Какое количество слов находятся между словами САЗАН и ЗАНАС (включая эти слова)?

Решение:

Так как мощность алфавита равна 4 (А, З, Н, С), то мы имеем дело с 5-буквенными словами четверичной системы. Давайте преобразуем данные следующим образом:

A З Н С 0 1 2 3

1. 00000 2. 00001 3. 00002 4. 00003 …

Давайте переведем слово САЗАН и ЗАНАС в четверичной систему по данным нашей таблицы:

Переведем получившееся число в десятичную систему:

301024=3*4 4 +1*4 2 +2*4 0 =768+16+2=786

102034=1*4 4 +2*4 2 +3*4 0 =256+32+3=291

Нужно к числу 1554 и 547 прибавить единицу(так как наши числа в троичной системе начинаются с нуля, а отсчет номеров начинается с единицы):

Ответ: 496

Сколько слов длины 4, начинающихся с согласной буквы, можно составить из букв Л, Е, Т, О? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.

Решение:

_ _ _ _ (длины 4)

начинающихся с согласной буквы — Л, Т

можно составить из букв Л, Е, Т, О

2 . 4 . 4 . 4 = 128

Ответ: 128

Сколько существует различных символьных последовательностей длины 5 в трёхбуквенном алфавите , которые содержат ровно две буквы О?

Решение:

_ _ _ _ _ (длины 5)

в трёхбуквенном алфавите , которые содержат ровно две буквы О

О О _ _ _ О _ О _ _ О _ _ О _ О _ _ _ О _ О О _ _ _ О _ О _ _ О _ _ О _ _ О О _ _ _ О _ О _ _ _ О О

10 вариантов, где _ : К, T (2)

Второй метод, чтобы найти количество вариантов:

Ответ: 80

Вася составляет 6-буквенные слова, в которых есть только буквы К, Р, О, Т, причём буква О используется в каждом слове ровно 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?

Решение:

_ _ _ _ _ _ (длины 6)

только буквы К, Р, О, Т, причём буква О используется в каждом слове ровно 1 раз

О _ _ _ _ _ _ О _ _ _ _ _ _ О _ _ _ _ _ _ О _ _ _ _ _ _ О _ _ _ _ _ _ О

6 вариантов, где _ : К, Р, Т (3)

Ответ: 1458

Сколько слов длины 4, начинающихся с согласной буквы и заканчивающихся гласной буквой, можно составить из букв М, Е, Т, Р, О? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.

Решение:

_ _ _ _ (длины 4)

начинающихся с согласной буквы (М, Т, Р) и заканчивающихся гласной буквой Е, О

можно составить из букв М, Е, Т, Р, О

3 . 5 . 5 . 2 = 150

Ответ: 150

Вася составляет 4-буквенные слова, в которых есть только буквы К, Л, О, У, Н, причём буква У используется в каждом слове хотя бы 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?

Решение:

_ _ _ _ (длины 4)

буквы К, Л, О, У, Н, причём буква У используется в каждом слове хотя бы 1 раз.

У 5 5 5 = 125 4 У 5 5 = 100 4 4 У 5 = 80 4 4 4 У = 64

125 + 100 + 80 + 64 = 369

Ответ: 369

Вася составляет 4-буквенные слова, в которых есть только буквы К, А, Т, Е, Р, причём буква Р используется в каждом слове хотя бы 2 раза. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?

Решение:

_ _ _ _ (длины 4)

буквы К, А, Т, Е, Р, причём буква Р используется в каждом слове хотя бы 2 раза

Р Р 5 5 = 25 Р 4 Р 5 = 20 Р 4 4 Р = 16 4 Р Р 5 = 20 4 Р 4 Р = 16 4 4 Р Р = 16

25 + 20 + 16 + 20 + 16 + 16 = 113

Ответ: 113

Сколько существует различных символьных последовательностей длины 3 в четырёхбуквенном алфавите , если известно, что одним из соседей A обязательно является D, а буквы B и C никогда не соседствуют друг с другом?

Решение:

Начинается на A: ad4=4 На B: bad,bb2,bd4=7 На C: cad,cc2,cd4=7 На D: da3,db2,dc2,dd4=11

Всех вариантов 3 4 = 64

Вычисляем количество нам не подходящих вариантов: 1. вс4 = 4 2. 4вс = 4 3. 3св = 3 4. св3 = 3 5. а24 = 8 6. 3а3 = 9 7. 22а = 4

Результат 64 — 35 = 29

Ответ: 29

Катя составляет 5-буквенные к оды из⋅ букв П, Р, А, В, Ы, Й. Каждую букву нужно использовать ровно 1 раз, при этом код не может начинаться с буквы Й и не может содержать сочетания РА. Сколько различных кодов может составить Катя?

📎📎📎📎📎📎📎📎📎📎