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

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

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

Решение:

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

A O Y
0 1 2

1. 00000
2. 00001
3. 00002
…

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

200003=2*34=2*81=16210

162+1=163

Ответ: 163

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

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

  1. ААААА
  2. ААААК
  3. ААААР
  4. ААААУ
  5. АААКА

……

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

Решение:

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

A К Р У
0 1 2 3

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

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

100004=1*44=1*256=25610

256+1=257

Ответ: 257

 

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

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

  1. ААААА
  2. ААААО
  3. ААААУ
  4. АААОА

……

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

Решение:

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

A O Y
0 1 2

1. 00000
2. 00001
3. 00002
…

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

ОАОАО => 101013

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

101013=1*34+1*32+1*30=81+9+1=91

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

91+1=92

Ответ: 92

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

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

  1. ААААА
  2. ААААЗ
  3. ААААН
  4. ААААС
  5. АААЗА

……

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

Решение:

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

A З Н С
0 1 2 3

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

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

САЗАН => 301024

ЗАНАС => 102034

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

301024=3*44+1*42+2*40=768+16+2=786

102034=1*44+2*42+3*40=256+32+3=291

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

786+1=787

291+1=292

787-292+1 = 496

Ответ: 496

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

Решение:

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

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

2 _ _ _

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

2 . 4 . 4 . 4 = 128

Ответ: 128

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

Решение:

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

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

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

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

2.2.2 = 8

8 . 10 = 80

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

 

Ответ: 80

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

Решение:

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

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

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

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

3.3.3.3.3 = 243

243 . 6 = 1458

Ответ: 1458

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

Решение:

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

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

3 _ _ 2

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

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,B,C,D}, если известно, что одним из соседей A обязательно является D, а буквы B и C никогда не соседствуют друг с другом?

Решение:

 

1-й способ:

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

Итого: 29

2-й способ:

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

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

Итого – 35

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

Ответ: 29