Author |
Topic: Typewriter Gibberish (Read 4868 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Typewriter Gibberish
« on: May 13th, 2003, 10:19am » |
 Quote  Modify
|
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?
|
| « Last Edit: May 13th, 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 13th, 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 13th, 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
|
on May 13th, 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 6th, 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:
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
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 6th, 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
|
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 6th, 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 6th, 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 SN. One way of denoting a permutation in SN 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 S3 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 xN = I, the identity of G. More generally, there is a least k, such that xk = 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 SN, 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 SN = N!.
Mathematically what this puzzle calls for then, is to find the highest order of any element of SN.
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 S3 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 xk = rk...zk, which will = I only if each of rk, ..., zk 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 {ai}i=1k, where SUMi ai <= 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 6th, 2003, 8:13pm » |
Quote Modify
|
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.
|
|
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 19th, 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: 2872
|
|
Re: Typewriter Gibberish
« Reply #11 on: Nov 21st, 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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print