2

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?

flag

1 Answer

2

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

link|flag
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 2010 at 16:56
You're right, I edited my answer accordingly. – Thorny Feb 5 2010 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 2010 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 2010 at 12:19

Your Answer

Get an OpenID
or

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