Решение
Рассмотрим некоторую расстановку ненулевых цифр на окружности. Упорядоченную пару (a,b) соседних цифр на этой окружности назовем 1-соседней, если b является соседней с a по часовой стрелке. Пару (a,c) назовем 2-соседней, если существует цифра b, для которой пары (a,b) и (b,c) являются 1-соседними.
Каждой расстановке ненулевых цифр на окружности однозначно соответствует цепочка 1-соседних пар вида: (1,a
1), (a
1,a
2), (a
2,a
3), ..., (a
7,a
8), (a
8,1), которой, в свою очередь, однозначно соответствует цепочка 2-соседних пар вида:
| | | (1,a2), (a2,a4), (a4,a6),(a6,a8),(a8,a1)(a1,a3)(a3,a5)(a5,a7)(a7,1), |
| (*) |
где a
2,a
3,...,a
8 ∈ {2,...,9} и a
i ≠ a
j при i ≠ j.
Если из цепочки (*) удалить любую пару, то по оставшимся парам она восстанавливается однозначно.
Если из цепочки (*) удалить две соседние пары, то она также восстанавливается однозначно.
Удаление из (*) любых трех пар приводит к неоднозначности восстановления цепочки (*). В этом можно убедиться, рассмотрев следующие фрагменты цепочки вида (*):
| (a,b)(b,c)(c,d) и (a,c)(c,b)(b,d), | | (a,b,c,d - различные цифры),
|
|
(a,b)_(c,d)(d,e) и (a,d)(d,b)_(c,e), | | (a,b,c,d,e - различные цифры),
| |
(a,b)_(c,d)_(e,f) и (a,d)(e,b)_(c,f), | | (a,b,c,d,e,f - различные цифры)
|
Таким образом, при наличии двух указанных в условии задачи цифровых текстов нам будут известны некоторые 2-соседние пары, в которых первая цифра берется из первой криптограммы, а вторая - из второй. Поэтому с учетом вышесказанного получаем условие однозначного восстановления порядка расстановки цифр на данной окружности.