Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This question is about a puzzle from the book of Raymond Smullyan: The Lady or the Tiger?

The description of the puzzle starts in Chapter 8, p. 103 which I do not repeat here as the whole book is accessible at the above link for those who do not know it. Smullyan provides a key of length 10 on p. 163, however, this is not the shortest, I know a key of length 8. Is this the shortest?

share|improve this question
add comment

1 Answer 1

up vote 2 down vote accepted

Edited in recognition of closed-mindedness.

My brute force search shows no keys shorter than 10. Here are the only keys of length 10 and 11 respectively:

RVLVQRVLVQ VRLVQVRLVQ

VLRVQVLRVQQ VLVRQVLVRQQ

Curiously, there are no keys of length 12.

The only word of length 7 that does not crash under iteration is RRQRRQQ, and it evolves unboundedly. There are 74 words of length 8 that grow to over 30 letters, I think none of them cycles, and there are two eventually cycling words, one you gave and the other its pair RQVRLVQQ. The first time an odd period greater than 1 appears is at length 12, these are the originating words (all end up with period 3):

RQQVLLRLVQQQ

RLQVLLRLVQQQ

RQLVLLLRVQQQ

RQVLLLVLRQQQ

RQLVLLLVRQQQ

RQLVLLLRVLQQ

RQVLLLVLRLQQ

RQLVLLLVRLQQ

RQLLVLLRLVQQ

RQVLLLVQQRQQ

RQVLLLVLQRQQ

RQLVLLLVQRQQ

share|improve this answer
1  
Ok, then I give here my key of length 8 (which can be extended to length 9 keys), spoiler alert! RQRVLVQQ –  domotorp Feb 4 '10 at 16:56
    
You're right, I edited my answer accordingly. –  Thorny Feb 5 '10 at 9:46
    
Wow, nice list, thank you! But why do you say that RRQRRQQ evolves unboundedly? It seems to me that it crashes in the 3rd step. –  domotorp Feb 5 '10 at 12:03
    
Because I only checked iterations up to length 30, and the maximal achieved length of that word is 32. Sorry. –  Thorny Feb 5 '10 at 12:19
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.