The Mysterious Lock of Monte Carlo

Chapters 8 and 13 from [The Lady or the Tiger]

Here is a [calculational solution] to this problem. This puzzle was also published as Weekly Puzzle 32: The Lock on The Weekly Puzzles. In this solution I will use that version.


We use the following abbreviations for statements about combinations:
  O.x == "x opens the lock"
  N.x == "x is neutral"
  J.x == "x jams the lock"
x and y represent combinations; a combination is a non-empty digit sequence. p and q represent (possibly empty) digit sequences. We also introduce the following notations for sequences:
  p = q == "p and q contain the same digits in the same order"
  <p> = "the sequence that is the reverse of p"
So for example <1233> = 3321.

The crucial notation that we introduce is:

  [x] = "the combination to which x is related"
In terms of the machines in Chapters 9 through 13 in [The Lady or the Tiger], [x] is the output of the machine for input x.


Using these notations we can represent the five properties as follows:
 (A)  [2x2] = x
 (B)  [1x] = 2[x]
 (C)  [5x] = <[x]>
 (D)  [9x] = [x][x]
 (E1) N.x => J.[x]
 (E2) J.x => N.[x]
We are also given that
 (Z)  exactly one of O.x, N.x, and J.x is true
One consequence of this (see my discussion of [Trilemmas]) is:
 (Z1) O.x == N.x == J.x
All these properties hold for all combinations x.

The problem is now to find the shortest x for which O.x.

Step 1

For any combination x:
==   "(Z1)"
   N.x == J.x
==   "logic, working towards (E1) and (E2)"
   (N.x => J.x) /\ (J.x => N.x)
<=   "(E1); (E2)"
   [x] = x
So any combination that is related to itself will open the lock.

Intermezzo: operations

Properties (A)-(D) allow us to simplify values of form [...]. But it is easy to see that they only work for values of the form [m2x2], where x is an arbitrary combination, and m is a (possibly empty) sequence of 1s, 5s, and 9s. For reasons that will become clear in a moment, we call each of those digits an 'operation digit'; n stands for an arbitrary operation digit. m is an 'operation sequence', i.e., a (possibly empty) sequence of operation digits.

Because expressions of the form [m2x2] occur often, we introduce a special notation:

  m.x = [m2x2]
We use a function-application notation here, with a reason. Let's compute 1.x:
=    "definition of ."
=    "(B)"
=    "(A)"
When we do this also for 5 and 9, we get
 (B') 1.x = 2x
 (C') 5.x = <x>
 (D') 9.x = xx
So we see that these digits are operations: 1 prepends a 2, 5 reverses, and 9 duplicates a digit sequence.

We can also combine operations:

 (*)  n.(m.x) = nm.x
We prove this only for n=1; the other proofs are similar.
=    "(B')"
=    "definition of ."
=    "(B) from right to left"
=    "definition of ."
To give a simple example, it is easy to compute that
=    "(*) from right to left"
=    "(B')"
=    "(C')"
In the next step we will perform a similar situation, but then from bottom to top.

Step 2

Armed with the knowledge about operations, we continue our quest for a self-related combination.
   [x] = x
<=   "write x as m2y2"
   (Em,y| x = m2y2: [m2y2] = m2y2)
Now we would like to write m2y2 as an operation on m and y. Since we know that we have a duplication operation, it seems that m2m2 is easier to rewrite. Therefore we calculate:
=    "(D') from right to left"
=    "definition of <...>, to put the 2 up front"
=    "(C') from right to left"
=    "(B') from right to left"
=    "(C') from right to left"
=    "(*), three times"
=    "definition of ."
With this we can continue our earlier calculation:
   (Em,y| x = m2y2: [m2y2] = m2y2)
<=   "take y:=m"
   (Em| x = m2m2: [m2m2] = m2m2)
==   "proof above"
   (Em| x = m2m2: [m2m2] = [95152m2])
<=   "Leibniz' rule"
   (Em| x = m2m2: m2m2 = 95152m2)
==   "remove 2m2 at the end"
   (Em| x = m2m2: m = 9515)
==   "one-point rule"
   x = 9515295152
Summarizing the complete calculation, we proved
  (Ax| x = 9515295152: O.x)
or equivalently O.9515295152. And this is a combination that opens the lock. I also believe this to be the shortest one, but have not been able to prove that.

Post Scriptum

It was only after I wrote the above, and contacted Tim Edmonds of The Weekly Puzzles about this solution, that I saw his. It turned out that there is a shorter combination; here is a calculational explanation.

Because of (Z) we know that a combination opens the lock iff it is not neutral and also doesn't jam it. In other words,

 (Z2) O.x == !J.x /\ !N.x
(This is another consequence of (Z): see [Trilemmas].) This allows us to prove a statement of the form O.x as follows:
==   "(Z2)"
   !J.x /\ !N.x
<=   "(E1) and (E2) from right to left"
   !N.[x] /\ !J.[x]
==   "(Z2) from right to left"
Applying this to the combination that we already found, and abbreviating m = 9515, we get
   O.m2m2                            --- already proved above
==   "(D') from right to left"
==   "definition of ."
=>   "the property we've just proven"
So 92951522 is also a working combination, and it is shorter that the one I (and Smullyan) found. Again, I cannot prove that it is the shortest.
This page is brought to you by Marnix Klooster, and is part of his home page. Feel free to e-mail me with comments on the form and content of this page.
Changes to calc/tlott-8-and-13.html:

Sat Oct 30 12:38:39 MEST 2004  Marnix Klooster
  * Move from CVS to darcs: do not show the CVS date anymore.

Thu Feb  7 19:43:35 MET 2002  marnix
  * Updated all files to use the m4 template

Wed Sep  5 21:20:00 MEST 2001  marnix
  * Made explicit that last changed date is in GMT

Wed Sep  5 21:08:51 MEST 2001  marnix
  * Now 'last changed' is on its own line

Wed Sep  5 10:10:47 MEST 2001  marnix
  * Added date last changed

Wed Sep  5 08:50:24 MEST 2001  marnix
  * Initial revision