i already submitted a wrong answer, but would like to know how others tackle it.?

Question

A monkey sat in front of a special typewriter that only contained keys for the letters A, L, G, O, R, I, T, H, M, S. The monkey sat at the typewriter for a long time and pressed the keys. At the end of this time, the pattern typed on the page was quite remarkable. In fact, the monkey had typed out a large number of 10 letter words, all different mis-spellings of the word ALGORITHMS, one after another. Moreover, each mis-spelling had all of all the letters A, L, G, O, R, I, T, H, M, S and every letter was in the wrong position. If the monkey had typed every mis-spelling of this type exactly once, and had typed nothing other than these mis-spellings, how many times was the letter A typed in total?

Answer 1

Sorry guys, you appear to have missed something in the question. Firstly ALGORITHMS has 10 letters so I think you are suggesting it is 10! Rather than 9! Actually neither is right since it says the monkey always get's every letter in the wrong position.

Let’s stat by looking at a simple case, say 3 letters and let’s use the word APE. All the possible combinations are;

APE -1
AEP -2
PAE -3
PEA -4
EAP -5
EPA -6

There are 3! = 6 possibilities, however 1 & 2 have A position 1, 1 & 6 have P in position 2 and 1 & 3 have E in position 3 hence the only eligible words are 4 and 5. In this case this is actually (n-1)! however this does not hold in general which we can see from the 4 letter case, we’ll use the word APES and the only legal words are;

PASE
PESA
PSAE
EASP
ESAP
ESPA
SAPE
SEAP
SEPA

There are 9 such words, whereas (4-1)! = 3! = 6. Thus a slightly different tact is needed, unfortunately here is where it get’s pretty complicated. I haven’t had much luck working out a formula for the number of words however you will notice a method which I think holds up.

Firstly notice there are always n-1 possibilities for the first letter (since all but the actual first letter are eligible) now for the second letter there are again n-1 possibilities since all but the second letter can be used however the choice of first letter will affect the choice of second (and subsequent letters).

Now for each choice of the first letter we have two options either the next letter is letter 1 (i.e. A) or one of the other letters. If it is not letter one we have essentially the same problem on n-1 letters, if it is letter one we still have n-2 letters to place with the same constraint. Hence the choice of n-1 letters is the sum of the problems for n-1 and n-2 letters. This leads to the sequence where the number of words for n letters is give n by W(n) [similarly the numbers of words for n-1 letters is W(n-1)];

W(n) = n * [W(n-1) + W(n-2)]

Now we can work through to get the following;

n L(n)
3 2
4 9
5 44
6 265
7 1854
8 14833
9 133496
10 1334961


I’ve gotta be honest, I’m doubt this is the simplest or most efficient way but I do believe it works.

Answer 2

Tindall got that right. Actually, it's a permutation problem. You have 9 letters, and you take 9 letters. Different cominations because order matters and/or you cannot use a letter again. Thus, 9 P 9. Hence, 9! / (9-9)! = 9! / 0! = 9! / 1 = 9! = ____.

Answer 3

You have to subtract one, as every word typed was misspelled. Therefore the word ALGORITHMS was not typed.

Answer 4

you got me