4
$\begingroup$

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, and here is the important part (copy-pasted from Bruce Ediger's webpage):

Property Q: For any combination x, the combination QxQ is specially related to x.

Property L: If x is specially related to y, then Lx is specially related to Qy.

Property V (the reversal property: If x is specially related to y, then Vx is specially related to the reverse of y.

Property R (the repetition property: If x is specially related to y, then Rx is specially related to yy.

Property Sp: If x is specially related to y, then if x jams the lock, y is neutral, and if x is neutral, then y jams the lock.

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? Spoiler alert: You can find this key in my comment to the accepted answer.)

$\endgroup$
2
  • 1
    $\begingroup$ For multiple reasons, including link rot, it is usually a good practice to actually reproduce the question you're asking. $\endgroup$
    – Michaël
    Mar 20, 2017 at 10:25
  • 1
    $\begingroup$ @M Agree, done! $\endgroup$
    – domotorp
    Mar 20, 2017 at 10:57

1 Answer 1

3
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ Ok, then I give here my key of length 8 (which can be extended to length 9 keys), spoiler alert! RQRVLVQQ $\endgroup$
    – domotorp
    Feb 4, 2010 at 16:56
  • $\begingroup$ You're right, I edited my answer accordingly. $\endgroup$
    – Thorny
    Feb 5, 2010 at 9:46
  • $\begingroup$ 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. $\endgroup$
    – domotorp
    Feb 5, 2010 at 12:03
  • $\begingroup$ Because I only checked iterations up to length 30, and the maximal achieved length of that word is 32. Sorry. $\endgroup$
    – Thorny
    Feb 5, 2010 at 12:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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