(Puzzle by Raymond Smullyan)

There is a safe containing millions of dollars – unfortunately the combination is written on only one card, and that card has been accidentally locked inside the safe! If the wrong combination is used, the lock will jam and the only way to open the safe would be to blow it up, destroying the contents.

A combination is a string of digits from 0 through 9. It can be any length and contain any number of digits occurring any number of times; 90915 is a combination; so is 2133127; so is 5. Certain combinations will open the lock, certain combinations will jam the lock, and the remaining combinations will have no effect whatever (these last are called neutral).

The small letters x and y will represent arbitrary combinations, and by xy is meant the combination x followed by the combination y; for example, if x is 213 and y is 3812, then xy is 2133812. By the reverse of a combination is meant the combination written backwards; for example, the reverse of 3812 is 2183. By the repeat xx of a combination x is meant the combination followed by itself; for example, the repeat of 3182 is 31823182.

Now, some of the combinations are related to other combinations. There are five properties of this relation:

Property A: For any combination x, the combination 2x2 is related to x. (For example, 21452 is related to 145.)

Property B: If x is related to y, then 1x is related to 2y. (For example, since 21452 is related to 145, then 121452 is related to 2145.)

Property C: If x is related to y, then 5x is related to the reverse of y. (For example, since 21452 is related to 145, then 521452 is related to 541.)

Property D: If x is related to y, then 9x is related to yy (the repeat of y).(For example, since 21452 is related to 145, then 921452 is related to 145145. Also, 521452 is related to 541, so 9521452 is related to 541541.)

Property E: If x is related to y, then if x is neutral then y jams the lock, and if x jams the lock then y is neutral. (For example, if 521452 is neutral, then 541 will jam the lock.)

Find the shortest possible combination that will open the lock.

Notes/Clues:
a) The relation is only one way. Think of it like mother and son. The mother is the parent of the son, but the son is not the parent of the mother.
b) The first thing you need to do is to establish (just using property E) how to solve the puzzle (i.e. how do you know if a combination opens the lock?). Then use this information to solve the puzzle using properties A thru D.

There is no way stated to prove that a combination opens the safe. The problem does say that any combination does one of 3 things: open or jam the lock or do nothing. Therefore, the only way to show that a combination opens the lock is to disprove either other case. Using property E, that will work when a combination is related to itself.

The only way to 'start' a relation is using property A, that 2x2 is related to x. For simpler notation, write that as 2x2 ~ x. Any number of subsequent trasformations will only form a prefix of 1s, 5s, and 9s to the 2x2 while changing the x somehow. Call that combination y, and you have:
y2x2 ~ y(x)
where y(x) is the result of x after having done all the transformations enumerated by the digits of y. We are trying to find a number related to itself, so y(x) must be equal to y2x2. The shortest way to do this would most likely be if
y(x)=xx2
or
y(x)=x2x2.

We can get either of these results from the transformations described above, and it is rather simple to determine the steps of y needed to get there from x.
Working with backwards transformations from xx2 we get:
xx2-2xx-xx-x
So, the steps must have been:
2x2 ~ x
92x2 ~ xx
192x2 ~ 2xx
5192x2 ~ xx2
:. x = 5192, and we have shown that
519251922 ~ 519251922.

Now to try x2x2-2x2x-2x-x we can establish:
2x2 ~ x
12x2 ~ 2x
912x2 ~ 2x2x
5912x2 ~ x2x2
:. x=591, and we have shown that
59125912 ~ 59125912.
This is shorter than the previous solution, and the shortest I could come up with.

Posted by DJ on 2003-03-03 17:51:08