Решение
Процедура зашифрования может быть полностью описана квадратной таблицей 10×10. На пересечении строки с номером i и столбца с номером j записываем цифру, в которую при зашифровании переходит цифра j, если она стоит в пароле после цифры i. Из однозначности расшифрования следует, что в каждой строке каждая цифра встречается ровно один раз.
Обозначим через ш
1, ш
2, ... ,ш
7 и о
1, о
2 зашифрованные пароли и два известных пароля в порядке, определяемом условием задачи. Процедура зашифрования сохраняет длину, поэтому ш
3 и ш
4 не могут соответствовать ни о
1, ни о
2. Предположив, что ш
1 соответствует о
1, получим часть таблицы, в которой в одной строке две одинаковые цифры. Это означает, что предположение неверно. Составляя таблицы, убеждаемся, что о
2 не шифруется ни в ш
6, ни в ш
7, ни в ш
5. В результате таких рассуждений остается только один вариант перехода о
1 - ш
2, о
2 - ш
5. Заполнение таблицы будет следующим:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
0 | | | | | | | | | 5 | |
1 | | | 3 | | | | | | | |
2 | 4 | 3 | 7 | | | | | 8 | | |
3 | | 7 | | | | | | | | |
4 | | | 2 | | | | | | | |
5 | | | | | | | | | 3 | |
6 | | | | | | | | | | |
7 | | | | | | 4 | | | | |
8 | | | 1 | 9 | | | | | | |
9 | td> | | | | | | | | | |
|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
0 | | | 6 | | | | | | 5 | |
1 | | | 3 | | | | | | | |
2 | 4 | 3 | 7 | 0 | 6 | 2 | 5 | 8 | 9 | |
3 | 3 | 7 | | | | | | | | |
4 | | | 2 | | | | | | | |
5 | | | | | | | | | 3 | 7 |
6 | | | | | | | | | | |
7 | | | | | | 4 | | | | |
8 | | | 1 | 9 | | | | | | |
9 | | | 1 | | | | | | | |
Очевидно, что в строке с номером 2 в последней клетке стоит 1. Знание этой таблицы позволяет однозначно расшифровать ш
3: получится 5830829. Пароли, соответствующие ш
1, ш
4, ш
6, ш
7, восстанавливаются не полностью.