Архив задач олимпиады по математике и криптографии
Перебор троичных ключей с наименьшими изменениями
При входе в личный кабинет на терминале требуется ввести трехзначный пароль x1,x2,x3, где x i∈{0,1,2}. Для этого на терминале имеются 3 окошка, а под каждым окошком расположены три кнопки. При нажатии на кнопку в окошке над ней появляется соответствующая цифра. Сейчас в окошках выставлена комбинация 000. Какое наименьшее количество нажатий кнопок потребуется, чтобы перебрать все возможные варианты пароля?
Всего имеется 27=33 трехзначных паролей (наборов) из 0, 1 и 2. Один такой пароль 000 уже набран, значит нам остается перебрать оставшиеся 26 вариантов, для чего потребуется по крайней мере 26 нажатий кнопок. Покажем, что 26 нажатий действительно хватит. Для этого все трехзначные наборы упорядочим так, чтобы соседние наборы отличались только в одном символе (классический код Грея). Тогда переход от одного набора к соседнему будет осуществляться нажатием одной кнопки, и всего потребуется как раз 26 нажатий. Упорядочить так наборы можно многими способами. Одна из возможных идей состоит в следующем: каждый пароль будем интерпретировать как координаты точки в трехмерном пространстве (рис.). Координаты точек, лежащих на прямой, параллельной одной из координатных осей, как раз отличаются только в одном символе. Значит, если, двигаясь параллельно осям, мы обойдем все точки, то тем самым получим требуемое упорядочение. Один из возможных обходов представлен на рисунке.
