jump to navigation

Problem of the Day #129: Troubles with AutoCorrect July 26, 2011

Posted by Alex in : potd , trackback

Sreenath rewrote Mitchell’s AutoCorrect function! He chose a permutation $\{a_i\}$ of $\{1, 2, 3, 4, 5\}$ such that each $5$-letter word $s_1 s_2 s_3 s_4 s_5$ is replaced with $s_{a_1} s_{a_2} s_{a_3} s_{a_4} s_{a_5}$. Mitchell is saddened because his vocabulary only contains $5$-letter words possible from a $26$-letter alphabet. He then realizes that some words remain unchanged by AutoCorrect. Given that Sreenath chose a permutation $\{a_i\}$ randomly, find the expected value of the total number of words in Mitchell’s vocabulary that are unaffected by AutoCorrect.

You may use a four-function calculator, but one is not necessary.

Comments»

1. steven - August 8, 2011

i don’t get the 2nd line.

2. Alex - August 8, 2011

I’m not completely sure which line is the 2nd line (browsers vary), but I’ll try and explain through examples.

If the permutation is {1, 2, 3, 4, 5}, then each word is mapped to itself. If the permutation is {5, 4, 3, 2, 1}, then the word is reversed. If the permutation is {3, 5, 2, 4, 1}, then a new word is formed from an old word: the first letter of the new word is the 3rd letter of the old word; the second letter of the new word is the 5th letter of the old word; the 3rd letter of the new word is the 2nd letter of the old word; and so on. abcde would become cebda under this transformation.

Mitchell is only allowed to type 5-letter words. Each letter of one of these words comes from the 26-letter alphabet, and each letter can be used as many times as he wants. For example, aaaaa and abcdz are both valid words. Thus, Mitchell wants to find the number of 5-letter words that satisfy his requirement.

Also note that the *same permutation* is used for every word that Mitchell types. It’s not a random permutation each time, but a random permutation chosen once and used for all words.

Hope something there helped!

3. steven - August 15, 2011

cool i get it now. thanks