198.79K

Category:

informatics

Комбинаторика в задачах ЕГЭ (задание № 8)

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

ЗАДАНИЕ №8
КОМБИНАТОРИКА
Жевтило Ирина
Аскольдовна
Учитель информатики
МБОУ «Лицей «Дубна»

2.

Борис составляет 6-буквенные коды из букв Б, О, Р, И, С. Буквы Б и Р нужно
обязательно использовать ровно по одному разу, букву С можно использовать
один раз или не использовать совсем, буквы О и И можно использовать
произвольное количество раз или не использовать совсем. Сколько различных
кодов может составить Борис?
Решение
Найдём количество шестибуквенных слов, в которых есть ровно одна буква Б и ровно
одна буква Р, тогда остаётся 4 позиции для размещения букв С, И, О:
1) Если 4 позиции занимают буквы О и И, при этом код не содержит буквы С, то
получается 2 · 2 · 2 · 2 = 16 вариантов.
2) Если 4 позиции занимают буквы О, И и С, с учётом того, что буква С может
использоваться только один раз, то получается 4 · 8 = 32 варианта.
При этом буква Б может стоять на любой из шести позиций, буква Р - на любой из
оставшихся пяти позиций, всего 6 · 5 = 30 вариантов.
Тогда количество различных кодов: 30 · (16 + 32) = 1440.
Ответ: 1440.

3.

4.

Света составляет 5-буквенные коды из букв С, В, Е, Т, А. Каждую букву нужно
использовать ровно один раз, при этом нельзя ставить рядом две гласные. Сколько
различных кодов может составить Света?
Решение
Найдём все слова, в которых учитывается условие, что каждую букву нужно
использовать ровно один раз: 5 · 4 · 3 · 2 · 1 = 120.
Вычитаем слова с рядом стоящими гласными.
Слов, в которых гласные стоят рядом на первом и втором месте — 2 · 1 · 3 · 2 · 1 = 12.
Также гласные могут стоять рядом на втором и третьем месте, на третьем и
четвёртом, на четвёртом и пятом. Значит, всего слов, в которых гласные стоят
рядом — 12 · 4 = 48. Таким образом, ответ — 120 − 48 = 72.
Ответ: 72.

5.

Света составляет 5-буквенные коды из букв С, В, Е, Т, А. Каждую букву нужно
использовать ровно один раз, при этом нельзя ставить рядом две гласные. Сколько
различных кодов может составить Света?
ks=0
b='СВЕТА'
for i in b:
for j in b:
for k in b:
for l in b:
for m in b:
s=i+j+k+l+m
if (s.count('В')==1) and (s.count('Е')==1) and (s.count('С')<=1)and
(s.count('Т')==1) and (s.count('А')==1) and (s.count('ЕА')==0) and (s.count('АЕ')==0):
ks+=1
print (ks)

6.

Света составляет 5-буквенные коды из букв С, В, Е, Т, А. Каждую букву нужно
использовать ровно один раз, при этом нельзя ставить рядом две гласные. Сколько
различных кодов может составить Света?
from itertools import *
a='СВЕТА'
k=0
for i in permutations(a, 5):
s=''.join(i)
if 'ЕА' not in s and 'АЕ' not in s:
k+=1
print (k)

7.

Света составляет 5-буквенные коды из букв С, В, Е, Т, А. Буквы в
коде могут повторяться, использовать все буквы не обязательно, но
букву С нужно использовать хотя бы один раз. Сколько различных
кодов может составить Света?
Сначала найдём общее количество слов: 5 · 5 · 5 · 5 · 5 = 3125. После
этого вычтем из них количество слов, в которых буква С не
встречается: 3125 − 4 · 4 · 4 · 4 · 4 = 2101. Таким образом, Света
может составить 2101 код.
Ответ: 2101.

8.

Света составляет 5-буквенные коды из букв С, В, Е, Т, А. Буквы в коде
могут повторяться, использовать все буквы не обязательно, но букву С
нужно использовать хотя бы один раз. Сколько различных кодов может
составить Света?
ks=0
b='СВЕТА'
for i in b:
for j in b:
for k in b:
for l in b:
for m in b:
s=i+j+k+l+m
if s.count('С')>=1:
ks+=1
print (ks)

9.

Света составляет 5-буквенные коды из букв С, В, Е, Т, А. Буквы в
коде могут повторяться, использовать все буквы не обязательно, но
букву С нужно использовать хотя бы один раз. Сколько различных
кодов может составить Света?
#2
f ro m i t e r t o o l s i m p o r t *
a='СВЕТА'
k=0
fo r i i n p ro d u c t ( a , re p e a t = 5 ) :
s=''.join(i)
if s.count('С')>=1:
k+=1
print (k)

10.

Светлана составляет коды из букв своего имени. Код должен состоять из 8 букв, и каждая
буква в нём должна встречаться столько же раз, сколько в имени Светлана. Кроме того,
одинаковые буквы в коде не должны стоять рядом. Сколько кодов может составить Светлана?
Всего слов = 8!/2!=(3*4*5*6*7*8)
Исключить АА
7 вариантов (АА_ _ _ _ _ _)=6*5*4*3*2*1*7
3*4*5*6*7*8 - 6*5*4*3*2*1*7 =1*2*3*4*5*6*7*(8-2)=15120

11.

a='СВЕТЛАНА'
z=set()
for i1 in a:
for i2 in a:
for i3 in a:
for i4 in a:
for i5 in a:
for i6 in a:
for i7 in a:
for i8 in a:
s=i1+i2+i3+i4+i5+i6+i7+i8
if 'АА' not in s:
if s.count('С')==1 and s.count('А')==2 and
s.count('В')==1 and s.count('Л')==1 and s.count('Е')==1 and s.count('Т')==1 and
s.count('Н')==1 :
z.add(s)
print (len(z))

12.

Светлана составляет коды из букв своего имени. Код должен состоять из 8 букв, и каждая
буква в нём должна встречаться столько же раз, сколько в имени Светлана. Кроме того,
одинаковые буквы в коде не должны стоять рядом. Сколько кодов может составить Светлана?
#2
f ro m i t e r t o o l s i m p o r t *
k=0
fo r x i n s e t ( p e r m u t a t io n s ( ' С В Е Т Л А Н А ' ) ) :
s=''.join(x)
if 'АА' not in s:
k+=1
print (k)

13.

Андрей составляет 4-буквенные коды из букв А, Н, Д, Р, Е, Й. Каждую букву можно
использовать любое количество раз, при этом код не может начинаться с буквы Й и
должен содержать хотя бы одну гласную. Сколько различных кодов может составить
Андрей?
Решение.
Найдём все слова, не начинающиеся с буквы Й: 5 · 6 · 6 · 6 = 1080. Теперь вычтем из
них все слова, не начинающиеся с буквы Й и не содержащие гласных:
1080 − 3 · 4 · 4 · 4 = 888. Таким образом, ответ — 888.
Ответ: 888.

14.

Андрей составляет 4-буквенные коды из букв А, Н, Д, Р, Е, Й. Каждую букву можно
использовать любое количество раз, при этом код не может начинаться с буквы Й и
должен содержать хотя бы одну гласную. Сколько различных кодов может составить
Андрей?
ks=0
b='АНДРЕЙ'
a='АНДРЕ'
for i in a:
for j in b:
for k in b:
for l in b:
s=i+j+k+l
if (s.count('Е')>=1) or (s.count('А')>=1) :
ks+=1
print (ks)

15.

Андрей составляет 4-буквенные коды из букв А, Н, Д, Р, Е, Й. Каждую букву можно
использовать любое количество раз, при этом код не может начинаться с буквы Й и
должен содержать хотя бы одну гласную. Сколько различных кодов может составить
Андрей?
#2
from itertools import*
a='АНДРЕЙ'
k=0
for i in product(a, repeat=4):
s=''.join(i)
if ((s.count('Е')>=1) or (s.count('А')>=1)) and s[0]!='Й' :
k+=1
print (k)

16.

Сколько существует шестизначных чисел, делящихся на 5, в которых каждая
цифра может встречаться только один раз, при этом никакие две чётные и две
нечётные цифры не стоят рядом.
Решение
Заметим, что чётных и нечётных цифр 5 и 5 соответственно.
Чтобы число делилось на 5, необходимо, чтобы на конце числа стояла цифра 5
или 0.
Найдём количество шестизначных чисел, делящихся на 5 и начинающихся с
нечётной цифры: 5 · 4 · 4 · 3 · 3 · 1 = 720.
Найдём количество шестизначных чисел, делящихся на 5 и начинающихся с
чётной цифры: 4 · 4 · 4 · 3 · 3 · 1 = 576.
Таким образом, получаем ответ: 720 + 576 = 1296.
Ответ: 1296.

17.

Найдите количество пятизначных восьмеричных чисел, в которых все цифры
различны и никакие две четные или нечетные не стоят рядом.
Решение.
Заметим, что чётных и нечётных цифр в восьмеричной системе счисления 4 и 4
соответственно.
Найдём количество пятизначных чисел, начинающихся с нечётной цифры:
4 · 4 · 3 · 3 · 2 = 288.
Найдём количество пятизначных чисел, начинающихся с чётной цифры:
3 · 4 · 3 · 3 · 2 = 216.
Таким образом, получаем ответ: 288 + 216 = 504.
Ответ: 504.

18.

Ольга составляет 5-буквенные коды из букв О, Л, Ь, Г, А. Каждую букву нужно
использовать ровно 1 раз, при этом Ь нельзя ставить первым и нельзя ставить после
гласной. Сколько различных кодов может составить Ольга?
Решение
Пусть буква Г обозначает гласную, а буква С — согласную. Тогда в слове на любой
позиции могут быть использованы гласные Г, согласные С и конструкция СЬ,
обозначающая какую-либо согласную с мягким знаком.
Тогда, например, при использовании в качестве согласной буквы в конструкции СЬ,
буквы Л можно будет получить 4 · 3 · 2 · 1 = 24 варианта слов.
Для оставшейся согласной буквы также получаем 24 варианта.
Таким образом, всего можно составить 2 · 24 = 48 различных кодов.
Ответ: 48.

19.

Матвей составляет 6-буквенные коды из букв М, А, Т, В, Е, Й. Каждую букву нужно
использовать ровно 1 раз, при этом код не может начинаться с буквы Й и не может
содержать сочетания АЕ. Сколько различных кодов может составить Матвей?
Решение
Сначала найдём общее количество возможных слов. Поскольку на первое место можно
поставить любую букву, кроме Й, общее количество возможных слов равняется
5 · 5 · 4 · 3 · 2 · 1 = 600.
Определим, сколько слов содержат сочетание АЕ. Пусть слово начинается с АЕ, тогда
количество вариантов равняется 1 · 1 · 4 · 3 · 2 · 1 = 24. Пусть АЕ это вторая и третья
буквы слова, тогда количество вариантов равняется 3 · 1 · 1 · 3 · 2 · 1 = 18. Пусть АЕ это
третья
и
четвёртая
буквы
слова,
тогда
количество
вариантов
равняется
3 · 3 · 1 · 1 · 2 · 1 = 18. В случае, когда АЕ это четвёртая и пятая буквы слова, количество
вариантов равняется 3 · 3 · 2 · 1 · 1 · 1 = 18. В случае, когда АЕ это пятая и шестая буквы
слова, количество вариантов равняется 3 · 3 · 2 · 1 · 1 · 1 = 18.
Таким образом, количество кодов,
600 − 24 − 18 − 18 − 18 − 18 = 504.
Ответ: 504
которые
может
составить
Матвей,
равняется

20.

Михаил составляет 6-буквенные коды. В кодах разрешается использовать только буквы
А, Б, В, Г, при этом код не может начинаться с гласной и не может содержать двух
одинаковых букв подряд. Сколько различных кодов может составить Михаил?
Решение.
На первое место слова можно поставить любую из 4 букв, кроме А. На каждое
следующее место можно поставить любую из 4 букв, кроме той, которая стоит на
предыдущем месте. Значит, всего Михаил может составить 3 · 3 · 3 · 3 · 3 · 3 = 729 кодов.

21.

Маша составляет шестибуквенные слова перестановкой букв слова КАПКАН. При этом она избегает
слов с двумя подряд одинаковыми буквами. Сколько различных кодов может составить Маша?
Решение:
1) если не учитывать, что в слове есть одинаковые буквы, общее количество перестановок 6 букв равно 6!
= 720
2) так как перестановка пары одинаковых букв не даёт нового слова, каждая пара уменьшает количество
уникальных слов в 2 раза; а у нас 2 пары (повторяются К и А), поэтому количество уникальных слов – в
4 раза меньше, оно равно 720/4 = 180
3) теперь из 180 нужно вычесть количество слов, где встречаются пары КК и АА;
4) сначала найдём количество слов, в которых встречаются обе пары, и КК, и АА; обозначим X=КК, Y=АА,
таким образом, нужно найти количество слов из 4-х разных «букв» (Н, П, Х, Y), это количество равно 4! =
24
5) теперь подсчитаем слова, в которых есть X=КК, но нет АА; получаем набор из 5 «букв» (А, A, Н, П, Х),
количество уникальных слов равно 5!/2 = 60 (учитывая, что перестановка букв А не меняет слово);
кроме того, среди них есть еще 24 слова, в которых есть обе пары, то есть имеем 60 – 24 = 36 слов, где
есть КК, но нет АА
6) аналогично получаем, что есть 36 слов, где есть АА, но нет КК
7) количество нужных нам слов равно 180 – 24 – 36 – 36 = 84.
8) Ответ: 84.

22.

Петя составляет шестибуквенные слова перестановкой букв слова АВРОРА. При этом он избегает слов с
Решение:
двумя
подряд одинаковыми буквами. Сколько всего различных слов может составить Петя?
1) если не учитывать, что в слове есть одинаковые буквы, общее количество перестановок 6 букв равно 6!
= 720
2) так как перестановка пары одинаковых букв не даёт нового слова, каждая пара уменьшает количество
уникальных слов в 2 раза; а у нас 2 пары (повторяются К и А), поэтому количество уникальных слов – в
4 раза меньше, оно равно 720/4 = 180
3) теперь из 180 нужно вычесть количество слов, где встречаются пары РР и АА;
4) сначала найдём количество слов, в которых встречаются обе пары, и РР, и АА; обозначим X=РР, Y=АА,
таким образом, нужно найти количество слов из 4-х разных «букв» (В, О, Х, Y), это количество равно 4! =
24
5) теперь подсчитаем слова, в которых есть X=РР, но нет АА; получаем набор из 5 «букв» (А, A, В, О, Х),
количество уникальных слов равно 5!/2 = 60 (учитывая, что перестановка букв А не меняет слово);
кроме того, среди них есть еще 24 слова, в которых есть обе пары, то есть имеем 60 – 24 = 36 слов, где
есть РР, но нет АА
6) аналогично получаем, что есть 36 слов, где есть АА, но нет РР
7) количество нужных нам слов равно 180 – 24 – 36 – 36 = 84.
8) Ответ: 84.

23.

Петя составляет шестибуквенные слова перестановкой букв слова ТАРТАР. Сколько всего различных слов
может составить Петя?
Решение:
1) если не учитывать, что в слове есть одинаковые буквы, общее количество перестановок 6 букв равно 6!
= 720
2) так как перестановка пары одинаковых букв не даёт нового слова, каждая пара уменьшает количество
уникальных слов в 2 раза; а у нас 3 пары (повторяются Т, Р и А), поэтому количество уникальных слов –
в 8 раз меньше, оно равно 720/8 = 90
3) Ответ: 90.

24.

Петя составляет шестибуквенные слова перестановкой букв слова МОЛОКО. Сколько всего различных слов
может составить Петя?
Решение:
1) Количество вариантов с 3 буквами «О» равно 20.
2) На оставшихся трех позициях будут стоять 3*2*1=6
3) 6*20=120
4) Ответ: 120.

25.

Юрий составляет 4-буквенные слова из букв П, Р, И, К, А, З. Каждую букву можно использовать не более
одного раза, при этом в слове нельзя использовать более одной гласной. Сколько различных кодов может
составить Юрий?
Решение:
1) Количество слов без гласных 4*3*2*1=24.
2) если в слове 1 гласная, то количество слов 1*4*3*2=24
т.к. 1 гласная может стоять на 1-м, 2-ом, 3 и 4-том местах в слове, нужно 24*4=96 слов
у нас 2 гласные, значит 96*2=192
Ответ: 192+24=216

26.

Алексей составляет 5-буквенные слова из букв М, А, Г, И, С, Т, Р. Каждую букву можно использовать не
более одного раза, при этом в слове нельзя использовать более одной гласной. Сколько различных кодов
может составить Алексей?
Решение:
1) Количество слов без гласных 5*4*3*2*1=120.
2) если в слове 1 гласная, то количество слов 1*5*4*3*2=120
т.к. 1 гласная может стоять на 1-м, 2-ом, 3 , 4-том и 5 местах в слове, нужно 120*5=600 слов
у нас 2 гласные, значит 600*2=1200
Ответ: 1200+120=1320

27.

Женя составляет слова переставляя буквы З, А, П, И, С, Ь. Сколько слов может
составить Женя, если известно, что Ь не может стоять на первом месте и после
гласной
Решение:
1) Количество слов без Ь знака на первом месте 5*5*4*3*2*1=600.
2) Количество слов с «Ь» после гласной? ИЬ*4*3*2*1=24
3) т.к. 1 гласная может стоять на 1-м, 2-ом, 3 , 4-том и 5 местах в слове, нужно
24*5=120
у нас 2 гласные, значит 120*2=240
Ответ: 600-240=360

28.

Ипполит составляет 6-буквенные слова, в которых есть только буквы М, Е, Ч, Т, А, причём буква
А используется в каждом слове хотя бы 3 раза. Каждая из других допустимых букв может
встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая
допустимая последовательность букв, не обязательно осмысленная. Сколько различных слов
может написать Ипполит?
Решение:
1) Количество слов без А 4*4*4*4*4*4=46.=4096
2) Количество слов с 1 «А» 45*6=1024*6 = 6144
3) Количество слов с 2 «А» 44*20=256*20 =5120
4) Общее количество слов =56 = 15625
Ответ: 600-240=360

29.

Ипполит составляет 6-буквенные слова, в которых есть только буквы М, Е, Ч, Т, А, причём буква
А используется в каждом слове хотя бы 3 раза. Каждая из других допустимых букв может
встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая
допустимая последовательность букв, не обязательно осмысленная. Сколько различных слов
может написать Ипполит?
Решение:
1) Количество слов без А на первом месте 4*4*4*4*4*4=46.=4096
2) Количество слов с 1 «А» 45*6=1024*6 = 6144
3) Количество слов с 2 «А» 44*15=256*15 =3840
4) Общее количество слов =56 = 15625
Ответ: 15625 – (4096+6144+3840)=1545

30.

Ипполит составляет 6-буквенные слова, в которых есть только буквы М, Е, Ч, Т, А, причём буква
А используется в каждом слове хотя бы 3 раза. Каждая из других допустимых букв может
встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая
допустимая последовательность букв, не обязательно осмысленная. Сколько различных слов
может написать Ипполит?
Решение:
1) Количество слов с 3 «А» 43*20=1280
2) Количество слов с 4 «А» 42*15=240
3) Количество слов с 5 «А» 4*6=24
4) Количество слов из 6 «А» =1
Ответ: 1280+240+24+1=1545

31.

Петя составляет шестибуквенные слова перестановкой букв слова ЧИУАУА.
Сколько всего различных слов может составить Петя?
Решение:
Используем формулу перестановок с повторениями.
Всего шесть букв. Количество повторений:
А - 2. И - 1. У - 2. Ч - 1.
6! / ( 2! * 1! * 2! * 1!) = 6! / 4 = 720 / 4 = 180.
Ответ: 180

32.

Петя составляет семибуквенные слова перестановкой букв слова ТРАТАТА.
Сколько всего различных слов может составить Петя?
Решение:
Используем формулу перестановок с повторениями.
Всего шесть букв. Количество повторений:
А - 3. Т - 3. Р - 1.
7! / ( 3! * 3! 1!) = 7*6*5*4*3*2*1 / (1*2*3* 1*2*3) = 140.
Ответ: 140

33.

Петя составляет пятибуквенные слова перестановкой букв слова МАРТА. При этом он избегает слов с
двумя подряд одинаковыми буквами. Сколько всего различных слов может составить Петя?
Общее количество слов 5!/2! (две буквы А) = 120/2=60
Чтобы буквы не повторялись исключить
*
А
*
А
А
*
3
А
А
Ответ: 36
*
2
*
1
А
А
А
6
6
6
6
24

34.

for i in range (len(s)-1):
f='МАРТ'
if s[i]==s[i+1]:
k=0
g=1
for k1 in f:
break
for k2 in f:
for k3 in f:
if s.count ('М')==1 and s.count ('А')==2 and s.count
('Р')==1 and s.count ('Т')==1 and g==0:
for k4 in f:
k+=1
for k5 in f:
print (s)
s=k1+k2+k3+k4+k5
g=0
print (k

English Русский Rules