Author 
Topic: Typewriter Gibberish (Read 3957 times) 

william wu
wu::riddles Administrator
Gender:
Posts: 1291


Typewriter Gibberish
« on: May 13^{th}, 2003, 10:19am » 
Quote Modify

A puzzle written by Leonid Broukhis, sent via email. 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?

« Last Edit: May 13^{th}, 2003, 10:19am by william wu » 
IP Logged 
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com



tohuvabohu
Guest


Re: Typewriter Gibberish
« Reply #1 on: May 13^{th}, 2003, 11:05am » 
Quote Modify
Remove

In the 46 key case the worst case scenario would be 39720 iterations.


IP Logged 



tohuvabohu
Guest


Re: Typewriter Gibberish
« Reply #2 on: May 13^{th}, 2003, 11:09am » 
Quote Modify
Remove

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.


IP Logged 



Leonid Broukhis
Guest


Re: Typewriter Gibberish
« Reply #3 on: May 13^{th}, 2003, 1:38pm » 
Quote Modify
Remove

on May 13^{th}, 2003, 11:05am, tohuvabohu wrote:In the 46 key case the worst case scenario would be 39720 iterations. 
 No, it's slightly more than that: 60060. 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.


IP Logged 



Ghoste
Newbie
Posts: 5


Re: Typewriter Gibberish
« Reply #4 on: Jun 6^{th}, 2003, 3:03pm » 
Quote Modify

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): 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: ABCA BCAB CABC DED EDE FF .... ZZ 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 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"


IP Logged 



Ghoste
Newbie
Posts: 5


Re: Typewriter Gibberish
« Reply #5 on: Jun 6^{th}, 2003, 3:16pm » 
Quote Modify

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


IP Logged 



tohuvabohu
Guest


Re: Typewriter Gibberish
« Reply #6 on: Jun 6^{th}, 2003, 3:31pm » 
Quote Modify
Remove

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.


IP Logged 



Ghoste
Newbie
Posts: 5


Re: Typewriter Gibberish
« Reply #7 on: Jun 6^{th}, 2003, 5:20pm » 
Quote Modify

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


IP Logged 



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Typewriter Gibberish
« Reply #8 on: Jun 6^{th}, 2003, 8:05pm » 
Quote Modify

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_{3} 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 nonidentity elements of S_{3} 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)^{3} = 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 ?


IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Typewriter Gibberish
« Reply #9 on: Jun 6^{th}, 2003, 8:13pm » 
Quote Modify

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


IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



Jimmy Song
Guest


Re: Typewriter Gibberish
« Reply #10 on: Nov 19^{th}, 2003, 12:19pm » 
Quote Modify
Remove

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.


IP Logged 



rmsgrey
Uberpuzzler
Gender:
Posts: 2818


Re: Typewriter Gibberish
« Reply #11 on: Nov 21^{st}, 2003, 4:59am » 
Quote Modify

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::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)::


IP Logged 



