Тема: Кодирование данных, комбинаторика, системы счисления.
Что нужно знать:
· русский алфавит
· принципы работы с числами, записанными в позиционных системах счисления
· если слово состоит из L букв, причем есть n1 вариантов выбора первой буквы, n2 вариантов выбора второй буквы и т.д., то число возможных слов вычисляется как произведение
N = n1 · n2 · … · nL
· если слово состоит из L букв, причем каждая буква может быть выбрана n способами, то число возможных слов вычисляется как N = nL
Пример задания:
Р-10. Маша составляет шестибуквенные слова перестановкой букв слова КАПКАН. При этом она избегает слов с двумя подряд одинаковыми буквами. Сколько различных кодов может составить Маша?
Решение:
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.
Ещё пример задания:
Р-09. Маша составляет 5-буквенные коды из букв В, У, А, Л, Ь. Каждую букву нужно использовать ровно 1 раз, при этом код буква Ь не может стоять на первом месте и перед гласной. Сколько различных кодов может составить Маша?
Решение:
1) проще всего сначала найти общее количество возможных слов, а затем вычесть из него количество «запрещённых» слов – тех, которые начинаются на букву Ь или содержат комбинации ЬУ и ЬА
2) сначала найдём общее количество слов, не накладывая никаких ограничений; при этом есть 5 способов выбрать первую букву, 4 способа выбрать вторую и т.д., так что общее число вариантов равно 5! = 5 × 4 × 3 × 2 × 1 = 120
3) первой буквой не может быть Ь, это исключает 1 × 4 × 3 × 2 × 1 = 24 варианта
4) теперь определим, сколько слов содержит запрещённую комбинацию символов ЬУ; эта комбинация может располагаться на одной из 4-х позиций:
ЬУ***, *ЬУ**, **ЬУ*, ***ЬУ
первый случай уже исключён (слово не может начинаться с буквы Ь), для каждого из остальных случаев количество вариантов распределения остальных букв равно 3 × 2 × 1 = 6 варианта, то есть запрет сочетания ЬУ исключает 3 × 3 × 2 × 1 = 18 кодов
5) аналогично запрет сочетания ЬА исключает ещё 18 кодов
6) таким образом, из 120 слов запрещёнными являются 24 варианта с первой буквой Ь, 18 варианта, содержащие ЬУ в середине слова, и 18 вариантов, содержащие ЬА в середине слова
7) остаётся 120 – 24 – 18 – 18 = 60 кодов
8) Ответ: 60.
Ещё пример задания:
Р-08. Вася составляет 4-буквенные коды из букв У, Л, Е, Й. Каждую букву нужно использовать ровно 1 раз, при этом код не может начинаться с буквы Й и не может содержать сочетания ЕУ. Сколько различных кодов может составить Вася?
Решение:
1) проще всего сначала найти общее количество возможных слов, а затем вычесть из него количество слов, в которых есть сочетание ЕУ
2) первой буквой не может быть Й, поэтому осталось только 3 возможных первых буквы
3) предположим, что первую букву выбрали, тогда вторую выбираем из оставшихся трёх
4) при выборе третьей буквы у нас только 2 варианта, а последняя буква – та, которая осталась последней невыбранной:
5) в итоге общее количество возможных слов равно 3 × 3 × 2 × 1 = 18
6) теперь определим, сколько слов содержат сочетание ЕУ; нужно рассмотреть все возможные позиции, где может стоять пара ЕУ
7) пусть слово начинается с ЕУ, тогда следующую букву можно выбрать двумя способами, а последнюю – только одним, так что количество вариантов равно 2:
| 1(Е) | 1(У) |
8) пусть пара ЕУ – это вторая и третья буквы; тогда на первом месте может стоять только буква Л (но не Й), а на последнем – Й, получаем еще один вариант:
| 1(Л) | 1(Е) | 1(У) | 1(Й) |
9) сдвиг пары ЕУ в конец слова даёт ещё одну комбинацию
| 1(Л) | 1(Й) | 1(Е) | 1(У) |
10) таким образом, из 18 слов четыре (2 + 1 + 1) содержат ЕУ
11) Ответ: 14.
Ещё пример задания:
Р-07. Вася составляет 3-буквенные слова, в которых есть только буквы В, Е, С, Н, А, причём буква А используется в каждом слове хотя бы 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?
Решение (способ 1):
1) буква А может стоять на одном из трёх мест: А**, *А*, **А, где * обозначает любой из пяти символов
2) в каждом случае в остальных двух позициях может быть любая из пяти букв
3) для шаблона А** получаем (перемножая количество вариантов для каждой позиции)
1 · 5 · 5 = 25 слов
4) для шаблона *А* тоже получим 25 слов, но нужно учесть, что все слова, в который первая буква А мы уже подсчитали, поэтому считаем только слова, где на первом место стоит какая-то другая буква (В, Е, С или Н)
5) отсюда находим, что шаблон *А* добавляет 4 · 1 · 5 = 20 новых слов
6) рассматривая шаблон **А, не учитываем уже подсчитанные слова, в которых буква А есть на первом или втором местах, количество новых слов – 4 · 4 · 1 = 16
7) всего получается 25 + 20 + 16 = 61 слово
8) Ответ: 61.
Решение (способ 2):
1) количество слов с буквой А можно вычислить как разность между количеством всех возможных слов и количеством слов, в которых нет буквы А
2) количество всех слов 5 · 5 · 5 = 53 = 125 (на любой из 3-х позиций может стоять любая из 5 букв)
3) количество слов, в которых нет буквы А равно 4 · 4 · 4 = 43 = 64 (на любой из 3-х позиций может стоять любая из 4 букв, кроме А)
4) получается 125 – 64 = 61 слово, в котором есть буква А (она или несколько)
5) Ответ: 61.
Ещё пример задания:
Р-06. Вася составляет 5-буквенные слова, в которых есть только буквы С, Л, О, Н, причём буква С используется в каждом слове ровно 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?
Решение:
1) буква С может стоять на одном из пяти мест: С****, *С***, **С**, ***С* и ****С, где * обозначает любой из оставшихся трёх символов
2) в каждом случае в остальных четырёх позициях может быть любая из трёх букв Л, О, Н, поэтому при заданном расположении буквы С имеем 34 = 81 вариант
3) всего вариантов 5 · 81 = 405.
4) Ответ: 405.
Ещё пример задания:
Р-05. Сколько существует различных символьных последовательностей длины 5 в четырёхбуквенном алфавите {A, C, G, T}, которые содержат ровно две буквы A?
Решение (вариант 1, перебор):
1) рассмотрим различные варианты слов из 5 букв, которые содержат две буквы А и начинаются с А:
АА*** А*А** А**А* А***А
Здесь звёздочка обозначает любой символ из набора {C, G, T}, то есть один из трёх символов.
2) итак, в каждом шаблоне есть 3 позиции, каждую из которых можно заполнить тремя способами, поэтому общее число комбинаций (для каждого шаблона!) равно 33 = 27
3) всего 4 шаблона, они дают 4 · 27 = 108 комбинаций
4) теперь рассматриваем шаблоны, где первая по счёту буква А стоит на второй позиции, их всего три:
*АА** *А*А* *А**А
они дают 3 · 27 = 81 комбинацию
5) два шаблона, где первая по счёту буква А стоит на третьей позиции:
**АА* **А*А
они дают 2 · 27 = 54 комбинации
6) и один шаблон, где сочетание АА стоит в конце
***АА
они дают 27 комбинаций
7) всего получаем (4 + 3 + 2 + 1) · 27 = 270 комбинаций
8) ответ: 270.
Решение (вариант 2, использование формул комбинаторики):
1) в последовательности из 5 символов нужно использовать ровно две буквы А и три символа, не совпадающих с А, которые обозначим звездочкой
2) сначала найдём количество перестановок из двух букв А и трёх звёздочек
3) используем формулу для вычисления числа перестановок с повторениями; для двух разных символов она выглядит так:
Здесь 
– количество букв А, 
– количество звёздочек и восклицательный знак обозначает факториал натурального числа, то есть произведение всех натуральных чисел от 1 до 
: 
4) в нашем случае 
и 
, так что получаем
5) теперь разберёмся со звёздочками: вместо каждой из них может стоять любой из трёх символов (кроме А), то есть на каждую из 10 перестановок мы имеем 33 = 27 вариантов распределения остальных символов на месте звёздочек
6) таким образом, получаем всего 10 · 27 = 270 вариантов.
7) ответ: 270.
Ещё пример задания:
Р-04. Сколько слов длины 5, начинающихся с гласной буквы, можно составить из букв Е, Г, Э? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.
Решение:
1) первая буква слова может быть выбрана двумя способами (Е или Э), остальные – тремя
2) общее число различных слов равно 2*3*3*3*3 = 162
3) ответ: 162.
Решение (через формулы, А.Н. Носкин):
1) Дано слово длиной 5 символов типа *****, где красная звездочка – гласная буква (Е или Э), а черная буква любая из трёх заданных.
2) Общая формула количества вариантов:
N = M L, где М – мощность алфавита, а L – длина кода.
3) Так как положение одной из букв строго регламентировано (знак умножения в зависимых событиях), то формула всех вариантов примет вид: N = M 1 L 1 ∙ M 2 L2,
4) Тогда M 1 = 2 (алфавит гласных букв), а L 1 = 1 (только 1 позиция в слове).
M 2 = 3 (алфавит всех букв), а L 2 = 4 (оставшиеся 4 позиции в слове).
5) В итоге получаем: N = 21 ∙ 34 = 2 ∙ 81 = 162.
6) ответ: 162.
Ещё пример задания:
Р-03. Все 4-буквенные слова, составленные из букв К, Л, Р, Т, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
КККК
КККЛ
КККР
КККТ
……
Запишите слово, которое стоит на 67-м месте от начала списка.
Решение:
1) самый простой вариант решения этой задачи – использование систем счисления; действительно, здесь расстановка слов в алфавитном порядке равносильна расстановке по возрастанию чисел, записанных в четверичной системе счисления (основание системы счисления равно количеству используемых букв)
2) выполним замену К®0, Л®1, Р®2, Т®3; поскольку нумерация слов начинается с единицы, а первое число КККК®0000 равно 0, под номером 67 будет стоять число 66, которое нужно перевести в четверичную систему: 66 = 10024
3) Выполнив обратную замену (цифр на буквы), получаем слово ЛККР.
4) Ответ: ЛККР.
Ещё пример задания:
Р-02. Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке.
Вот начало списка:
ААААА
ААААО
ААААУ
АААОА
……
Запишите слово, которое стоит на 240-м месте от начала списка.
Решение (1 способ, перебор с конца):
1) подсчитаем, сколько всего 5-буквенных слов можно составить из трех букв;
2) очевидно, что есть всего 3 однобуквенных слова (А, О, У); двух буквенных слов уже 3´3=9 (АА, АО, АУ, ОА, ОО, ОУ, УА, УО и УУ)
3) аналогично можно показать, что есть всего 35 = 243 слова из 5 букв
4) очевидно, что последнее, 243-е слово – это УУУУУ
5) далее идём назад: предпоследнее слово УУУУО (242-е), затем идет УУУУА (241-е) и, наконец, УУУОУ (240-е)
6) Ответ: УУУОУ.
| Возможные ловушки и проблемы: · хорошо, что требовалось найти слово, которое стоит близко к концу списка; если бы было нужно, скажем, 123-е слово, работы было бы значительно больше |
Решение (2 способ, троичная система, идея М. Густокашина):
1) по условию задачи важно только то, что используется набор из трех разных символов, для которых задан порядок (алфавитный); поэтому для вычислений можно использовать три любые символа, например, цифры 0, 1 и 2 (для них порядок очевиден – по возрастанию)
2) выпишем начало списка, заменив буквы на цифры:
1. 00000
2. 00001
3. 00002
4. 00010
……
3) это напоминает (в самом деле, так оно и есть!) числа, записанные в троичной системе счисления в порядке возрастания: на первом месте стоит число 0, на втором – 1 и т.д.
4) тогда легко понять, что 240-м месте стоит число 239, записанное в троичной системе счисления
5) переведем 239 в троичную систему: 239 = 222123
6) заменяем обратно цифры на буквы: 22212 ® УУУОУ
7) Ответ: УУУОУ.
| Возможные ловушки и проблемы: · нужно помнить, что нумерация в задаче начинается с 1, а числа в троичной системе – с нуля, поэтому для получения 240-го элемента списка нужно переводить в троичную систему число 240-1 = 239. |
Решение (3 способ, закономерности в чередовании букв, И.Б. Курбанова):
1) подсчитаем, сколько всего 5-буквенных слов можно составить из трех букв:
| А | А | А | А | А | |
| А | А | А | А | О | |
| А | А | А | А | У | |
| А | А | А | О | А | |
| … | … | … | … | … | … |
| ... | |||||
| … | |||||
| У | У | У | О | У | |
| У | У | У | У | А | |
| У | У | У | У | О | |
| У | У | У | У | У |
35 = 243 слова; 240-ое место – четвертое с конца;
2) так как слова стоят в алфавитном порядке, то первая треть (81 шт) начинаются с «А», вторая треть (тоже 81) – с «О», а последняя треть – с «У», то есть первая буква меняется через 81 слово
3) аналогично:
• 2-я буква меняется через 81/3 = 27 слов;
• 3-я буква – через 27/3 = 9 слов;
• 4-я буква – через 9/3 = 3 слова и
• 5-я буква меняется в каждой строке.
4) из этой закономерности ясно, что
· на первой позиции в искомом слове будет буква «У» (последние 81 букв);
· на второй – тоже буква «У» (последние 27 букв);
· на третьей – тоже буква «У» (последние 9 букв);
· на четвертой – буква «О» (т.к. последние три буквы «У», а перед ними 3 буквы «О»)%
· на пятой – буква «У» (т.к. последние 3 буквы чередуются «А», «О», «У», а перед ними такая же последовательность).
5) Ответ: УУУОУ.
Еще пример задания (автор – В.В. Путилов):
Р-01. Все 5-буквенные слова, составленные из 5 букв А, К, Л, О, Ш, записаны в алфавитном порядке.
Вот начало списка:
ААААА
ААААК
ААААЛ
ААААО
ААААШ
АААКА
……
На каком месте от начала списка стоит слово ШКОЛА?
Решение:
1) по аналогии с предыдущим решением будем использовать пятеричную систему счисления с заменой А ® 0, К ® 1, Л ® 2, О ® 3 и Ш ® 4
2) слово ШКОЛА запишется в новом коде так: 413205
3) переводим это число в десятичную систему:
413205 = 4×54 + 1×53 + 3×52 + 2×51 = 2710
4) поскольку нумерация элементов списка начинается с 1, а числа в пятеричной системе – с нуля, к полученному результату нужно прибавить 1, тогда…
5) Ответ: 2711.
| Возможные ловушки и проблемы: · нужно помнить, что список в задании начинается с 1, а числа в троичной системе – с нуля, поэтому для получения N-ой по счёту цепочки нужно переводить в троичную систему число N-1. |
Еще пример задания:
Р-00. Все 5-буквенные слова, составленные из букв А, О, У, записаны в обратном алфавитном порядке. Вот начало списка:
УУУУУ
УУУУО
УУУУА
УУУОУ
……
Запишите слово, которое стоит на 240-м месте от начала списка.
Решение (2 способ, троичная система, идея М. Густокашина):
1) по условию задачи важно только то, что используется набор из трех разных символов, для которых задан порядок (алфавитный); поэтому для вычислений можно использовать три любые символа, например, цифры 0, 1 и 2 (для них порядок очевиден – по возрастанию)
2) выпишем начало списка, заменив буквы на цифры так, чтобы порядок символов был обратный алфавитный (У → 0, О → 1, А → 2):
1. 00000
2. 00001
3. 00002
4. 00010
……
3) это напоминает (в самом деле, так оно и есть!) числа, записанные в троичной системе счисления в порядке возрастания: на первом месте стоит число 0, на втором – 1 и т.д.
4) тогда легко понять, что 240-м месте стоит число 239, записанное в троичной системе счисления
5) переведем 239 в троичную систему: 239 = 222123
6) заменяем обратно цифры на буквы, учитывая обратный алфавитный порядок (0 → У, 1 → О, 2 → А): 22212 ® АААОА
7) Ответ: АААОА.
Задачи для тренировки [1]:
1) Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка:
ААААА
ААААО
ААААУ
АААОА
……
Запишите слово, которое стоит на 101-м месте от начала списка.
2) Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка:
ААААА
ААААО
ААААУ
АААОА
……
Запишите слово, которое стоит на 125-м месте от начала списка.
3) Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка:
ААААА
ААААО
ААААУ
АААОА
……
Запишите слово, которое стоит на 170-м месте от начала списка.
4) Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка:
ААААА
ААААО
ААААУ
АААОА
……
Запишите слово, которое стоит на 210-м месте от начала списка.
5) Все 5-буквенные слова, составленные из букв А, К, Р, У, записаны в алфавитном порядке. Вот начало списка:
ААААА
ААААК
ААААР
ААААУ
АААКА
……
Запишите слово, которое стоит на 150-м месте от начала списка.
6) Все 5-буквенные слова, составленные из букв А, К, Р, У, записаны в алфавитном порядке. Вот начало списка:
ААААА
ААААК
ААААР
ААААУ
АААКА
……
Запишите слово, которое стоит на 250-м месте от начала списка.
7) Все 5-буквенные слова, составленные из букв А, К, Р, У, записаны в алфавитном порядке. Вот начало списка:
ААААА
ААААК
ААААР
ААААУ
АААКА
……
Запишите слово, которое стоит на 350-м месте от начала списка.
8) Все 5-буквенные слова, составленные из букв А, К, Р, У, записаны в алфавитном порядке. Вот начало списка:
ААААА
ААААК
ААААР
ААААУ
АААКА
……
Запишите слово, которое стоит на 450-м месте от начала списка.
9) Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка:
ААААА
ААААО
ААААУ
АААОА
……
Укажите номер первого слова, которое начинается с буквы У.
10) Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка:
ААААА
ААААО
ААААУ
АААОА
……
Укажите номер слова ОАОАО.
11) Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка:
ААААА
ААААО
ААААУ
АААОА
……
Укажите номер слова УАУАУ.
12) Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка:
ААААА
ААААО
ААААУ
АААОА
……
Укажите номер первого слова, которое начинается с буквы О.
13) Все 5-буквенные слова, составленные из букв А, К, Р, У, записаны в алфавитном порядке. Вот начало списка:
ААААА
ААААК
ААААР
ААААУ
АААКА
……
Укажите номер первого слова, которое начинается с буквы У.
14) Все 5-буквенные слова, составленные из букв А, К, Р, У, записаны в алфавитном порядке. Вот начало списка:
ААААА
ААААК
ААААР
ААААУ
АААКА
……
Укажите номер первого слова, которое начинается с буквы К.
15) Все 5-буквенные слова, составленные из букв А, К, Р, У, записаны в алфавитном порядке. Вот начало списка:
ААААА
ААААК
ААААР
ААААУ
АААКА
……
Укажите номер слова РУКАА.
16) Все 5-буквенные слова, составленные из букв А, К, Р, У, записаны в алфавитном порядке. Вот начало списка:
ААААА
ААААК
ААААР
ААААУ
АААКА
……
Укажите номер слова УКАРА.
17) Все 5-буквенные слова, составленные из букв К, О, Р, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
ККККК
ККККО
ККККР
КККОК
……
Запишите слово, которое стоит под номером 238.
18) Все 5-буквенные слова, составленные из букв И, О, У, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
ИИИИИ
ИИИИО
ИИИИУ
ИИИОИ
……
Запишите слово, которое стоит под номером 240.
19) Все 4-буквенные слова, составленные из букв М, А, Р, Т, записаны в алфавитном порядке. Вот начало списка:
АААА
АААМ
АААР
АААТ
……
Запишите слово, которое стоит на 250 -м месте от начала списка.
20) Все 5-буквенные слова, составленные из букв Р, О, К, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
ККККК
ККККО
ККККР
КККОК
……
Запишите слово, которое стоит под номером 182.
21) Сколько слов длины 4, начинающихся с согласной буквы, можно составить из букв Л, Е, Т, О? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.
22) Сколько существует различных символьных последовательностей длины 5 в трёхбуквенном алфавите {К, О, T}, которые содержат ровно две буквы О?
23) Сколько существует различных символьных последовательностей длины 6 в трёхбуквенном алфавите {К, О, T}, которые содержат ровно две буквы К?
24) Сколько существует различных символьных последовательностей длины 6 в четырёхбуквенном алфавите {М, А, Р, T}, которые содержат ровно две буквы Р?
25) Сколько слов длины 6, начинающихся с согласной буквы, можно составить из букв Т, О, К? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.
26) Сколько слов длины 5, начинающихся с согласной буквы и заканчивающихся гласной буквой, можно составить из букв К, У, М, А? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.
27) Вася составляет 6-буквенные слова, в которых есть только буквы К, Р, О, Т, причём буква О используется в каждом слове ровно 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?
28) Вася составляет 5-буквенные слова, в которых есть только буквы К, Р, А, Н, Т, причём буква К используется в каждом слове ровно 2 раза. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?
29) Вася составляет 6-буквенные слова, в которых есть только буквы К, А, Н, Т, причём буква К используется в каждом слове ровно 2 раза. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?
30) Сколько слов длины 6, начинающихся и заканчивающихся согласной буквой, можно составить из букв Г, О, Д? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.
31) Сколько слов длины 4, начинающихся с согласной буквы и заканчивающихся гласной буквой, можно составить из букв М, Е, Т, Р, О? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.
32) (Е.В. Хламов) Сколько существует различных символьных последовательностей длины 3 в четырёхбуквенном алфавите {A,B,C,D}, если известно, что одним из соседей A обязательно является D, а буквы B и C никогда не соседствуют друг с другом?
33) (А.Н. Носкин) Все 5-буквенные слова, составленные из букв П, О, Р, Т, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
ООООО
ООООП
ООООР
ООООТ
ОООПО
……
Какое количество слов находятся между словами ТОПОР и РОПОТ (включая эти слова)?
34) Все 5-буквенные слова, составленные из букв А, З, Н, С, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
ААААА
ААААЗ
ААААН
ААААС
АААЗА
……
Какое количество слов находятся между словами САЗАН и ЗАНАС (включая эти слова)?
35) Все 5-буквенные слова, составленные из букв Д, К, М, О, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
ДДДДД
ДДДДК
ДДДДМ
ДДДДО
ДДДКД
……
Какое количество слов находятся между словами ДОМОК и КОМОД (включая эти слова)?
36) Все 4-буквенные слова, составленные из букв М, А, Р, Т, записаны в алфавитном порядке. Вот начало списка:
АААА
АААМ
АААР
АААТ
……
Какое количество слов находятся между словами МАРТ и РАМТ (включая эти слова)?
37) Все 5-буквенные слова, составленные из букв А, К, Р, У, записаны в алфавитном порядке. Вот начало списка:
ААААА
ААААК
ААААР
ААААУ
АААКА
……
Какое количество слов находятся между словами РУКАА и УКАРА (включая эти слова)?
38) Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка:
ААААА
ААААО
ААААУ
АААОА
……
Какое количество слов находятся между словами УАУАУ и ОУОУА (включая эти слова)?
39) Игорь составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Игорь использует 4-буквенные слова, в которых есть только буквы A, B, C, D, X, причём буква X появляется ровно 1 раз. Каждая из других допустимых букв может встречаться в кодовом слове любое количество раз или не встречаться совсем. Сколько различных кодовых слов может использовать Игорь?
40) Алексей составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Алексей использует 5-буквенные слова, в которых есть только буквы A, B, C, X, причём буква X может появиться на последнем месте или не появиться вовсе. Сколько различных кодовых слов может использовать Алексей?
41) Вася составляет 3-буквенные слова, в которых есть только буквы К, Р, А, Н, причём буква А используется в каждом слове хотя бы 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?
42) Вася составляет 4-буквенные слова, в которых есть только буквы Л, Е, Т, О, причём буква Е используется в каждом слове хотя бы 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?
43) Вася составляет 5-буквенные слова, в которых есть только буквы Л, Е, Т, О, причём буква Е используется в каждом слове хотя бы 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?
44) Вася составляет 4-буквенные слова, в которых есть только буквы К, Л, О, У, Н, причём буква У используется в каждом слове хотя бы 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?
45) Вася составляет 5-буквенные слова, в которых есть только буквы К, Л, О, У, Н, причём буква У используется в каждом слове хотя бы 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?
46) Вася составляет 3-буквенные слова, в которых есть только буквы Б, А, Л, К, О, Н, причём буква Б используется в каждом слове хотя бы 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?
47) Вася составляет 4-буквенные слова, в которых есть только буквы Б, А, Л, К, О, Н, причём буква Б используется в каждом слове хотя бы 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?
48) Вася составляет 5-буквенные слова, в которых есть только буквы Б, А, Л, К, О, Н, причём буква Б используется в каждом слове хотя бы 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?
49) Вася составляет 3-буквенные слова, в которых есть только буквы К, А, Т, Е, Р, причём буква Р используется в каждом слове хотя бы 2 раза. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?
50) Вася составляет 4-буквенные слова, в которых есть только буквы К, А, Т, Е, Р, причём буква Р используется в каждом слове хотя бы 2 раза. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?
51) Вася составляет 5-буквенные слова, в которых есть только буквы К, А, Т, Е, Р, причём буква Р используется в каждом слове хотя бы 2 раза. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?
52) (М.В. Кузнецова) Вася составляет 4-буквенные слова, в которых есть только буквы К, О, М, А, Р, причём буква А используется в них не более 3-х раз (или не используется совсем). Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?
53) (М.В. Кузнецова) Вася составляет 5-буквенные слова, в которых есть только буквы М, У, Х, А, причём буква У может использоваться не более 3-х раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?
54) (М.В. Кузнецова) Вася составляет 5-буквенные слова, в которых есть только буквы С, Л, О, Н, причём в каждом слове используется буква О, но не более 3-х раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последо