Тема . ТЕОРИЯ ЧИСЕЛ

Оценка + пример в задачах по теории чисел

Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела теория чисел
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#92482

Каждую букву русского алфавита закодировали последовательностью из нулей и единиц (последовательности могут быть разной длины). Используя этот код, Сеня записал слово “ЛИГА”. Оказалось, что полученная последовательность нулей и единиц расшифровывается однозначно. Какое наименьшее количество цифр могло в ней быть?

Источники: Лига открытий - 2017

Показать ответ и решение

Оценка. Если цифр не больше 6,  то какие-то две из четырёх букв должны быть закодированы последовательностью длины 1,  т. е. одна из них закодирована цифрой 0,  а другая — цифрой 1.  Но тогда наша последовательность имеет расшифровку, в которой участвуют только эти две буквы, что противоречит условию.

Пример. Закодируем буквы, например, так: Л — 10,  И — 11,  Г — 0,  А — 01,  все остальные буквы закодируем разным количеством единиц, большим 3.  Нашему слову будет соответствовать последовательность 1011001.  Буквы, закодированной “1  ”, нет, а буква, начинающаяся с “10  ”, ровно одна — “10  ”. Таким образом, первая буква однозначно восстанавливается. Так как не существует буквы, начинающейся с “110  ”, вторая буква тоже расшифровывается однозначно. Буквы, код которой начинается с “00  ”, нет, поэтому третья буква закодирована символом “0  ”. Если код четвёртой буквы — “0  ”, то пятая буква должна быть закодирована символом “1  ”, а таких букв нет, значит, четвёртая буква закодирована “01  ”.

_________________________________________________________________________________________________________________________________________________________________________________

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

Ответ:

 7  цифр

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное онлайн-обучение

Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!