Задача к ЕГЭ по информатике на тему «количество информации и комбинаторика» №1

Чтобы скрыть свои тайны от чужих глаз, ТС решил кодировать свой GTD не на родном языке, а на собственном придуманном. Собрав алфавит из 100 разных символов, он захотел добавить его на собственный телефон, но обнаружил ограничение по памяти на нём — максимум 4 Мбайт загружаемой информации. Найдите, какое минимальное количество символов ТС придётся выкинуть из собственного алфавита(тем самым подставив под угрозу безопасность своего GTD), если известно, что кроме алфавита, ему нужно загрузить дополнительную информацию, которая составляет 1 бит для первого символа, 2 бита для второго символа, то есть для каждого следующего символа требуется в 2 раза больше дополнительной информации, чем для предыдущего. Чтобы закодировать алфавит, ТС нужно сложить количество бит, отведенных на кодирование самих символов, и количество бит, отведенных на загрузку дополнительной информации.

Возьмём, что ТС использует N  символов и x  бит на символ. Тогда можем составить неравенство:

N ∗ x+ 20 + 21 + ...+ 2N −1 ≤ 225

Свернём по формуле арифмитической прогрессии:

        N       25 N ∗ x+ 2  − 1 ≤ 2

N не может быть равно 25, так как слева будет слишком много.

Возьмём N =  24  .

      5 24 ≤ 2  , значит, 5 бит на символ, x = 5  .

Неравенство выполняется.

Получается, ТС нужно оставить 100 — 24 = 76 символов.

Ответ: 76
Оцените статью
Я решу все!