Совпадение при замене

• Решение

Решение

Последовательность из k нулей или k единиц обозначим соответственно через 0^k или 1^k. Тогда шифрование каждого знака сообщения состоит в замене




м п н п о 0  ® 0k11k2 1  ® 0k3  для I способа,       м п н п о 1  ® 1k40k5 0  ® 0k6  для II способа.

(1)

В зашифрованном сообщении все серии из единиц имеют длину k₂ для первого способа и длину k₄ для второго способа, поэтому, для совпадения результатов зашифрования необходимо, чтобы


k2=k4.

(2)

Теперь легко получить, что в сообщении должно быть одинаковое число нулей и единиц.

Пусть n - число нулей в сообщении. Тогда число нулей в зашифрованном I способом сообщении равно nk₁ + nk₃, а II способом - nk₅ + nk₆. Таким образом,


nk1 + nk3 = nk5 + nk6.

(3)

Из  видно, что сообщение должно начинаться с нуля и оканчиваться единицей. Пусть перед первой единицей сообщения расположено a нулей. Тогда первые а +1 знаков сообщения представляются при шифровании в виде:




при а=1       м п н п о 0k11k20k3    для I способа, 0k61k40k5    для II способа,




при а > 1       м п н п о 0k11k20k11k2...0k11k20k3   для I способа, 0ak61k40k5   для II способа.

При a=1 получаем необходимость равенства k₁=k₆, а значит, с учетом  - равенства k₃=k₅.

При а > 1 получаем условия:




k1=ak6 , а - натуральное,




k1=k5+bk6, b - натуральное или нуль.

Подставляя k₁=k₅+bk₆ в , получаем равенство k₃=(1-b)k₆, которое при натуральных k₃, k₆ и b і 0 возможно лишь в случае b = 0. Следовательно, k₃=k₆, а значит, с учетом  k₁=k₅.

Таким образом, при а > 1 необходимы условия k₂=k₄, k₅=k₁=ak₆=ak₃, где a - натуральное. Из  следует, что сообщение должно иметь вид 0...01...1, где число нулей и число единиц равно a.
• Ответ

Ответ

При k₂=k₄, k₁=k₆, k₃=k₅ сообщения вида 0101...01 шифруются одинаково.

При k₂=k₄, k₅=k₁=ak₆=ak₃, где a - натуральное, сообщения вида (0...01...1) ... (0...01...1) (группы из a нулей и a единиц) шифруются одинаково.

Примечание. Первый ответ не является частным случаем второго при a = 1.