Содержание:
Решение 8 задания
Уровень сложности — базовый,
Требуется использование специализированного программного обеспечения — нет,
Максимальный балл — 1,
Примерное время выполнения — 4 минуты.
Проверяемые элементы содержания: Знание о методах измерения количества информации
Задание демонстрационного варианта 2021 года ФИПИ
Сколько вариантов шифра или кодовых слов
Шифр кодового замка представляет собой последовательность из пяти символов, каждый из которых является цифрой от 1 до 6.
Сколько различных вариантов шифра можно задать, если известно, что цифра 1 должна встречаться в коде ровно 1 раз, а каждая из других допустимых цифр может встречаться в шифре любое количество раз или не встречаться совсем?
Ответ: 3125
- Формула нахождения количества различных сообщений:
- Итак, что у нас дано из этой формулы:
- Длина сообщения (L) = 5 символов
- Мощность алфавита (N) = 6 (цифры от 1 до 6).
- Но так как цифра 1 встречается по условию ровно один раз, а остальные 5 цифр — любое количество раз, то будем считать, что N = 5 (цифры от 2 до 6, исключая 1).
Найдем количество вариантов для одного случая, а именно: когда единица стоит на первом месте, а остальные 5 цифр размещаем на четыре позиции:
1 5 5 5 5 - 1 * Q = 54 = 625
Найдем количество вариантов двумя разными способами (можно выбрать любой из них):
✎ 1 способ. Найдем количество вариантов методом перебора:
1 5 5 5 5 -1 * Q=54
= 625 5 1 5 5 5 -1 * Q=54
= 625 5 5 1 5 5 -1 * Q=54
= 625 5 5 5 1 5 -1 * Q=54
= 625 5 5 5 5 1 -1 * Q=54
= 625
✎ 2 способ. Найдем количество вариантов при помощи формулы комбинаторики:
\[ C{\binom{4}{5}}= \frac{5!}{4!(5-4)!} = 5 \]
625 * 5 = 3125
Шифр кодового замка представляет собой последовательность из пяти символов, каждый из которых является либо буквой (A или B) или цифрой (1, 2 или 3).
Сколько различных вариантов шифра можно задать, если известно, что в коде присутствует ровно одна буква, а все другие символы являются цифрами?
Ответ: 810
- Формула нахождения количества различных сообщений:
- Посчитаем количество возможных шифров для одного из вариантов (например, когда буквы находятся на первой позиции). Так как цифры (1, 2, 3) могут занимать 4 позиции из пяти, а две буквы (А и В) одну из позиций, значит:
Q = 2 * 34 = 162
AB 123 123 123 123 = 162
"2" означает одна из двух букв: А или B, "3" - одна из трех цифр: 2 3 3 3 3 -> Q = 2 * 34 = 162 3 2 3 3 3 -> Q = 2 * 34 = 162 3 3 2 3 3 -> Q = 2 * 34 = 162 3 3 3 2 3 -> Q = 2 * 34 = 162 3 3 3 3 2 -> Q = 2 * 34 = 162
5 * 162 = 810
Олег составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Олег использует 4-буквенные слова, в которых есть только буквы A, Б, В, Г, Д и Е, причём буква Г появляется ровно 1 раз и только на первом или последнем месте. Каждая из других допустимых букв может встречаться в кодовом слове любое количество раз или не встречаться совсем.
Сколько различных кодовых слов может использовать Олег?
Ответ: 250
- Вспомним формулу получения количества возможных вариантов слов:
- где n1 — количество вариантов выбора первой буквы, n2 — количество вариантов выбора второй буквы и т.п.
- Рассмотрим варианты, когда буква Г встречается на первом или последнем месте:
N = n1 * n2 * n3 * … * nL = nL
Г ? ? ? = 1 * 5 * 5 * 5 = 53 = 125 ? ? ? Г = 5 * 5 * 5 * 1 = 53 = 125
125 + 125 = 250
Шифр кодового замка представляет собой последовательность из пяти символов, каждый из которых является одной из букв X, Y или Z.
Сколько различных вариантов шифра можно задать, если известно, что буква X должна встречаться в коде ровно 2 раза, а каждая из других допустимых букв может встречаться в шифре любое количество раз или не встречаться совсем?
Типовые задания для тренировки
Ответ: 80
- Формула нахождения количества различных сообщений:
- Итак, что у нас дано из этой формулы:
- Начальная мощность алфавита (N) = 3 (буквы X, Y, Z). Но так как буква X встречается ровно два раза, то мы ее рассмотрим отдельно, а остальные 2 буквы — встречаются любое количество раз, значит, будем считать, что:
N = 3 - 1 = 2 (Y и Z)
(L) = 5 - 2 = 3 символа (остальные два символа отведем на размещение X)
X X ? ? ? -> 12 * Q = 23 = 8
✎1 способ. Перебор всех вариантов:
X X ? ? ? - 12 * Q = 23 = 8 X ? X ? ? - 12 * Q = 23 = 8 X ? ? X ? - 12 * Q = 23 = 8 X ? ? ? X - 12 * Q = 23 = 8 ? X X ? ? - 12 * Q = 23 = 8 ? X ? X ? - 12 * Q = 23 = 8 ? X ? ? X - 12 * Q = 23 = 8 ? ? X X ? - 12 * Q = 23 = 8 ? ? X ? X - 12 * Q = 23 = 8 ? ? ? X X - 12 * Q = 23 = 8
✎ 2 способ. При помощи формулы поиска числа сочетаний:
\[ C{\binom{k}{n}}= \frac{n!}{k!(n-k)!} \]
Число сочетаний из n элементов по k элементов:
\[ C{\binom{2}{5}}= \frac{5!}{2!(5-2)!} = \frac{120}{12} = 10 \]
* Факториал числа: n! = 0 * 1 * 2 * 3 * .. * n
8 * 10 = 80
Сколько слов длины 5, начинающихся с согласной буквы и заканчивающихся гласной буквой, можно составить из букв ОСЕНЬ? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.
Типовые задания для тренировки
Ответ: 500
- Из букв слова ОСЕНЬ имеем 2 гласных буквы (О, Е) и 2 согласных буквы (С, Н). Буква мягкий знак «нейтральна».
- Подсчитаем количество букв на каждой из 5 позиций:
2 5 5 5 2 СН все все все ОЕ
N = n1 * n2 * n3 * … * nL = nL
N = 2 * 5 * 5 * 5 * 2 = 500
Вася составляет 4-буквенные слова, в которых есть только буквы Л, Е, Т, О, причём буква Е используется в каждом слове хотя бы 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем.
Сколько существует таких слов, которые может написать Вася?
Типовые задания для тренировки
Ответ: 175
-
✎ 1 способ:
- Количество вариантов различных слов вычислим по формуле:
- n1 — количество вариантов выбора первой буквы и т.п.
- Рассмотрим все варианты расположения буквы Е:
N = n1 * n2 * n3 * …
где
1. Е ? ? ? или 2. ? Е ? ? или 3. ? ? Е ? или 4. ? ? ? Е Где вопросительный знак означает любую букву из Л, Е, Т, О.
Е ? ? ? = 1 * 4 * 4 * 4 = 64 т.е. на первой позиции - только 1 буква - Е, на каждой последующей - одна из четырех букв Л, Е, Т, О.
? Е ? ? = 3 * 1 * 4 * 4 = 48
? ? Е ? = 3 * 3 * 1 * 4 = 36
? ? ? Е = 3 * 3 * 3 * 1 = 27
64 + 48 + 36 + 27 = 175
Результат: 175
✎ 2 способ:
- Так как по условию буква Е встретится хотя бы 1 раз, значит, можно утверждать, что не может быть такого, чтобы буква Е не встретилась бы ни одного раза.
- Таким образом, рассчитаем случай, когда буква Е встречается все 4 раза (т.е. все случаи) и отнимем от результата невозможный случай: когда буква Е не встретится ни одного раза:
1. Буква Е используется 4 раза (т.е. на всех позициях): 4 * 4 * 4 * 4 = 256 2. Буква Е не используется совсем (т.е. только 3 буквы): 3 * 3 * 3 * 3 = 81
256 - 81 = 175
Вася составляет 4-буквенные слова, в которых есть только буквы К, А, Т, Е, Р, причём буква Р используется в каждом слове хотя бы 2 раза. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем.
Сколько существует таких слов, которые может написать Вася?
Типовые задания для тренировки
Ответ: 113
- Количество возможных вариантов слов вычислим по формуле:
- где n1 — количество вариантов выбора первой буквы, n2 — количество вариантов выбора второй буквы и т.п.
- Сначала по формуле получим все варианты для всех пяти букв, включая букву Р:
N = n1 * n2 * n3 * … * nL = nL
5 * 5 * 5 * 5 = 54 = 625
4 * 4 * 4 * 4 = 44 = 256
р ? ? ? = 1 * 4 * 4 * 4 = 43 ? р ? ? = 4 * 1 * 4 * 4 = 43 ? ? р ? = 4 * 4 * 1 * 4 = 43 ? ? ? р = 4 * 4 * 4 * 1 = 43 Получим 43 * 4 = 256
625 - 256 - 256 = 113
Олег составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Олег использует 5-буквенные слова, в которых есть только буквы A, Б, В, и Г, причём буква Г появляется не более одного раза и только на последнем месте. Каждая из других допустимых букв может встречаться в кодовом слове любое количество раз или не встречаться совсем.
Сколько различных кодовых слов может использовать Олег?
Ответ: 324
- Вспомним формулу получения количества возможных вариантов слов:
- где n1 — количество вариантов выбора первой буквы,
- n2 — количество вариантов выбора второй буквы и т.п.
- Так как буква Г появляется не более одного раза и только на последнем месте, значит, она может либо появиться 1 раз на последнем месте, либо не появиться совсем.
- Рассмотрим варианты, когда буква Г встречается 1 раз на последнем месте и встречается 0 раз:
N = n1 * n2 * n3 * … * nL = nL
1 раз: ? ? ? ? Г = 3 * 3 * 3 * 3 * 1 = 34 = 81 0 раз: ? ? ? ? ? = 3 * 3 * 3 * 3 * 3 = 35 = 243
81 + 243 = 324
Вася составляет 4-буквенные слова, в которых есть только буквы К, О, М, А, Р, причём буква А используется в них не более 3-х раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, необязательно осмысленная.
Сколько существует таких слов, которые может написать Вася?
Типовые задачи для тренировки
Ответ: 624
- Вспомним формулу получения количества возможных вариантов слов:
- где n1 — количество вариантов выбора первой буквы,
- n2 — количество вариантов выбора второй буквы и т.п.
- Так как буква А по условию используется не более 3-х раз, это значит, что она используется либо 3 раза, либо 2 раза, либо 1 раз, либо не используется совсем. Рассмотрим все эти варианты отдельно.
- 1. Буква А используется 3 раза:
N = n1 * n2 * n3 * … * nL = nL
А А А _ -> 1 * 1 * 1 * 4 = 4 А А _ А -> 1 * 1 * 4 * А = 4 А _ А А -> 1 * 4 * 1 * 1 = 4 _ А А А -> 4 * 1 * 1 * 1 = 4
_
может быть любая из 4 букв: К О М Р. Значит, имеем:4 * 4 = 16 вариантов
А А _ _ -> 1 * 1 * 4 * 4 = 16 А _ А _ -> 1 * 4 * 1 * 4 = 16 А _ _ А -> 1 * 4 * 4 * 1 = 16 _ А А _ -> 4 * 1 * 1 * 4 = 16 _ А _ А -> 4 * 1 * 4 * 1 = 16 _ _ А А -> 4 * 4 * 1 * 1 = 16
_
может быть любая из 4 букв: К О М Р. Значит имеем:16 * 6 = 96 вариантов
А _ _ _ -> 1 * 4 * 4 * 4 = 64 _ А _ _ -> = 64 _ _ А _ -> = 64 _ _ _ А -> = 64
64 * 4 = 256 вариантов
_ _ _ _ -> 44 = 256
16 + 96 + 256 + 256 = 624
Сколько существует различных символьных последовательностей длины 3 в четырёхбуквенном алфавите {A,B,C,D}, если известно, что одним из соседей A обязательно является D, а буквы B и C никогда не соседствуют друг с другом?
Ответ: 29
- Вспомним формулу получения количества возможных вариантов слов:
- где n1 — количество вариантов выбора первой буквы,
- n2 — количество вариантов выбора второй буквы и т.п.
- Будем рассматривать варианты, расставляя каждую букву последовательно по алфавиту, начиная с первой буквы. При этом будем учитывать указанные ограничения для букв А, B и С:
N = n1 * n2 * n3 * … * nL = nL
Начинаем с A: A D 4ABCD = 1 * 1 * 4 = 4 Начинаем с B: B A D, B B 2BD, B D 4ABCD = 7 Начинаем с C: C A D, C C 2CD, C D 4ABCD = 7 Начинаем с D: D A 3BCD, D B 2BD, D C 2CD, D D 4ABCD = 11
4 + 7 + 7 + 11 = 29
Из букв С, Р, Е, Д, А составляются трехбуквенные комбинации по следующему правилу – в комбинации не может быть подряд идущих гласных и одинаковых букв.
Сколько всего комбинаций можно составить, используя это правило?
Ответ: 66
- Рассмотрим два варианта: когда слово начинается с гласной буквы, и когда оно начинается с согласной.
1. С гласной:
1.1 2 3 2 = 2 * 3 * 2 = 12 гл с с 1.2 2 3 2 = 2 * 3 * 2 = 12 гл с гл
2. С согласной:
2.1 3 2 2 = 3 * 2 * 2 = 12 с с с 2.2 3 2 3 = 3 * 2 * 3 = 18 с гл с 2.3 3 2 2 = 3 * 2 * 2 = 12 с с гл
12 + 12 + 12 + 18 + 12 = 66
Дано слово КОРАБЛИКИ. Таня решила составлять новые 5-буквенные слова из букв этого слова по следующим правилам:
1) слово начинается с гласной буквы;
2) гласные и согласные буквы в слове должны чередоваться;
3) буквы в слове не должны повторяться.
Сколько существует таких слов?
Типовые задачи для тренировки
Ответ: 72
- Учтем, что в слове КОРАБЛИКИ две буквы К и две И.
- Всего в слове 4 гласных, но поскольку две буквы И, то необходимо считать только 3 гласных.
- Всего в слове 5 согласных, однако две из них — буквы К, поэтому считать следует 4 согласных.
- Посчитаем количество согласных и гласных для каждой из 5 позиций слова, учитывая, что с каждой последующей буквой количество используемых гласных/согласных уменьшается. Под позициями приведем пример букв:
гл с гл с гл 3 4 2 3 1 оаи крбл оа крб и
3 * 4 * 2 * 3 * 1 = 72
Петя составляет шестибуквенные слова перестановкой букв слова АДЖИКА. При этом он избегает слов с двумя подряд одинаковыми буквами. Сколько всего различных слов может составить Петя?
Ответ: 240
- Посчитаем количество слов без двух подряд одинаковых букв. Будем считать относительно буквы А, которых две в заданном слове АДЖИКА. Буквы не могут повторяться, поэтому их кол-во в каждом варианте будет уменьшается:
А*А*** = 4*3*2*1 = 24 слова с данным расположением буквы А. А**А** = 4*3*2*1 = 24 А***А* = 4*3*2*1 А****А = ... *А*А** *А**А* *А***А **А*А* **А**А ***А*А
10 * 24 = 240
Маша составляет 7-буквенные коды из букв В, Е, Н, Т, И, Л, Ь. Каждую букву нужно использовать ровно 1 раз, при этом код буква Ь не может стоять на последнем месте и между гласными. Сколько различных кодов может составить Маша?
Ответ: 4080
7 6 5 4 3 2 1 - количество возможных вариантов букв на семи позициях ИТОГО: 7! = 5040 слов
6 5 4 3 2 1 Ь = 6! = 720
И Ь Е 4 3 2 1 = 24 варианта Так как буквы смещаются по всем позициям, то получим (4 И Ь Е 3 2 1, ...): 24 * 5 = 120 Е Ь И 4 3 2 1 = 24 варианта 24 * 5 = 120
5040 - 720 - 120 - 120 = 4080
Сколько существует n-значных чисел, записанных в m-ной системе счисления
Сколько существует восьмизначных чисел, записанных в восьмеричной системе счисления, в которых все цифры различны и рядом не могут стоять 2 чётные или 2 нечётные цифры?
Ответ: 1008
- Выпишем все четные и нечетные цифры, которые могут использоваться в 8-й с.с.:
четные: 0, 2, 4, 6 - итого 4 цифры нечетные: 1, 3, 5, 7 - итого 4 цифры
1) с четной цифры: 3 4 3 3 2 2 1 1 = 3*4*3*3*2*2*1*1 = 432 ч н ч н ч н ч н
2) с нечетной цифры: 4 4 3 3 2 2 1 1 = 4*4*3*3*2*2*1*1 = 556 н ч н ч н ч н ч
432 + 556 = 1008
Список в алфавитном порядке
Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Ниже приведено начало списка:
1. ААААА
2. ААААО
3. ААААУ
4. АААОА
…
Запишите слово, которое стоит под номером 242 от начала списка.
Ответ: УУУУО
- Данное задание лучше решать следующим образом. Подставим вместо букв цифры (А -> 0, О -> 1, У -> 2):
1. 00000 2. 00001 3. 00002 4. 00010 ...
остатки 241 | 3 | 1 80 | 3 | 2 26 | 3 | 2 8 | 3 | 2 2 | |
Все 4-буквенные слова, составленные из букв Д, Е, К, О, Р, записаны в алфавитном порядке и пронумерованы, начиная с 1.
Ниже приведено начало списка.
1. ДДДД 2. ДДДЕ 3. ДДДК 4. ДДДО 5. ДДДР 6. ДДЕД …
Под каким номером в списке идёт первое слово, которое начинается с буквы K?
Ответ: 251
- Подставим вместо букв цифры (Д -> 0, Е -> 1, К -> 2, О -> 3, Р -> 4):
1. 0000 2. 0001 3. 0002 4. 0003 5. 0004 6. 0010 ...
K -> 2 -> 2000
По формуле разложения числа по степеням основания: 20005 = 2 * 53 + 0 * 22 + 0 + 0 = 2 * 125 = 25010
Все 4-буквенные слова, составленные из букв П, Р, С, Т, записаны в алфавитном порядке.
Вот начало списка:
1. ПППП 2. ПППР 3. ПППС 4. ПППТ 5. ППРП ... ...
На каком месте в списке стоит первое слово, начинающееся с буквы Р?
Типовые задачи для тренировки
Ответ: 65
Все четырёхбуквенные слова, составленные из букв В, Е, Г, А, Н записаны в алфавитном порядке и пронумерованы, начиная с 1. Начало списка выглядит так:
1. АААА 2. АААВ 3. АААГ 4. АААЕ 5. АААН 6. ААВА …
Под каким номером в списке идёт первое слово, в котором нет буквы А?
Ответ: 157
- Пронумерованный список начинается со всех букв А. Представим, что А — 0, В — 1, Г — 2, Е — 3, Н — 4. Получим следующий список:
1. 0000 2. 0001 3. 0002 4. 0003 5. 0004 6. 0010
11115 = 1 * 53 + 1 * 52 + 1 * 51 + 1 * 50 = 156
156 + 1 = 157
Вероятность событий
За четверть Василий Пупкин получил 20 оценок. Сообщение о том, что он вчера получил четверку, несет 2 бита информации.
Сколько четверок получил Василий за четверть?
Ответ: 5
- Для решения данного задания необходимо вспомнить две формулы:
1. Формула Шеннона:
x - количество информации в сообщении о событии p - вероятность события
2. Формула вероятности случайного события:
m - число случаев, способствующих событию А n - общее число равновозможных случаев
2 = log2(1/p); => 1/p = 4; => p = 1/4
p = ?/20
1/4 = ?/20
? = 1/4 * 20 = 5