This is an item for math and logic puzzles.  Post 'em if you got 'em.

32 responses total.

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."

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.

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.

Grr.  Must find time to try this... 

OK, here's a "sub-puzzle":  If x yields y, what prefix p can you add to x so
that px yields y2 ?

2?  Or am I missing something?

 x -> y  ==> 474x -> y2   in these rules.

I've been conjecturing that it is likely that all of the rules are used 
at least once in the solution, simply because it's a manufactured 
problem.  I think I have some ideas about how prefixes 3, 4, and 7 get 
used, as well as 1 and 2, but I haven't really been able to get good 
ideas about 5 and 6 yet.  

There is at least on solution where not all of the rules are used.

Re #6,7: Flem is correct.  A string that begins with 2 would not be valid
input.

Re #7: Remember that there are 8 tests, so if you don't use all the rules on
the first one, you will get more chances to use them later.

Re #8: That's correct.  How do you know that, Paul?

OK, now that Greg has told us that x -> y implies 474x -> y2, what prefix q
could you add to x so that qx -> yy2 ?

4743x -> yy2

I know #8, because I found a specific solution.

Oh, I was under the impression that this particular set of rules applied 
only to the first test.  

Same rules for all 8 tests.  OK, so if 4743x -> yy2, then what about
47431x2 ?

As soon as someone posts a solution, I'll post the second test.

Ah, I see...

OK, would anyone like to post a solution?

I'll do the deed.

47431x2 -> xx2, so substituting 47431 for x, we get
  47431474312 -> 47431474312

Good!

For the second test, the suitor had to send the princess a number, x, such
that she would send back the repeat of x - the number xx.  What x would work?

View hidden response.

resp:17 contains a solution.  

For the third test, the suitor had to send the princess a number x such that
she would send back the reverse of x.  What number x would work?  An extra
bonus would be given if the number x contains no more than 12 digits.

Well, all valid inputs end with 2.  So if x produces the reverse of x, then
the reveres of x begins with a 2.  So it might be the case that the last thing
that happens is to tack a 2 onto the output.  I.e., x might begin with a 7.

This one was more difficult, but x = 745361745362 does the trick.  

Looks good.  734173412 also does it.

The Fourth Test:
For this test, the suitor had to send a number x such that the princess would
send back the number x with its last digit erased.  What x would work?

Ah.  I had figured out the 5361 sequence before I got around to playing with
4's.  I probably should have done the fours first, but... 

This one is pretty easy.  There's a 5 digit solution, which might not use the
techniques that the problem is designed for, but is correct.  
  I'm pretty sure that there's only one 5 digit solution, so this might 
be a pretty big hint, but I'll not post it just yet.  

I got a 5-digit solution too.  It's not the solution he gives in the book.

There's a class of solutions that are inputs of the form x31x312, where 
x meets some conditions.  The most obvious of these is where x = "", the 
empty string:  31312 -> 3131.  I'd be interested to see if the book 
gives any solutions not of this form.  

The solution in the book points out that 5361x2 yields x1x, so 53615362 yields
5361536.

I believe I can prove that 31312 is the only 5 digit solution.  (At least,
I think I proved it in the shower this morning, but I didn't write it down.)

The Fifth Test:

For this test, the suitor had to send a number x such that the princess would
send back a *different* number y, which the suitor was to send back to the
princess, and she would (hopefully) send back the first number x.

What number x would work?

The easy way (to prove that 31312 is the shortest input that satisfies 
test 4) would be exhaustive testing.  There aren't many valid inputs 
that are 5 digits or fewer:  x1yz2, where x is in { ,1,3,4,5,6,7}, 
and y and z are in { ,1,2,3,4,5,6,7}.  (y and z might possibly be 8,9, 
or 0; I don't recall if the rules allow that or not.)  That's only 
7*8*8 = 448 valid inputs of 5 digits or less.  (847 if y and z can be 
8, 9 or 0.)

It's OK to use digits 8, 9, and 0.  

Other valid 5-digit inputs look like xy1z2.  But the only ones of those with
4-digit outputs are 331x2, which produce xxxx, and therefore don't qualify.
The only way to get a 4-digit output from x1yz2 is if x is 3, and then you
have 31yz2, which produces yzyz.  So clearly 31312 is the only such which
produces itself minus its last digit.  So there you go.  :)

Hint on the 5th test (in #27): One way to do this one is to look for an input
x whose output is 1x2.

Here's another hint:
/---------------------------------------------\
| Find a prefix p such that px2 yields 1xx22. |
\---------------------------------------------/

We should try to wrap this up by the end of winter agora, so I'll solve test
number 5.  If p = 6477431, then px2 yields 1xx22, which in turn yields xx2.
So therefore pp2 yields 1pp22, which yields pp2.  So one solution is
/-----------------\
| 647743164774312 |
\-----------------/

Onward...

/-----------------------------------------------------\
| The Sixth Test:  The suitor had to send a number x, |
| get back a number y, return y to the princess, and  |
| get back the *reverse* of the original number x.    |
| What number x would work?                           |
\-----------------------------------------------------/

Response not possible - You must register and login before posting.

- Backtalk version 1.3.30 - Copyright 1996-2006, Jan Wolter and Steve Weiss