Разбор 8 задания ЕГЭ по информатике

Количество сообщений длиной L битов:

Т.е. количество сообщений длиной 2 бита, как в примере с нашими буквами, будет равно N = 2² = 4

Ответ: 4

Ответ: 17576

• Длина сообщения = 4. Мощность алфавита = 4. Но мешает условие: буква А встречается ровно два раза.
• В таких заданиях можно использовать способ перебора всевозможных вариантов:

два раза буква А, на остальных местах - одна из трех оставшихся букв:
А А 3 3     = 3 * 3 = 32 = 9
А 3 А 3     = 9
А 3 3 А     = 9 
3 А А 3     = 9
3 А 3 А     = 9
3 3 А А     = 9
  

• Получили 6 вариантов, каждый из которых равен 9.
• Проверим формулой числа сочетаний:

Число сочетаний из n элементов по k элементов:

\[ C{\binom{k}{n}}= \frac{n!}{k!(n-k)!} \]

• В задаче:

\[ C{\binom{2}{4}}= \frac{4!}{2!(4-2)!} = \frac{24}{2*2} = 6 \]

* Факториал числа n! = 1 * 2 * 3 *..* n
• Т.е. проверка прошла успешно, мы получили 6 вариантов.
• Осталось посчитать количество всех сообщений:

6 * 9 = 54

• Формула нахождения количества различных сообщений:
Q = N^L
• Итак, что у нас дано из этой формулы:
• Длина сообщения (L) = 5 символов
• Мощность алфавита (N) = 6 (цифры от 1 до 6).
• Но так как цифра 1 встречается по условию ровно один раз, а остальные 5 цифр — любое количество раз, то будем считать, что N = 5 (цифры от 2 до 6, исключая 1). Т.е. возьмем вариант, когда 1 стоит на первом месте, а остальные 5 цифр размещаем на 4 позиции:

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

• получили 5 вариантов;

✎ 2 способ. Найдем количество вариантов при помощи формулы комбинаторики:

\[ C{\binom{4}{5}}= \frac{5!}{4!(5-4)!} = 5 \]

• получили 5 вариантов;
• В итоге получим:

625 * 5 = 3125

Результат: 3125

• Формула нахождения количества различных сообщений:
Q = N^L
• Посчитаем количество возможных шифров для одного из вариантов (например, когда буквы находятся на первой позиции). Так как цифры (1, 2, 3) могут занимать 4 позиции из пяти, а две буквы (А и В) одну из позиций, значит:

Q = 2 * 34 = 162

• Имеем 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 вариантов с размещением букв А и B.
• Осталось умножить:

5 * 162 = 810

Результат: 810

• Вспомним формулу получения количества возможных вариантов слов:

N = n1 * n2 * n3 * … * nL = n^L

• где n1 — количество вариантов выбора первой буквы, n2 — количество вариантов выбора второй буквы и т.п.
• Рассмотрим варианты, когда буква Г встречается на первом или последнем месте:

Г ? ? ? = 1 * 5 * 5 * 5 = 53 = 125 
? ? ? Г = 5 * 5 * 5 * 1 = 53 = 125

• Вместо знаков ? может стоять одна из пяти букв (А, Б, В, Д, Е), т.к. буква Г там стоять не может
• Теперь суммируем количество найденных вариантов:

125 + 125 = 250

Результат: 250

• Формула нахождения количества различных сообщений:
Q = N^L
• Итак, что у нас дано из этой формулы:
• Начальная мощность алфавита (N) = 3 (буквы X, Y, Z). Но так как буква X встречается ровно два раза, то мы ее рассмотрим отдельно, а остальные 2 буквы — встречаются любое количество раз, значит, будем считать, что:

N = 3 - 1 = 2 (Y и Z)

• Исходя из предыдущего пункта, длина сообщения тоже сократится:

(L) = 5 - 2 = 3 символа (остальные два символа отведем на размещение X)

• Количество различных сообщений (вариантов шифра) = Q = ?
• Т.е. для одного варианта размещения (для одного варианта шифра) имеем:

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! = 1 * 2 * 3 * .. * n

• Количество вариантов найдено верно, т.к. результат обоих способов = 10. В итоге получаем:

8 * 10 = 80

Результат: 80

• Из букв слова ОСЕНЬ имеем 2 гласных буквы (О, Е) и 2 согласных буквы (С, Н). Буква мягкий знак «нейтральна».
• Подсчитаем количество букв на каждой из 5 позиций:

2   5   5   5   2
СН   все  все  все   ОЕ

• Вспомним формулу получения количества возможных вариантов слов:

N = n1 * n2 * n3 * … * nL = n^L

• где n1 — количество вариантов выбора первой буквы, n2 — количество вариантов выбора второй буквы и т.п.
• Т.е. количество вариантов равно произведению полученных чисел:

N = 2 * 5 * 5 * 5 * 2 = 500

Результат: 500

✎ 1 способ:
• Количество вариантов различных слов вычислим по формуле:

N = n1 * n2 * n3 * …
где

• n1 — количество вариантов выбора первой буквы и т.п.
• Рассмотрим все варианты расположения буквы Е:

1. Е ? ? ? или 
2. ? Е ? ? или 
3. ? ? Е ? или
4. ? ? ? Е 

Где вопросительный знак означает любую букву из Л, Е, Т, О.

• Подсчитаем по формуле количество слов для варианта 1:

Е ? ? ? = 1 * 4 * 4 * 4 = 64

т.е. на первой позиции - только 1 буква - Е, на каждой последующей - одна из четырех букв Л, Е, Т, О.

• Подсчитаем по формуле количество слов для варианта 2; учтем, что на первой позиции букву Е мы уже посчитали для первого варианта!:

? Е ? ? = 3 * 1 * 4 * 4 = 48

• Подсчитаем по формуле количество слов для варианта 3; учтем, что на первой и второй позициях букву Е мы уже посчитали в предыдущих вариантах!:

? ? Е ? = 3 * 3 * 1 * 4 = 36

• Подсчитаем по формуле количество слов для варианта 4; учтем, что на первой, второй и третьей позициях букву Е мы уже посчитали в предыдущих вариантах:

? ? ? Е = 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

• Вычтем из первого варианта невозможный вариант № 2:

256 - 81 = 175

Результат: 175

• Количество возможных вариантов слов вычислим по формуле:

N = n1 * n2 * n3 * … * nL = n^L

• где n1 — количество вариантов выбора первой буквы, n2 — количество вариантов выбора второй буквы и т.п.
• Сначала по формуле получим все варианты для всех пяти букв, включая букву Р:

5 * 5 * 5 * 5 = 54 = 625

• Из общего количества вариантов нам необходимо исключить те варианты, где Р не встречается вообще и Р встречается только 1 раз. Найдем их последовательно:
• 1. Буква Р не встречается совсем:

4 * 4 * 4 * 4 = 44 = 256

• 2. Буква Р встречается только один раз:

р ? ? ? = 1 * 4 * 4 * 4 = 43
? р ? ? = 4 * 1 * 4 * 4 = 43
? ? р ? = 4 * 4 * 1 * 4 = 43
? ? ? р = 4 * 4 * 4 * 1 = 43

Получим  43 * 4 = 256

• Теперь вычтем из общего количества найденные варианты (№ 1 и № 2):

625 - 256 - 256 = 113

Результат: 113

• Вспомним формулу получения количества возможных вариантов слов:

N = n1 * n2 * n3 * … * nL = n^L

• где n1 — количество вариантов выбора первой буквы,
• n2 — количество вариантов выбора второй буквы и т.п.
• Так как буква Г появляется не более одного раза и только на последнем месте, значит, она может либо появиться 1 раз на последнем месте, либо не появиться совсем.
• Рассмотрим варианты, когда буква Г встречается 1 раз на последнем месте и встречается 0 раз:

1 раз: ? ? ? ? Г = 3 * 3 * 3 * 3 * 1 = 34 = 81 
0 раз: ? ? ? ? ? = 3 * 3 * 3 * 3 * 3 = 35 = 243

• Вместо знаков ? может стоять одна из трех букв (А, Б, В), т.к. буква Г там стоять не может
• Теперь суммируем количество найденных вариантов:

81 + 243 = 324

Результат: 324

• Вспомним формулу получения количества возможных вариантов слов:

N = n1 * n2 * n3 * … * nL = n^L

• где n1 — количество вариантов выбора первой буквы,
• n2 — количество вариантов выбора второй буквы и т.п.
• Так как буква А по условию используется не более 3-х раз, это значит, что она используется либо 3 раза, либо 2 раза, либо 1 раз, либо не используется совсем. Рассмотрим все эти варианты отдельно.
• 1. Буква А используется 3 раза:

А А А _  -> 1 * 1 * 1 * 4 = 4
А А _ А  -> 1 * 1 * 4 * А = 4
А _ А А  -> 1 * 4 * 1 * 1 = 4
_ А А А  -> 4 * 1 * 1 * 1 = 4

• Итого получаем 4 варианта, в которых вместо символа _ может быть любая из 4 букв: К О М Р. Значит, имеем:

 4 * 4 = 16 вариантов

• 2. Буква А используется 2 раза:

А А _ _  -> 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

• Итого получаем 6 вариантов, в которых вместо символа _ может быть любая из 4 букв: К О М Р. Значит имеем:

 16 * 6 = 96 вариантов

• 3. Буква А используется 1 раз:

А _ _ _  -> 1 * 4 * 4 * 4 = 64
_ А _ _  -> = 64
_ _ А _  -> = 64
_ _ _ А  -> = 64

• Итого имеем:

64 * 4 = 256 вариантов

• Буква А используется 0 раз:

_ _ _ _ -> 44 = 256

• Суммируем результаты всех трех случаев:

16 + 96 + 256 + 256 = 624

Результат: 624

• Вспомним формулу получения количества возможных вариантов слов:

N = n1 * n2 * n3 * … * nL = n^L

• где n1 — количество вариантов выбора первой буквы,
• n2 — количество вариантов выбора второй буквы и т.п.
• Будем рассматривать варианты, расставляя каждую букву последовательно по алфавиту, начиная с первой буквы. При этом будем учитывать указанные ограничения для букв А, B и С:

Начинаем с 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

Результат: 29

• Рассмотрим два варианта: когда слово начинается с гласной буквы, и когда оно начинается с согласной.

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

Результат: 66

• Учтем, что в слове КОРАБЛИКИ две буквы К и две И.
• Всего в слове 4 гласных, но поскольку две буквы И, то необходимо считать только 3 гласных.
• Всего в слове 5 согласных, однако две из них — буквы К, поэтому считать следует 4 согласных.
• Посчитаем количество согласных и гласных для каждой из 5 позиций слова, учитывая, что с каждой последующей буквой количество используемых гласных/согласных уменьшается. Под позициями приведем пример букв:

гл   с   гл   с   гл  
3    4    2   3    1
оаи   крбл   оа   крб    и

• Количество слов вычисляется как произведение полученных чисел:

3 * 4 * 2 * 3 * 1 = 72

Результат: 72

• Посчитаем количество слов без двух подряд одинаковых букв. Будем считать относительно буквы А, которых две в заданном слове АДЖИКА. Буквы не могут повторяться, поэтому их кол-во в каждом варианте будет уменьшается:

А*А*** = 4*3*2*1 = 24 слова с данным расположением буквы А. 
А**А** = 4*3*2*1 = 24
А***А* = 4*3*2*1
А****А = ...
*А*А**
*А**А*
*А***А
**А*А*
**А**А
***А*А

• Получили 10 вариантов, и в каждом из них можно составить по 24 слова.
• Таким образом, получим общее количество слов:

10 * 24 = 240

Ответ: 240

• Выполним задание следующим образом: 1. посчитаем общее количество слов, не учитывая никакие ограничения. 2. Затем посчитаем случаи, которые необходимо исключить. 3. Вычтем из результата пункта 1 результат пункта 2.
• Общее количество независимо от ограничений (учтем, что буквы не должны повторяться):

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

Ответ: 4080

• Выпишем все четные и нечетные цифры, которые могут использоваться в 8-й с.с.:

четные: 0, 2, 4, 6 - итого 4 цифры
нечетные: 1, 3, 5, 7 - итого 4 цифры

• Рассмотрим два случая построения числа по заданию: 1) начиная с четной цифры и 2) начиная с нечетной цифры. Изобразим схематично числа, указывая сверху возможное количество цифр на разряд:

1) с четной цифры:
3  4  3  3  2  2  1  1 = 3*4*3*3*2*2*1*1 = 432
ч  н  ч  н  ч  н  ч  н

Самый старший разряд не может быть равен 0 (поэтому 3 цифры из 4 возможных), так как разряд просто потеряется, и число станет семизначным). Каждый последующий разряд включает на одну цифру меньше, так как по заданию цифры не могут повторяться.

2) с нечетной цифры:
4  4  3  3  2  2  1  1 = 4*4*3*3*2*2*1*1 = 556
н  ч  н  ч  н  ч  н  ч

Каждый последующий разряд включает на одну цифру меньше, так как по заданию цифры не могут повторяться.
• Сложим количество вариантов в обеих случаях:

432 + 556 = 1008

Ответ: 1008

• Данное задание лучше решать следующим образом. Подставим вместо букв цифры (А -> 0, О -> 1, У -> 2):

1. 00000
2. 00001
3. 00002
4. 00010
...

• Видим, что каждая последующее число получается путем прибавления в столбик единицы к предыдущему числу. В троичной системе счисления! Т.к. цифр всего три.
• Порядковый номер, написанный рядом с пунктом, всегда на единицу больше располагающейся рядом цифры в троичной системе счисления.
• Значит, пункту под номером 242 будет соответствовать число 241 в троичной системе счисления.
• Переведем 241 в 3-ю систему делением на 3:

        остатки
241 | 3 | 1
 80 | 3 | 2
 26 | 3 | 2
  8 | 3 | 2
  2 |   |

• Перепишем остатки снизу вверх: 22221, им соответствуют буквы УУУУО

Результат: УУУУО

• Подставим вместо букв цифры (Д -> 0, Е -> 1, К -> 2, О -> 3, Р -> 4):

1. 0000
2. 0001
3. 0002
4. 0003
5. 0004
6. 0010
...

• Видим, что каждое последующее число получается путем прибавления единицы в столбик к предыдущему (в пятеричной системе счисления! т.к. цифр всего пять).
• Порядковый номер, написанный рядом с пунктом, всегда на единицу больше располагающейся рядом цифры в пятеричной системе счисления.
• Определим число, которое получится, если мы в начале слова поставим букву К (остальные должны остаться нулями, т.к. числа идут по порядку, а нам необходимо первое, начинающееся с К):

K -> 2 -> 2000

• Полученное число — 2000 — необходимо перевести из пятеричной системы счисления в десятичную, чтобы узнать порядковый номер:

По формуле разложения числа по степеням основания:

20005 = 2 * 53 + 0 * 22 + 0 + 0 = 2 * 125 = 25010 

• Поскольку порядковый номер числа всегда на единицу больше самого числа, то имеем 251.

Результат: 251

• Пронумерованный список начинается со всех букв А. Представим, что А — 0, В — 1, Г — 2, Е — 3, Н — 4. Получим следующий список:

1. 0000
2. 0001
3. 0002
4. 0003
5. 0004
6. 0010

• Такой список представляет из себя увеличивающиеся числа 5-й системы счисления.
• Так как букве А соответствует 0, то первое (самое младшее) четырехзначное число без нуля — это 1111.
• Чтобы вычислить под каким номером стоит данное число, переведем его в 10-ю систему и прибавим к результату единицу (так как порядковые номера в списке на единицу больше самих чисел):

11115 = 1 * 53 + 1 * 52 + 1 * 51 + 1 * 50 = 156
156 + 1 = 157

Результат: 157

• Для решения данного задания необходимо вспомнить две формулы:

1. Формула Шеннона:

x = log₂(1/p)

x - количество информации в сообщении о событии
p - ве­ро­ят­ность со­бы­тия

2. Формула вероятности случайного события:

p(A) = m/n

m - число случаев, способствующих событию А
n - общее число равновозможных случаев

• Подставим в первую формулу известное значение — вероятность того, что Ва­си­лий по­лу­чил чет­вер­ку:

2 = log2(1/p);
    => 
1/p = 4; 
    =>
p = 1/4

• Затем подставим известное по условию значение в формулу вероятности случайного события:

p = ?/20

• Поскольку p мы уже нашли, подставим найденное значение и найдем искомое число — количество четверок за четверть:

1/4 = ?/20

? = 1/4 * 20 = 5

Результат: 5