wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Typewriter Gibberish
        
(Message started by: william wu on May 13^th, 2003, 10:19am)

Title: Typewriter Gibberish
Post by william wu on May 13^th, 2003, 10:19am

A puzzle written by Leonid Broukhis, sent via e-mail. Feel free to give opinions on its difficulty or wording.

On April 1st a typist found the hammers of the typewriter resoldered 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?

Title: Re: Typewriter Gibberish
Post by tohuvabohu on May 13^th, 2003, 11:05am

In the 46 key case the worst case scenario would be [hide]39720 iterations.[/hide]

Title: Re: Typewriter Gibberish
Post by tohuvabohu on May 13^th, 2003, 11:09am

When I saw the title of this thread I thought it was going to be about an interesting news article I just read:

NO PROSE FROM PLAYFUL PRIMATES
Display 'tests' old theory that typing monkeys could write
by Jill Lawless (Associated Press)

LONDON -- Give an infinite number of monkeys an infinite number of typewriters, the theory goes, and they will eventually produce the works of Shakespeare.

Give six monkeys one computer for a month, and they will make a mess.

Researchers at Plymouth University in England reported this week that primates left alone with a computer attacked the machine and failed to produce a single word.

In a project intended more as performance art than scientific
experiment, faculty and students in the university's media program left a computer in the monkey enclosure at Paignton Zoo in southwest England, home to six Sulawesi crested macaques.

Then, they waited.

At first, said researcher Mike Phillips, "the lead male got a stone and started bashing the hell out of it.

"Another thing they were interested in was in defecating and urinating all over the keyboard," added Phillips, who runs the university's Institute of Digital Arts and Technologies.

Eventually, Elmo, Gum, Heather, Holly, Mistletoe and Rowan produced five pages of text, composed mostly of the letter S. Later, A, J, L and M crept in.

Title: Re: Typewriter Gibberish
Post by Leonid Broukhis on May 13^th, 2003, 1:38pm

on 05/13/03 at 11:05:08, tohuvabohu wrote:

In the 46 key case the worst case scenario would be [hide]39720 iterations.[/hide]

No, it's slightly more than that: [hide]60060[/hide].

Unfortunately, for anyone who knows who Neil J. A. Sloane
is, this puzzle is as easy as figuring the values for
N=1 to 6 or 7; then typing in the sequence of the values into the search form. But as an interview question, I believe, it is quite good.

For extra credit, write a program that returns the answer for a given N.

Title: Re: Typewriter Gibberish
Post by Ghoste on Jun 6^th, 2003, 3:03pm

I don't know if the first part of the question was answered, but how's this proof that the doc will always revert back to the unscrambled eventually (also I came up with a different answer, so I'd be interested in seeing what I did wrong):

[hide] Each key can have an unchanged hammer or a random different hammer.

The key to the character represented in the hammer has also been replaced (it cannot have been unchanged, as the first key is using its hammer). The letter on the hammer can either correspond to the first key, or to yet another key.

As the typewriter has limited keys, eventually we will hit trace the sequence to the original key. If we map out the sequences for all keys we might come up with something like:

A-B-C-A
B-C-A-B
C-A-B-C
D-E-D
E-D-E
F-F
....
Z-Z

These sequences represent the number of times an individual character would have to be put through the scrambled typewriter to come back out unscrambled (for A, B and C it's 3 and for D and E it's 2).

If you mapped out all the sequences for each letter and counted the links (not the letters) on each of those sequences you could then look for their least common multiple and you would arrive at the number of times you would need to type the document to get the unscrambled original.

I came to 2 conclusions/assumptions to figure out the N problem (which is probably where I screwed up)

1. As for the amount needed in 46 (or N) keys, you just need to find the combination of sequences that would yield the largest least common multiple (because you're shooting for worst case).

2. Also, the sum of the lengths of all unique sequences (if we define unique as sequences that contain different letters, not just letters cycled) has to be 46 (as each letter would be to the right of a link exactly once in a set of all unique sequences).

So based on those 2 , to find the max number of tries based on the number of keys, start adding prime numbers (include 1) until you get just more than N and throw the last one out and then find their least common denominator. These basically represent the unique sequence lengths required for the worst case scenario.

For 46, these primes would be: 1 2 3 5 7 11 13 (which add up to 42 and have a least common denominator of 30030), so for 46 keys, it would take you 30030 tries to ensure succes [/hide]

Thoughts, comments? Please be kind when telling me I'm wrong, as I hurt easily :-)

Damn, my hide tags aren't working in the preview... :-(

-Luis
"Acracia es porvenir"

Title: Re: Typewriter Gibberish
Post by Ghoste on Jun 6^th, 2003, 3:16pm

Interesting that my answer came out to exactly half as much as Leonid. Hmmmmm... I wonder if I forgot to multiply by 2 somewhere :-D

Title: Re: Typewriter Gibberish
Post by tohuvabohu on Jun 6^th, 2003, 3:31pm

I suppose you won't mind correction from me, since I got it wrong,too. My original answer improved on yours by realizing there were enough spare keys to use 17 instead of 13 as the highest chain.
But the point we both missed is that a prime factor may occur more than once without being reducible if both occurances are in the same number. You can change your 2 to a 4 and double the total number of iterations needed.

Title: Re: Typewriter Gibberish
Post by Ghoste on Jun 6^th, 2003, 5:20pm

That makes sense. There's some pretty smart people on this board :-)
-Luis
"Acracia es porvenir."

Title: Re: Typewriter Gibberish
Post by Icarus on Jun 6^th, 2003, 8:05pm

Mathematically this is a group theory problem. The change of the hammers represents a permutation of the N keys. The set of all permutations of N objects is denoted by the symbol S_N. One way of denoting a permutation in S_N is to list the numbers 1 to N, and then below them, the number of the position each object is taken to. For instance the 6 permutations in S₃ are:

I	\|	A	\|	B	\|	X	\|	Y	\|	Z
1 2 3	\|	1 2 3	\|	1 2 3	\|	1 2 3	\|	1 2 3	\|	1 2 3
1 2 3	\|	2 3 1	\|	3 1 2	\|	1 3 2	\|	3 2 1	\|	2 1 3

Two permutations can be combined. For instance AX carries 1 -> 2 -> 3, 2 -> 3 -> 2, and 3 -> 1 -> 1. Thus AX = Y. Examing this, we get the following Multiplication table:

 I | A | B | X | Y | Z
A | B | I | Y | Z | X
B | I | A | Z | X | Y
X | Z | Y | I | B | A
Y | X | Z | A | I | B
Z | Y | X | B | A | I

An examination of this table provides the following properties of a group (though some are more easily proven from the definition):

The "multiplication" is associative: (xy)z=x(yz) for all x, y, z
There is an identity: Ix = xI = x for all x
Each element has an inverse:
II = I, AB = BA = I, XX = I, YY = I, and ZZ = I.

Notice also it is not commutative. For example AX = Y, but XA = Z.

The following theorem is true of all finite groups:
If a group G has N elements, and x is any member of G, then x^N = I, the identity of G. More generally, there is a least k, such that x^k = I, and k | N.

The number k is called the order of x in G, and is written o(x).

To apply this to the puzzle, since any rearrangement of the hammers corresponds to a permutation from S_N, by the quoted theorem, there must be some k, such that applying the rearrangement k times brings you back to the original arrangement - i.e. the intended text. Further, this k must divide the number of elements of S_N = N!.

Mathematically what this puzzle calls for then, is to find the highest order of any element of S_N.

If N=3, then it is seen by examination that the answer is 3. More generally, a permutation can be broken into a series of loops. For instance A takes 1 to 2, 2 to 3, and 3 back to 1. This loop is denoted by (123) (and by (231), and by (312) - but usually loops are listed with the lowest number first).
The non-identity elements of S₃ may be written as: A = (123), B = (132), X = (23), Y = (13), Z = (12).
For N > 3, multiple loop permutations are possible. For instance (12)(34). Every permutation can be expressed in this way.
If two loops do not involve any of the same positions, then it should be clear that they commute: for instance (123)(456) = (456)(123). Thus [(123)(456)]^k = (123)^k(456)^k. It is also easy to see that the order of a loop is just its length: (123)³ = I.

Last, if x=rst...yz, where each of r, s, t, ..., y, z are independent loops, then x^k = r^k...z^k, which will = I only if each of r^k, ..., z^k equals I. Which is true iff k is a multiple of all the orders. Hence the order of x is the LCM (least common multiple) of the lengths of all the independent loops in x.

Since the sum of the independent loops in x must be less than or equal to N, the problem reduces to this:

What is the maximum LCM of {a_i}_i=1^k, where SUM_i a_i <= N ?

Title: Re: Typewriter Gibberish
Post by Icarus on Jun 6^th, 2003, 8:13pm

I want to point out that what I have written is just a more math-theoretic expression of the same logic as used by Ghoste, not a different approach.

Title: Re: Typewriter Gibberish
Post by Jimmy Song on Nov 19^th, 2003, 12:19pm

I interpreted the question differently, namely, how many iterations guarantee the clear text for any particular typewriter setting on that particular iteration. In this case, 60060 is clearly not the case if there's a loop of length 41 (60060 is not divisible by 41). The answer, in this case, is a little more complicated.

Title: Re: Typewriter Gibberish
Post by rmsgrey on Nov 21^st, 2003, 4:59am

Actually, I think the variation is simpler to answer - you don't need to find worst case sets of cycles.

For N=46, I get::[hide]32*27*25*7*11*13*17*19*23*29*31*37*41*43 - the LCM of 1...46 (which I'm too lazy to evaluate explicitly)::[/hide]