The Keyboard Prank

Anne comes into the office to find that her co-workers had played a prank on her. The keycaps on her keyboard had been shuffled such that if she types out a message according to the letters on the keyboard, the message is gibberish when it appears on the screen.

No matter, she thinks. She types out the gibberish message with the letters on her keyboard, ending up with another gibberish message. She continues this process on the new message, repeating until she gets her original message back.

Is it always possible to get the original message back, no matter how the keyboard was rewired? And in the cases where this is possible, what is the maximum number of times she would need to retype the message in order to get the original message back? We can assume that the message only involves the letters A-Z.

Solution

It is always possible to get the original message back, no matter how the keyboard is rewired. She is guaranteed to get the original message back after retyping the message 26771144400 times.

To show this, let’s start with an easier example with the letters A to E. Imagine if Anne types out “ABCDE” using her keyboard and observes the letters that appear. Notice that the result will also be the letters from A-E, just not in the same order. That is a permutation!

We’ll assume after typing “ABCDE”, she sees “BCAED” on her screen. Remember that a permutation can be decomposed into disjoint cycles? We can represent the cycles with:

A → B → C → A
D → E → D

If a message starts with the letter A, then after the first re-type it will be B, then C, then back to A after 3 steps. The same goes for the other letters in this cycle, B and C. By the same reasoning, if a message starts with the letter D or E, it will end up on the original letter again after 2 steps. For us to get the original message again, we need to type it 6 times, the lowest common multiple of 2 and 3.

In general, a permutation of 5 letters can leave us with cycles of length 1, 2, 3, 4, and/or 5. To get the worst-case scenario, we take the lowest common multiple of 1, 2, 3, 4, and 5 to get 60.

For our original problem with 26 letters, we know that the re-mapping of letters also gives us a permutation that can be broken down into cycles of 1 to 26. The lowest common multiple of all the numbers from 1 to 26 is 26771144400, giving us our answer.

Extra Credit: Computing the LCM

If you want to learn how to compute the lowest common multiple of the numbers from 1 to n by hand, read on.

First, remember that to get the lowest common multiple (LCM) of any 2 numbers, we have to compute both their prime factorisations, then take the highest power of each prime. Let’s try finding the LCM of 72 and 100.

$72 = 2^{3} \times 3^{2}$
$100 = 2^{2} \times 5^{2}$

Taking the highest of each power, we get $2^{3} \times 3^{2} \times 5^{2} = 1800$ .

How about the LCM of a sequence of numbers from 1 to n? For a start, notice that we’ll only have to consider the primes between 1 to n. Any prime above that will have a power of 0 in the prime factorisation.

Let’s try to compute the LCM of the numbers from 1 to 10. Our primes are 2, 3, 5, and 7.

The largest number from 1 to 10 that is a power of 2 is $8 = 2^{3}$ . The next power of 2 is 16, which is more than 10. So the highest power of 2 in the LCM is 3. We can actually compute this more easily with $⌊ \log_{2} n ⌋$ . The largest number from 1 to 10 that is a power of 3 is $9 = 3^{2}$ , hence the highest power of 3 in the LCM is 2 (which we can also compute with $⌊ \log_{3} n ⌋$ . Likewise, for 5 and 7, the highest power is 1. The LCM of the numbers from 1 to 10 is therefore $2^{3} \times 3^{2} \times 5 \times 7 = 2520$ .

In general, the LCM of the numbers 1 to n is:

$\prod_{p \in P} p^{⌊ \log_{p} n ⌋} where P = {p \in N : p \leq n, p prime}$

For n=26, we get the LCM $= 2^{4} \times 3^{2} \times 5^{2} \times 7 \times 11 \times 13 \times 17 \times 19 \times 23$ .

Try These Next

Counting Towns from a Tower

Antipodal Temperature

Measuring Time with Hourglasses 1