Математика ЕГЭ
Русский язык ЕГЭ
Математика 5-7
Математика ОГЭ
Информатика
Физика
Обществознание
Кликните, чтобы открыть меню

11. Количество информации и комбинаторика

1. Вспоминай формулы по каждой теме
2. Решай новые задачи каждый день
3. Вдумчиво разбирай решения

Вычисление количества информации в паролях и автомобильных номерах

Задание 1 #16048

Петрович с соседнего подъезда занимается созданием и учётом номеров для машин. Эти номера он отдаёт в местное МВД для людей, которые оформляют свои машины. Бывают массовые и индивидуальные заказы. Каждый созданный номер необходимо внести в общую базу данных, где хранятся номера машин всех россиян. Поступил заказ на всевозможные варианты номеров “С*ОТ?КА*” для 128 региона (вместо символа “?” используются все буквы кириллицы, вместо символа “*” используются цифры 0-7, при этом используется максимальная из всех вариантов номера мощность алфавита). В базу данных информация заносится по следующим правилам: номер разбивается на отдельные (одинарные) символы (то есть “АР” рассматривается как “А” и “Р”); для кодирования кириллицы в номере используется русский алфавит из 33 букв, для кодирования каждой цифры в номере используется общий “алфавит” (словарь) с одной и той же мощностью, при этом он (словарь) занимает минимальное количество бит; число региона кодируется минимальным количеством бит. Вся информация занимает минимальное целое число байт. Сколько Кбайт нужно загрузить Петровичу в базу данных МВД? В ответе укажите целое число.

1 символ кириллицы, состоящей из 33 букв, может быть закодирован не менее, чем 6 битами, так как \( 2^{5}=32<33<2^{6}=64 \).

Рассмотрим заказанный номер как “С”,“*”,“О”,“Т”,“?”,“К”,“А”,“*”. Используется 6 букв из кириллицы и 2 цифры. Так как максимальное число 7, то придётся выделить хотя бы 3 бита, так как \( 2^{3}=8 \). Итого, \( (6\cdot6+2\cdot3)\cdot33\cdot8\cdot8=88704 \) бит (умножаем на 33 и 8, потому что необходимо перебрать все тройки из букв, которых всего 33, с цифрами, которых всего 8, так как используются цифры 0-7).

Регион 128 может быть закодирован не менее, чем 7 битами, так как \( 2^{7}=128 \). Для всего заказа соответственно \( 7\cdot33\cdot8\cdot8=14784 \) бит.

Итак, получаем, что Петровичу придётся внести

\( \dfrac{88704+14784}{8\cdot1024}\approx13 \) Кбайт информации о номерах из заказа.

Ответ: 13

Задание 2 #16043

Петрович с соседнего подъезда занимается созданием и учётом номеров для машин. Эти номера он отдаёт в местное МВД для людей, которые оформляют свои машины. Бывают массовые и индивидуальные заказы. Каждый созданный номер необходимо внести в общую базу данных, где хранятся номера машин всех россиян. Поступил заказ на 33 номеров “ЦА456Р*” для 1234 региона (вместо символа “*” используются буквы кириллицы, при этом используется максимальная из всех вариантов номера мощность алфавита). В базу данных информация заносится по следующим правилам: номер разбивается на отдельные (одинарные) символы (то есть “АР” рассматривается как “А” и “Р”); для кодирования кириллицы в номере используется русский алфавит из 33 букв, для кодирования каждой цифры в номере используется общий “алфавит” (словарь) с одной и той же мощностью, при этом он (словарь) занимает минимальное количество бит; число региона кодируется минимальным количеством бит. Вся информация занимает минимальное целое число байт. Сколько байт нужно загрузить Петровичу в базу данных МВД? В ответе укажите целое число.

1 символ кириллицы, состоящей из 33 букв, может быть закодирован не менее, чем 6 битами, так как \( 2^{5}=32<33<2^{6}=64 \).

Рассмотрим заказанный номер как “Ц”,“А”,“4”,“5”,“6”,“Р”,“*”. Используется 4 буквы из кириллицы и 3 цифры. Так как максимальное число 6, то придётся выделить хотя бы 3 бита, так как \( 2^{2}=4<7<2^{3}=8 \). Итого, \( (4\cdot6+3\cdot3)\cdot33=1089 \) бит.

Регион 1234 может быть закодирован не менее, чем 11 битами, так как \( 2^{10}=1024<1234<2^{11}=2048 \). Для 33 номеров соответственно \( 11\cdot33=363 \) бит.

Итак, получаем, что Петровичу придётся внести

\( \dfrac{1089+363}{8}\approx182 \) байт информации о 33 номерах.

Ответ: 182

Задание 3 #16044

Петрович с соседнего подъезда занимается созданием и учётом номеров для машин. Эти номера он отдаёт в местное МВД для людей, которые оформляют свои машины. Бывают массовые и индивидуальные заказы. Каждый созданный номер необходимо внести в общую базу данных, где хранятся номера машин всех россиян. Поступил заказ на всевозможные варианты номеров “Б1*1Р?К” для 89 региона (вместо символа “?” используются буквы кириллицы, вместо символа “*” используются цифры 0-9, при этом используется максимальная из всех вариантов номера мощность алфавита). В базу данных информация заносится по следующим правилам: номер разбивается на отдельные (одинарные) символы (то есть “АР” рассматривается как “А” и “Р”); для кодирования кириллицы в номере используется русский алфавит из 33 букв, для кодирования каждой цифры в номере используется общий “алфавит” (словарь) с одной и той же мощностью, при этом он (словарь) занимает минимальное количество бит; число региона кодируется минимальным количеством бит. Вся информация занимает минимальное целое число байт. Сколько Кбайт нужно загрузить Петровичу в базу данных МВД? В ответе укажите целое число.

1 символ кириллицы, состоящей из 33 букв, может быть закодирован не менее, чем 6 битами, так как \( 2^{5}=32<33<2^{6}=64 \).

Рассмотрим заказанный номер как “Б”,“1”,“*”,“1”,“Р”,“?”,“К”. Используется 4 буквы из кириллицы и 3 цифры. Так как максимальное число 9, то придётся выделить хотя бы 4 бита, так как \( 2^{3}=8<10<2^{4}=16 \). Итого, \( (4\cdot6+3\cdot4)\cdot33\cdot10=11880 \) бит (умножаем на 33 и 10, потому что необходимо перебрать все пары из букв, которых всего 33, с цифрами, которых всего 10).

Регион 89 может быть закодирован не менее, чем 7 битами, так как \( 2^{6}=64<89<2^{7}=128 \). Для всего заказа соответственно \( 7\cdot33\cdot10=2310 \) бит.

Итак, получаем, что Петровичу придётся внести

\( \dfrac{11880+2310}{8\cdot1024}\approx2 \) Кбайт информации о номерах из заказа.

Ответ: 2

Задание 4 #16045

Петрович с соседнего подъезда занимается созданием и учётом номеров для машин. Эти номера он отдаёт в местное МВД для людей, которые оформляют свои машины. Бывают массовые и индивидуальные заказы. Каждый созданный номер необходимо внести в общую базу данных, где хранятся номера машин всех россиян. Поступил заказ на всевозможные варианты номеров “ГР6*6ОБ?” для 64 региона (вместо символа “?” используются все буквы кириллицы, вместо символа “*” используются цифры 0-6, при этом используется максимальная из всех вариантов номера мощность алфавита). В базу данных информация заносится по следующим правилам: номер разбивается на отдельные (одинарные) символы (то есть “АР” рассматривается как “А” и “Р”); для кодирования кириллицы в номере используется русский алфавит из 33 букв, для кодирования каждой цифры в номере используется общий “алфавит” (словарь) с одной и той же мощностью, при этом он (словарь) занимает минимальное количество бит; число региона кодируется минимальным количеством бит. Вся информация занимает минимальное целое число байт. Сколько Кбайт нужно загрузить Петровичу в базу данных МВД? В ответе укажите целое число.

1 символ кириллицы, состоящей из 33 букв, может быть закодирован не менее, чем 6 битами, так как \( 2^{5}=32<33<2^{6}=64 \).

Рассмотрим заказанный номер как “Г”,“Р”,“6”,“*”,“6”,“О”,“Б”,“?”. Используется 5 букв из кириллицы и 3 цифры. Так как максимальное число 6, то придётся выделить хотя бы 3 бита, так как \( 2^{2}=4<7<2^{3}=8 \). Итого, \( (5\cdot6+3\cdot3)\cdot33\cdot7=9009 \) бит (умножаем на 33 и 7, потому что необходимо перебрать все пары из букв, которых всего 33, с цифрами, которых всего 7, так как по условию используются только цифры 0-6).

Регион 64 может быть закодирован не менее, чем 6 битами, так как \( 2^{6}=64 \). Для всего заказа соответственно \( 6\cdot33\cdot7=1386 \) бит.

Итак, получаем, что Петровичу придётся внести

\( \dfrac{9009+1386}{8\cdot1024}\approx2 \) Кбайт информации о номерах из заказа.

Ответ: 2

Задание 5 #16046

Петрович с соседнего подъезда занимается созданием и учётом номеров для машин. Эти номера он отдаёт в местное МВД для людей, которые оформляют свои машины. Бывают массовые и индивидуальные заказы. Каждый созданный номер необходимо внести в общую базу данных, где хранятся номера машин всех россиян. Поступил заказ на всевозможные варианты номеров “АМ*?*АМ” для 228 региона (вместо символа “?” используются все буквы кириллицы, вместо символа “*” используются цифры 0-9, при этом используется максимальная из всех вариантов номера мощность алфавита). В базу данных информация заносится по следующим правилам: номер разбивается на отдельные (одинарные) символы (то есть “АР” рассматривается как “А” и “Р”); для кодирования кириллицы в номере используется русский алфавит из 33 букв, для кодирования каждой цифры в номере используется общий “алфавит” (словарь) с одной и той же мощностью, при этом он (словарь) занимает минимальное количество бит; число региона кодируется минимальным количеством бит. Вся информация занимает минимальное целое число байт. Сколько Кбайт нужно загрузить Петровичу в базу данных МВД? В ответе укажите целое число.

1 символ кириллицы, состоящей из 33 букв, может быть закодирован не менее, чем 6 битами, так как \( 2^{5}=32<33<2^{6}=64 \).

Рассмотрим заказанный номер как “А”,“М”,“*”,“?”,“*”,“А”,“М”. Используется 5 букв из кириллицы и 2 цифры. Так как максимальное число 9, то придётся выделить хотя бы 4 бита, так как \( 2^{3}=8<10<2^{4}=16 \). Итого, \( (5\cdot6+2\cdot4)\cdot33\cdot10\cdot10=125400 \) бит (умножаем на 33 и 10, потому что необходимо перебрать все тройки из букв, которых всего 33, с цифрами, которых всего 10).

Регион 228 может быть закодирован не менее, чем 8 битами, так как \( 2^{7}=128<228<2^{8}=256 \). Для всего заказа соответственно \( 8\cdot33\cdot10\cdot10=26400 \) бит.

Итак, получаем, что Петровичу придётся внести

\( \dfrac{125400+26400}{8\cdot1024}\approx19 \) Кбайт информации о номерах из заказа.

Ответ: 19

Задание 6 #16047

Петрович с соседнего подъезда занимается созданием и учётом номеров для машин. Эти номера он отдаёт в местное МВД для людей, которые оформляют свои машины. Бывают массовые и индивидуальные заказы. Каждый созданный номер необходимо внести в общую базу данных, где хранятся номера машин всех россиян. Поступил заказ на всевозможные варианты номеров “БО*Г?АМ” для 56 региона (вместо символа “?” используются все буквы кириллицы, вместо символа “*” используются цифры 0-4, при этом используется максимальная из всех вариантов номера мощность алфавита). В базу данных информация заносится по следующим правилам: номер разбивается на отдельные (одинарные) символы (то есть “АР” рассматривается как “А” и “Р”); для кодирования кириллицы в номере используется русский алфавит из 33 букв, для кодирования каждой цифры в номере используется общий “алфавит” (словарь) с одной и той же мощностью, при этом он (словарь) занимает минимальное количество бит; число региона кодируется минимальным количеством бит. Вся информация занимает минимальное целое число байт. Сколько Кбайт нужно загрузить Петровичу в базу данных МВД? В ответе укажите целое число.

1 символ кириллицы, состоящей из 33 букв, может быть закодирован не менее, чем 6 битами, так как \( 2^{5}=32<33<2^{6}=64 \).

Рассмотрим заказанный номер как “Б”,“О”,“*”,“Г”,“?”,“А”,“М”. Используется 6 букв из кириллицы и 1 цифру. Так как максимальное число 4, то придётся выделить хотя бы 3 бита, так как \( 2^{2}=4<5<2^{3}=8 \). Итого, \( (6\cdot6+1\cdot3)\cdot33\cdot5=6435 \) бит (умножаем на 33 и 5, потому что необходимо перебрать все пары из букв, которых всего 33, с цифрами, которых всего 5, так как используются цифры 0-4).

Регион 56 может быть закодирован не менее, чем 6 битами, так как \( 2^{5}=32<56<2^{6}=64 \). Для всего заказа соответственно \( 6\cdot33\cdot5=990 \) бит.

Итак, получаем, что Петровичу придётся внести

\( \dfrac{6435+990}{8\cdot1024}\approx1 \) Кбайт информации о номерах из заказа.

Ответ: 1

Задание 7 #16054

Британские учёные проводят много различных исследований и наблюдений, о которых знают даже папуасы в Новой Гвинее. Для доступа на территорию их института учёные имеют специальные чипы в правой руке. На него записаны имя сотрудника, название его исследования и личный код для идентификации. Для записи имени и названия исследования используется латинский алфавит (26 букв) с заглавными буквами. Под имя выделено 10 символов, а для исследования 152 символа. При этом используют посимвольное кодирование, все символы кодируют одинаковым минимально возможным количеством бит. Для записи личного кода используют числа. Вся информация на чипе занимает минимальное целое число байт. Каково максимальное количество бит используется в кодировании личного кода коде чисел, если известно, что база данных из 80 Британских учёных весит 10 КБайт?

1 символ латинского алфавита с заглавными буквами может быть закодирован не менее, чем 6 битами, так как \(2^5=32<26\cdot2<2^6=64.\) Так как символы кодируют минимально возможным числом бит, то 10 символов имени занимают \(10\cdot6=60\) бит, а 152 символов исследования занимают \(152\cdot6=912\) бит.

На одного Британского учёного приходится не более \(\frac{10\cdot1024}{80}=128\) байт. Пусть i – количество бит, которым закодирован личный код. Получается, что \(128\ \text{байт}\ge (i+50\ \text{бит}+760\ \text{бит})\div 8\), \(1024-912-60\ge i,\) \(52\ge i,\) \( i=52 \) бита.

Ответ: 52