Помогите разведчице

[Ktina]

(Оффтоп)

Папа места не находит, по квартире мечется. Думал, дочка - комсомолка, а она...
разведчица!

В разведке "Леншкола" используется шифр, в которм каждая буква русского алфавита кодируется последовательностью из двоичных цифр.
С помощью этого шифра разведчица Катя написала своё имя и отправила в сообщении разведчице Ксюше.
Какое минимальное число цифр могло быть в Катином сообщении, если известно, что Ксюша расшифровала его однозначно?

[Shadow]

10?
к=10
а=11
т=010
я=011
все остальные символы начинают с 00 и имеют определенную длину.

[Ktina]

Shadow в сообщении #516782 писал(а):

10?
к=10
а=11
т=010
я=011
все остальные символы начинают с 00 и имеют определенную длину.

Можно меньше.

[Shadow]

Ktina в сообщении #516803 писал(а):

Можно меньше.

Тогда 9. т=01, я=001, все остальные 000...

[Ktina]

Shadow в сообщении #516925 писал(а):

Ktina в сообщении #516803 писал(а):

Можно меньше.

Тогда 9. т=01, я=001, все остальные 000...

А что мешает сделать меньше девяти?

Нет, можно ещё меньше.

[Dave]

А меньше нельзя. Если это, конечно, правильный шифр, в котором никакая последовательность не является началом другой.

[Ktina]

Dave в сообщении #516939 писал(а):

А меньше нельзя. Если это, конечно, правильный шифр, в котором никакая последовательность не является началом другой.

А если шифр не правильный?

[Dave]

Ktina в сообщении #516940 писал(а):

А если шифр не правильный?

Тогда Катя и Ксюша не разведчицы.

[Ktina]

Dave в сообщении #516943 писал(а):

Ktina в сообщении #516940 писал(а):

А если шифр не правильный?

Тогда Катя и Ксюша не разведчицы.

Я верно поняла, что любой правильный шифр расшифровывается однозначно?
Но ведь не каждая расшифровывающаяся однозначно последовательность обязана быть правильно зашифрована.

Хорошо, давайте разобьём задачу на два пункта:

а) шифр - правильный
б) шифр не правильный

Будем считать, что с первым пунктом Вы успешно справились.

[Dave]

Ну тогда можно составить из 8 цифр при таком шифре:

К=00
а=01
т=10
я=11
<Остальные буквы> = строки длиной больше 8.

Только я, хоть убейте, не пойму, что это за шифр такой, в котором нормально зашифровать можно только одно слово (ну и какие-то его перестановки, разве что).

[Ktina]

Dave в сообщении #516984 писал(а):

Ну тогда можно составить из 8 цифр при таком шифре:

К=00
а=01
т=10
я=11
<Остальные буквы> = строки длиной больше 8.

Только я, хоть убейте, не пойму, что это за шифр такой, в котором нормально зашифровать можно только одно слово (ну и какие-то его перестановки, разве что).

Убивать не буду, но и 8 - неверный ответ.

[Dave]

Тогда уменьшим до 7 цифр:

К=00
а=01
т=1
я=10
<Остальные буквы> = строки длиной больше 7.

Меньше 7 нельзя потому, что:

1. Никакие из этих букв не могут иметь полностью одинаковый код, иначе они неразличимы.
2. Одной цифрой кодируется не более одной буквы, иначе любые другие последовательности могут быть расшифрованы как наборы "одноцифирных" букв.
3. Получаем, что минимум - это $1+2\cdot 3=7$.

[Shadow]

У вас слово "ткт" может быть прочтено как "яа"

[Ktina]

Dave в сообщении #516992 писал(а):

Тогда уменьшим до 7 цифр:

К=00
а=01
т=1
я=10
<Остальные буквы> = строки длиной больше 7.

Меньше 7 нельзя потому, что:

1. Никакие из этих букв не могут иметь полностью одинаковый код, иначе они неразличимы.
2. Одной цифрой кодируется не более одной буквы, иначе любые другие последовательности могут быть расшифрованы как наборы "одноцифирных" букв.
3. Получаем, что минимум - это $1+2\cdot 3=7$.

Вот теперь всё в ажуре

Можно ещё и так:

К=10
а=11
т=0
я=01
<Остальные буквы> = строки длиной больше 7.

[Dave]

Shadow в сообщении #517006 писал(а):

У вас слово "ткт" может быть прочтено как "яа"

О чём я и говорил, шифр неправильный (некоторые сообщения расшифровываются неоднозначно, но данное в условии - однозначно).