The key of the cipher, called the “swivelling grid”, is a stencil made from a square sheet of chequered paper of size $n \times n$ $($where n is even$)$. Some of the cells are cut out. One side of the stencil is marked. When this stencil is placed onto a blank sheet of paper in four possible ways $($marked side up, right, down or left$)$, its cut-outs completely cover the entire area of the square, where each cell is found under the cut-out exactly once. The letters of the message, that have length $n^2$, are successively written into the cut-outs of the stencil, where the sheet of paper is placed on a blank sheet of paper with the marked side up. After filling in all of the cut-outs of the stencil with the letters of the message, the stencil is placed in the next position, etc. After removing the stencil from the sheet of paper, there is an encrypted message.

Find the number of different keys for an arbitrary even number n.

Add to My Problems