Jump to content
BrainDen.com - Brain Teasers
  • 0

April Fool's Day and the typewriter


BMAD
 Share

Question

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

Link to comment
Share on other sites

7 answers to this question

Recommended Posts

  • 0

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.

 

 

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 1

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

Link to comment
Share on other sites

  • 1

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

 

 

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...