aruba
|
|
response 1 of 32:
| 
Feb 19 20:47 UTC 2000 |
I'm a big fan of Raymond Smullyan's logic puzzles. I've been working through
one of his recent books, called "The Riddle of Scheherazade". The premise is
that after the 1001st night, Scheherazade went on to tell the king puzzles for
several subsequent nights. On the thousand and thirteenth night, she gets to
this one:
A certain prince Al-Khizr was in love with the sultan's daughter and asked for
her hand in marriage.
"My daughter is very choosy," said the sultan, "and wants to marry only
someone who shows extraordinary intelligence. So if you want to marry her,
you must first pass eight tests."
"What are the tests?" asked the suitor.
"Well, for the first test, you have to write down a number that will be sent
to the princess. She will then send back a number to you. If she sends back
the very same number that you have sent her, then she will allow you to take
the second test. But if her number is different from yours, then you are
out."
"Now, how can I possibly know what number to write?" asked the suitor. "How
can I guess what number the princess has in mind?"
"Oh, she doesn't have a number in mind," said the sultan. "The number she
sends back is dependent on the number you send. The number you send
*completely determines* what number she will send back. And if you send the
right number, she will send back the same number."
"Then how can I guess the right number?" asked the suitor.
"It's not a matter of *guessing*," said the sultan. You must *deduce* the
correct number from the rules I am about to give you. For any numbers x and
y, by xy I mean not x *times* y but x *followed by* y, both numbers, of
course, written in base 10 Arabic notation. For example, if x is 5079 and y
is 863, then by xy I mean 5079863. Now here are the rules:
Rule 1: For any number x, if you send her 1x2, then she will send you back the
number x. For example, if you write 13542, she will write back 354.
Rule 2: For any number x, the *repeat* of x means xx. For example, the repeat
of 692 is 692692. And now, the second rule is that if x brings back y, then
3x will bring back the repeat of y. For example, since 15432 brings back 543,
then 315432 will bring back 543543. From which it further follows that if you
send her 3315432, you will get back 543543543543 (since 315432 brings back
543543).
Rule 3: The *reverse* of a number means the number written backwards. For
example, the reverse of 62985 is 58926. The third rule is that if x brings
back y, then 4x brings back the reverse of y. For example, since 172962
brings back 7296, then 4172962 brings back 6927. Thus, if you send her the
number 4172962, you will get back 6927. Or, combining Rules 1, 2, and 3,
since 316982 brings back 698698 (by Rules 1 and 2), then 4316982 brings back
896896.
Rule 4 (The Erasure rule): If x brings back y, and if y contains at least 2
digits, then 5x brings back the result of erasing the first digit of y. For
example, since 13472 brings back 347, then 513472 brings back 47.
Rule 5 (The Addition Rule): If x brings back y, then 6x brings back 1y and 7x
brings back 2y. For example, since 15832 brings back 583, then 615832 brings
back 1583, and 715832 brings back 2583.
"Those are the rules," said the sultan, "and from them can be deduced a number
x that will bring back the very number x. There are actually an infinite
number of solutions, but any single one will suffice for passing the first
test."
"Are there any *meanings* to these numbers?" asked the suitor.
"Ah, that is the princess' secret, but fortunately you don't have to know the
meaning in order to pass the first test."
|
aruba
|
|
response 2 of 32:
|
Feb 19 20:51 UTC 2000 |
I wrote a simulation of this puzzle in C. You can try out numbers by running
~aruba/bin/smullyan and passing numbers on the command line. For instance,
Ok: !~aruba/bin/smullyan 341232
produces the output:
341232 yields 3232
If you run the program with no parameters, it gives a summary of the
rules:
1. 1x2 yields x, for any number x.
(For the rest of the rules, assume that x yields y.)
2. 3x yields yy.
3. 4x yields the reverse of y (i.e., y written backwards.)
4. 5x yields cdr(y), i.e., y without its first digit.
5. 6x yields 1y.
6. 7x yields 2y.
If there's sufficient interest, I can ask someone to put the simulation in a
more convenient place.
|
aruba
|
|
response 3 of 32:
|
Feb 21 22:41 UTC 2000 |
OK, here are some hints. Clearly every valid input looks like this:
x1y2
where x is a sequence of digits taken from { 3,4,5,6,7 }, and y is any string
of digits. You can think of starting with 1y2, and then tacking digits on
to the beginning until you get what you want for output. Note that if
d = length of input - length of output
then d starts out at 2. Tacking on a 4 increases d by 1, a 5 increases it
by 2, and a 6 or a 7 leaves it unchanged. So the only way to decrease d is
by tacking on a 3. Since d starts out at 2 and you want it to be 0, it
follows that you need to use at least one 3.
|
