8 - Комбинаторика

Источники:

сайт Полякова (https://kpolyakov.spb.ru/)

демонстрационная версия станции КЕГЭ (https://kompege.ru/)

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

Решение

from itertools import *

s=0

for i in product('ПИР',repeat=5):

if i.count('П')==1: s+=1

print(s)

Ответ: 80

2) (№ 205) Сколько слов длины 5, начинающихся с гласной буквы, можно составить из букв Е, Г, Э? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.

Решение

from itertools import *

s=0

for i in product('ЕГЭ',repeat=5):

if i[0] in 'ЕЭ': s+=1

print(s)

Ответ: 162

3) (№ 206) Сколько существует различных символьных последовательностей длины 5 в четырёхбуквенном алфавите {A, C, G, T}, которые содержат ровно две буквы A?

Решение

from itertools import *

s=0

for i in product('ACGT',repeat=5):

if i.count('A')==2: s+=1

print(s)

Ответ: 270

4) (№ 208) Алексей составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Алексей использует 5-буквенные слова, в которых есть только буквы A, B, C, X, причём буква X может появиться на последнем месте или не появиться вовсе. Сколько различных кодовых слов может использовать Алексей?

Решение

from itertools import *

s=0

for i in product('ABCX',repeat=5):

if i[:-1].count('X')==0: s+=1

print(s)

Ответ: 324

4) (№ 208) Алексей составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Алексей использует 5-буквенные слова, в которых есть только буквы A, B, C, X, причём буква X может появиться на последнем месте или не появиться вовсе. Сколько различных кодовых слов может использовать Алексей?

Решение

from itertools import *

s=0

for i in product('ABCX',repeat=5):

if i[:-1].count('X')==0: s+=1

print(s)

Ответ: 324

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

Решение

from itertools import *

s=0

for a in product('ABCD',repeat=3):

i=''.join(a)

if i.count('CB')+i.count('BC')==0:

if i.count('A')==0: s+=1

elif i.count('A')==1 and i.count('AD')+i.count('DA')>0: s+=1

elif i=='ADA': s+=1

print(s)

Ответ: 29

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

Решение

from itertools import *

s=0

for i in product('МЕТРО',repeat=4):

if i[0] in 'МТР' and i[-1] in'ЕО':s+=1

print(s)

Ответ: 150

7) (№ 1885) Андрей составляет 7-буквенные коды из букв А, Н, Д, Р, Е, Й. Буквы А и Й должны встречаться в коде ровно по одному разу, при этом буква Й не может стоять на первом месте. Остальные допустимые буквы могут встречаться произвольное количество раз или не встречаться совсем. Сколько различных кодов может составить Андрей?

Решение

from itertools import *

s=0

for i in product('АНДРЕЙ',repeat=7):

if i.count('А')*i.count('Й')==1 and i[0]!='Й':s+=1

print(s)

Ответ: 36864

8) (№ 1888) Маша составляет шестибуквенные слова перестановкой букв слова КАПКАН. При этом она избегает слов с двумя подряд одинаковыми буквами. Сколько различных кодов может составить Маша?

Решение

from itertools import *

s=0

ak=''

for i in permutations('КАПКАН'):

a=''.join(i)

k=0

for j in 'КАПН':k+=a.count(j+j)

if k==0 and ak.find(a+':')==-1: s+=1;ak+=a+':'

print(ak.count(':'))

Ответ: 84

9) (№ 1889) Маша составляет 5-буквенные коды из букв В, У, А, Л, Ь. Каждую букву нужно использовать ровно 1 раз, при этом код буква Ь не может стоять на первом месте и перед гласной. Сколько различных кодов может составить Маша?

Решение

from itertools import *

s=0

for i in permutations('ВУАЛЬ'):

a=''.join(i)

if a[0]!='Ь':

s+=1

if 0<a.find('Ь')<4 and a[a.find('Ь')+1] in 'УА':s-=1

print(s)

Ответ: 60

10) (№ 1890) Вася составляет 4-буквенные коды из букв У, Л, Е, Й. Каждую букву нужно использовать ровно 1 раз, при этом код не может начинаться с буквы Й и не может содержать сочетания ЕУ. Сколько различных кодов может составить Вася?

Решение

from itertools import *

s=0

for i in permutations('УЛЕЙ'):

a=''.join(i)

if a[0]!='Й' and a.find('ЕУ')==-1:

s+=1

print(s)

Ответ: 14

11) (№ 1949) Маша составляет 7-буквенные коды из букв П, Е, С, К, А, Р, Ь. Каждую букву нужно использовать ровно 1 раз, при этом буква Ь не может стоять на первом месте, а также перед буквами Е, А и Р. Сколько различных кодов может составить Маша?

Решение

from itertools import *

s='ПЕСКАРЬ'

k=0

for st0 in permutations(s,7):

st=''

for i in st0:st+=i

if st[0]!='Ь':

st+=' '

if 'АЕР'.find(st[st.find(s[-1])+1])==-1:

k+=1

print(k)

Ответ: 2520

12) (№ 1959) Петя составляет семибуквенные слова перестановкой букв слова АССАСИН. Сколько всего различных слов может составить Петя?

Решение

from itertools import *

s=' АССАСИН '

ss=''.join(sorted(s))

a=''

k=0

for st0 in permutations(s,7):

st=''

for i in st0:st+=i

if ss==''.join(sorted(st)):

if a.find(st)==-1:

k+=1;a+=st+' '

print(k)

Ответ: 420

13) (№ 1960) Петя составляет шестибуквенные слова перестановкой букв слова ЧИУАУА. Сколько всего различных слов может составить Петя?

Решение

from itertools import *

s='ЧИУАУА'

ss=''.join(sorted(s))

a=''

k=0

for st0 in permutations(s,6):

st=''

for i in st0:st+=i

if ss==''.join(sorted(st)):

if a.find(st)==-1:

k+=1;a+=st+' '

print(k)

Ответ: 180

14) (№ 1961) Петя составляет семибуквенные слова перестановкой букв слова ТРАТАТА. Сколько всего различных слов может составить Петя?

Решение

from itertools import *

s='ТРАТАТА'

ss=''.join(sorted(s))

a=''

k=0

for st0 in permutations(s,7):

st=''

for i in st0:st+=i

if ss==''.join(sorted(st)):

if a.find(st)==-1:

k+=1;a+=st+' '

print(k)

Ответ: 140

15) (№ 1945) Петя составляет 7-буквенные слова из букв А, Б, Р, И, К, О, С. Каждую букву нужно использовать ровно 1 раз, при этом нельзя ставить подряд две гласные или две согласные. Сколько различных кодов может составить Петя?

Решение

Вариант 1 (ручной)

Имеем 4 - согласных (Б,Р,К,С) и 3 - гласных буквы (А, И, О).

Единственное расположение этих букв в слове из семи букв - Со Гл Со Гл Со Гл Со

С учетом неповторяемости букв получаем такую зависимость - 4*3*3*2*2*1*1 = 144

Вариант 2 (программный - дубовый)

s='абрикос'

m=['аи','иа','ао','оа','ио','ои','бр','рб','бк','кб','бс','сб','рк','кр','рс','ср','кс','ск']

kk=0

for s1 in s:

for s2 in s:

for s3 in s:

for s4 in s:

for s5 in s:

for s6 in s:

for s7 in s:

ss=s1+s2+s3+s4+s5+s6+s7

k=1

for i in s:

k*=ss.count(i)

if k==1:

k=0

for i in m:

k+=ss.count(i)

if k==0:

kk+=1

print(kk)

Ответ: 144

16) (№ 4249 А.Куканова) Лиля составляет 5-буквенные слова из букв С, О, Т, К, А, П, Л, З. Слово не должно заканчиваться на гласную и содержать сочетания ЗЛО. Буквы в слове не повторяются. Сколько слов может составить Лиля?

Решение

Вариант 1

from itertools import *

n = 0

for x in product('СОТКАПЛЗ', repeat=5):

x=''.join(x)

if not('ЗЛО' in x or x[4]=='О' or x[4]=='А'):

g=''

for k in x:

if not(k in g):

g+=k

if len(g)==5:

n+=1

print(n)

Вариант 2

from itertools import *

s='СОТКАПЛЗ'

k=0

for st0 in permutations(s,5):

st=''

for i in st0:st+=i

if not(st[4] in'АО'):

if not('ЗЛО' in st):

k+=1

print(k)

Ответ: 5008

17) (№ 1934) Вася составляет 5-буквенные коды из букв Г, Е, Л, И, Й. Каждую букву нужно использовать ровно 1 раз, при этом код не может начинаться с буквы Й и не может содержать сочетания ИЕЙ. Сколько различных кодов может составить Вася?

Решение

from itertools import *

s='ГЕЛИЙ'

k=0

for st0 in permutations(s,5):

st=''.join(st0)

if st[0]!='Й' and st.count('ИЕЙ')==0:k+=1

print(k)

Ответ: 90

18) (№ 2928 Апробация 19 февраля 2022 года, Москва) Определите количество семизначных чисел, записанных в семеричной системе счисления, учитывая, что числа не могут начинаться с цифр 3 и 5 и не должны содержать сочетания цифр 22 и 44 одновременно.

Решение

from itertools import *

k=0

for i1 in '1246':

for i in product('0123456',repeat=6):

c=i1+''.join(i)

if c.count('22')*c.count('44')==0: k+=1

print(k)

Ответ: 466456

19) (№ 5738 П. Финкель ) Маша составляет шестибуквенные слова из букв Т, И, М, А, Ш, Е, В, С, К. Она выбирает только те слова, в которых гласных меньше, чем согласных, и буква Ш не стоит рядом с согласной. Сколько таких слов может составить Маша?

Решение

a='ТИМАШЕВСК'

ag='ИАЕ'

zapret=['ШТ','ШМ','ШШ','ШВ','ШС','ШК','КШ','СШ','МШ','ТШ','ВШ']

k=0

for s1 in a:

for s2 in a:

for s3 in a:

for s4 in a:

for s5 in a:

for s6 in a:

s=s1+s2+s3+s4+s5+s6

ng=s.count('И')+s.count('А')+s.count('Е')

if ng*2<6:

fl=1

for p in zapret:

if p in s:

fl=0

break

if fl:

k+=1

print(k)

Ответ: 174175

20) (№ 4447 А.Богданов) МАРИНА из букв своего имени составляет слова перестановкой исходных букв. Сколько различных слов может составить МАРИНА, если первая буква не может быть гласной?

6Решение

from itertools import *

s,m='МАРИНА',set()

for st in map(''.join):

if st[0] in 'МРН': m.add(st)

print(len(m))

Ответ: 180

21) (№ 4256 А.Куканова) Оля составляет 5-буквенные слова из букв К, У, С, А, Т, Ь, причём слова не должны начинаться на мягкий знак и содержать сочетание СУК. Буквы в слове не должны повторяться. Сколько различных слов может составить Оля?

Решение

from itertools import *

s,m='КУСАТЬ',set()

for st in map(''.join,permutations(s,5)):

if st[0] !='Ь'and st.count('СУК')==0: m.add(st)

print(len(m))

Ответ: 586

22) (№ 4255 А.Куканова) Мила составляет 4-значные числа в 8-ичной системе. Сколько различных чисел, делящихся на 4 без остатка, может составить Мила?

Решение

from itertools import *

k=0

for a in map(''.join,product('01234567',repeat=4)):

if a[0]!='0' and a[-1] in '04': k+=1

print(k)

Ответ: 896

23) (№ 4254 А.Куканова) Полина составляет 5-значные числа в 5-ичной системе счисления, которые содержат не более 3 чётных цифр. Сколько различных чисел может составить Полина?

Решение

from itertools import *

k=0

for a in map(''.join,product('01234',repeat=5)):

n=a.count('0')+a.count('2')+a.count('4')

if a[0]!='0' and n<=3: k+=1

print(k)

Ответ: 1744

24) (№ 4253 А.Куканова) Евгения составляет 4-значные числа в 8-ичной системе счисления. Числа должны начинаться с чётной цифры, и цифры в них располагаются в невозрастающем порядке. Сколько различных чисел может составить Евгения?

Решение

from itertools import *

m=set()

for a in map(''.join,product('01234567',repeat=4)):

f=1

for i in range(len(a)-1):

if a[i+1]>a[i]:

f=0

break

if a[0] in'246' and f: m.add(a)

print(len(m))

Ответ: 129

25) (№ 4252 А.Куканова) Аня составляет слова, переставляя буквы в слове ОДЕКОЛОН, избегая слов, где соседние буквы — одинаковые. Сколько различных слов, включая исходное, может составить Аня?

Решение

from itertools import *

m=[]

for c in set(map(''.join, permutations('ОДЕКОЛОН'))):

if 'ОО' not in c: m.append(c)

print(len(m))

Ответ: 2400

26) (№ 4251 А.Куканова) Маша составляет 6-буквенные слова из букв З, Е, Р, К, А, Л, О, содержащие букву К, но не более 4 раз. Остальные буквы не могут повторяться. Сколько различных слов может составить Маша?

Решение

Решение 1

from itertools import *

k=0

for i in product('ЗЕРКАЛО',repeat=6):

i=''.join(i)

s=''

for a in i:

if not(a in s) or a=='К':s+=a

if len(s)==6 and 0<s.count('К')<=4: k+=1

print(k)

Решение 2

from itertools import *

m=[]

for c in set(map(''.join,permutations('ЗЕРКАЛОККК',6))):

if 'К' in c: m.append(c)

print(len(m))

Ответ: 12570

27) (№ 4250 А.Куканова) Лиза составляет слова из букв О, Н, И, К, С, причём буква С должна встречаться в этих словах ровно 3 раза, а буква О — ровно 1 раз. Длина слова составляет от 4 до 6 букв. Сколько различных слов может составить Лиза?

Решение

from itertools import *

k=0

for p in range(4,7):

for c in map(''.join, product('ОНИКС',repeat=p)):

if c.count('О')==1 and c.count('С')==3: k+=1

print(k)

Ответ: 604

28) (№ 4249 А.Куканова) Лиля составляет 5-буквенные слова из букв С, О, Т, К, А, П, Л, З. Слово не должно заканчиваться на гласную и содержать сочетания ЗЛО. Буквы в слове не повторяются. Сколько слов может составить Лиля?

Решение

from itertools import *

m=[]

for c in map(''.join,permutations('СОТКАПЛЗ',5)):

if c[-1] not in 'ОА' and 'ЗЛО'not in c: m.append(c)

print(len(m))

Ответ: 5008

29) (№ 4248 А.Куканова) Марта составляет 6-буквенные слова из букв И, Н, Ф, А, причём буква Ф должна встречаться в слове ровно 2 раза. Остальные буквы могут встречаться любое количество раз или не встречаться вообще. Сколько слов может составить Марта?

Решение

from itertools import *

m=[]

for c in map(''.join,product('ПИКАЧУ',repeat=5)):

if c.count('У')>=2: m.append(c)

print(len(m))

Ответ: 1526

30) (№ 4247 А.Куканова) Агата составляет 5-буквенные слова из букв П, И, К, А, Ч, У, причём буква У должна встречаться в слове хотя бы два раза. Остальные буквы могут встречаться любое число раз, в том числе не встречаться вообще. Сколько слов может составить Агата?

Решение

from itertools import *

m=[]

for c in map(''.join,product('ПИКАЧУ',repeat=5)):

if c.count('У')>=2: m.append(c)

print(len(m))

Ответ: 1526

31) (№ 3223) Сергей составляет 6-буквенные коды из букв С, О, Л, О, В, Е, Й. Буква Й может использоваться в коде не более одного раза, при этом она не может стоять на первом месте, на последнем месте и рядом с буквой Е. Все остальные буквы могут встречаться произвольное количество раз или не встречаться совсем. Сколько различных кодов может составить Сергей?

Решение

from itertools import *

m=[]

for c in set(map(''.join,product('СОЛОВЕЙ',repeat=6))):

if c.count('Й')<2 and c[0]!='Й'!= c[-1] and 'ЕЙ' not in c and 'ЙЕ' not in c:

m.append(c)

print(len(m))

Ответ: 23625

32) (№ 2784) Разведчик кодирует символы текста четырьмя стрелками. Каждая стрелка может иметь четыре положения (направления): ↑→↓←. Для первой стрелки запрещено положение вверх: ↑. Вторая и третья стрелки не могут находиться в одинаковом положении (направлении). Сколько всего различных символов текста может закодировать разведчик?

Решение

from itertools import *

m=[]

for c in set(map(''.join,product('ВПНЛ',repeat=4))):

if c[0] !='В' and c[1]!=c[2]: m.append(c)

print(len(m))

Ответ: 144

33) (№ 1923) Артур составляет 5-буквенные коды из букв Е, С, А, У, Л. Каждую букву нужно использовать ровно один раз, при этом нельзя ставить рядом две гласные. Сколько различных кодов может составить Артур?

Решение

from itertools import *

m=[]

for c in map(''.join,permutations('ЕСАУЛ')):

if 'АА' not in c.replace('Е','А').replace('У','А'): m.append(c)

print(len(m))

Ответ: 12

34) (№ 1900) Сколько существует чисел, восьмеричная запись которых содержит 8 цифр, причём все цифры различны и никакие две чётные и две нечётные цифры не стоят рядом.

Решение

from itertools import *

m=[]

for c in map(''.join,permutations('01234567')):

if c[0]!='0':

fl=1

for i in range(7): fl*=sum(map(int,c[i:i+2]))%2

if fl: m.append(c)

print(len(m))

Ответ: 1008

35) (№ 1899) Сколько существует чисел, восьмеричная запись которых содержит 7 цифр, причём все цифры различны и никакие две чётные и две нечётные цифры не стоят рядом.

Решение

from itertools import *

m=[]

for c in map(''.join,permutations('01234567',7)):

if c[0]!='0':

fl=1

for i in range(6): fl*=sum(map(int,c[i:i+2]))%2

if fl: m.append(c)

print(len(m))

Ответ: 1008

36) (№ 209) Игорь составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Игорь использует 4-буквенные слова, в которых есть только буквы A, B, C, D, X, причём буква X появляется ровно 1 раз. Каждая из других допустимых букв может встречаться в кодовом слове любое количество раз или не встречаться совсем. Сколько различных кодовых слов может использовать Игорь?

Решение

from itertools import *

m=[]

for c in map(''.join,product('ABCDX',repeat=4)):

if c.count('X')==1: m.append(c)

print(len(m))

Ответ: 256

37) (№ 5745 М.Ишимов) Определите количество чисел, восьмеричная запись которых содержит ровно 5 цифр, среди них две различные цифры, сумма которых является простым числом.

Решение

p=[2,3,5,7,11,13,17,19]

k=0

for x in range(8**4,8**5):

a=list(map(int,oct(x)[2:]))

fl=0

for i in range(4):

for j in range(i+1,5):

if (a[i]+a[j]) in p and a[i]!=a[j]: k+=1;fl=1;break

if fl:break

print(k)

Ответ: 27170

38) (№ 5749) (М. Байрамгулов) Миша составляет 5-буквенные слова из букв слова КОМПЬЮТЕР так, что в них можно переставить буквы и получить палиндром. Сколько различных слов может составить Миша?

Решение

from itertools import *

b=[]

for s in product('КОМПЬЮТЕР',repeat=5):

k=0

for c in set(s): k+=s.count(c)%2

if k==1:b.append(s)

print(len(b))

Ответ: 8649

39) (№ 5003 ) Вася составляет слова из букв слова ВЕРЕТЕНО. Код должен состоять из 8 букв, и каждая буква в нём должна встречаться столько же раз, сколько в заданном слове. Кроме того, в коде не должны стоять рядом две гласные и две согласные буквы. Сколько различных слов может составить Вася?

Решение

from itertools import *

b=[]

g,n='ЕО','ВРТН'

for s in set(map(''.join, permutations('ВЕРЕТЕНО'))):

for c in g: s=s.replace(c,'*')

for c in n: s=s.replace(c,'+')

if ('**' not in s) and ('++' not in s): b.append(s)

print(len(b))

Ответ: 192

40) (№ 5128 П.Волгин) Сколько существует натуральных чисел, шестнадцатеричная запись которых содержит 6 знаков, не начинается с единицы и заканчивается на AB?

Решение

Вариант 1 (программный)

Идея решения. Так как в конце шестнадцатеричного числа стоят две цифры "ab", то будет достаточно рассмотреть только изменяемую часть числа (4 первых цифры).

b=[]

for x in range(16**3,16**4):

x16=hex(x)[2:]

if x16[0]!='1': b.append(x)

print(len(b))

Вариант 2 (ручной)

Рассмотрим возможные комбинации цифр в числе.

14 16 16 16 1 1 = 14*16*16*16*1*1 =57344

Ответ: 57344