MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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:



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













share|cite|improve this answer
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

Your Answer


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.