Задача
Ключом шифра, называемого "поворотная решетка", является трафарет, изготовленный из квадратного листа клетчатой бумаги размера n×n (n чётно). Некоторые из клеток вырезаются. Одна из сторон трафарета помечена. При наложении этого трафарета на чистый лист бумаги четырьмя возможными способами (помеченной стороной вверх, вправо, вниз, влево) его вырезы полностью покрывают всю площадь квадрата, причём каждая клетка оказывается под вырезом ровно один раз. Буквы сообщения, имеющего длину n², последовательно вписываются в вырезы трафарета, сначала наложенного на чистый лист бумаги помеченной стороной вверх. После заполнения всех вырезов трафарета буквами сообщения трафарет располагается в следующем положении и т. д. После снятия трафарета на листе бумаги оказывается зашифрованное сообщение.
Найдите число различных ключей для произвольного чётного числа n.
Решение
Все клетки квадрата размера разобьём на непересекающиеся группы по четыре клетки в каждой. Отнесём клетки к одной и той же группе, если при каждом повороте квадрата до его самосовмещения они перемещаются на места клеток этой же группы. Всего таких групп будетn²/4. При наложении трафарета на квадрат ровно одна клетка из каждой группы окажется под его вырезами. Каждому трафарету поставим в соответствие упорядоченный набор всех клеток из таких групп, оказавшихся под вырезами трафарета при наложении его на квадрат помеченной стороной вверх. Этих клетокn²/4(по одной из каждой группы), значит, всего таких наборов 4n²/4..
Ответ
4n²/4.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь