April Fool's Day and the typewriter

[BMAD]

On April 1st a typist found the hammers of the typewriter re-soldered in an arbitrary order, so typing a text resulted in gibberish. The typist decided to type a document in its entirety using this typewriter. Afterwards, if the result does not represent the original text, he will type the result, and so on. Prove that the clear text will emerge sooner or later. How many iterations are enough to guarantee that the clear text will appear, if the typewriter has, say, 46 keys? N keys

[jasen]

I can prove this hipothesis is wrong !

let say the tipewritter only have 5 hammers and it was set like this :

letter 2 placed at hammer 1
letter 3 placed at hammer 2
letter 5 placed at hammer 3
letter 1 placed at hammer 4
letter 4 placed at hammer 5

our expected word is "12345"

1st iteration 2 3 5 1 4
2nd iteration 3 5 4 2 1
3rd iteration 4 1 2 5 3
4th iteration 5 4 1 3 2
5th iteration 2 3 5 1 4  (it is back to 1st iteration)

so it will never reveal the the expected word.

 

 

[bonanova]

@jasen, check your 3rd iteration.

12345 => 23514
23514 => 35421
35421 => 54132
54132 => 41253
41253 => 12345

[jasen]

@bonanova, thanks for  correcting me.

From the pattern, I think the original word will appear  before 47-th iteration.

I will create a computer simulation to check my answer.

[bonanova]

Looks like

A worst-case permutation for 46 keys:

2 1 4 5 3 7 8 9 10 6 12 13 14 15 11 17 18 19 20 21 22 16 24 25 26 27 28 29 30 31 32 33 23 35 36 37 38 39 40 41 42 43 44 45 46 34

This permutation requires 30030 iterations. Since it's a worst case, 30030 iterations guarantees recovery of the plaintext for 46 keys.

A little study of this permutation discloses the general form of a worst case for any value of N, as well as an algorithm to calculate the fewest iterations that guarantee recovery of the plaintext.

[bonanova]

The solution for N keys.

Write N as a sum of prime numbers. The number of iterations is the product of the distinct primes. For the previous case of N=46 we have

46 = 2+3+5+5+7+11+13

Now permute the groups:

2 means 1 2 => 2 1
3 means 4 5 6 => 5 6 4 (for example)
5 means 7 8 9 10 11 => 8 9 10 11 7 (for example)

and so on. Then the primes don't all repeat until their product of total iterations.

2x3x5x7x11x13 = 30,030

[kbrdsk]

I think we can go a little higher 

4x3x5x7x11x13 = 60,060 should work - as long as the individual cycles are co-prime it won't repeat until the product of the cycle lengths. 

For instance with 7 keys 2 3 4 1 6 7 5 shouldn't repeat for 12 cycles, indeed

2341675
3412756
4123567
1234675
2341756
3412567
4123675
1234756
2341567
3412675
4123756
1234567

So we start taking the first however many primes whose sum is <=n then with whatever keys we have left over try and replace primes with the most cost-efficient prime powers but I didn't go very far into that

 

 

[jasen]

 computer simulation proved  you are right !!

I think we can go a little higher 

Hidden Content