XSB Mister X

Although this problem has a straightforward solution, it does demonstrate the value of thinking deductively to understand the problem, which relates to “don't know” nondeterminism, and an appropriate use of lemmas.

Problem:

Problem as posted to comp.lang.prolog by Thorsten Seelend. Also known as Hans Freudenthal's Impossible Puzzle.

Mister X thinks about two integers between 1 and 100 excluding:

MISTERX: Two integers, X and Y between 2 and 99 (My formalization of the given information)

two_integers( X, Y ) :-
    between( 2, 98, X ),
    between( X, 99, Y ).

He tells Susan the Sum of them and Peter their Product. Their task is to get the two original values without telling each other the numbers that Mister X told them.

After some time Peter says: “I can't say definitively which are the original numbers.”

PETER1: There is more than one pair of factors giving Product

:- table peter1/1.
 
peter1( Product ) :-
    \+ unique_factors( Product ).

Then Susan responds: “Neither can I, but I knew that you couldn't know it.”

SUSAN1: The product of every pair of summands giving Sum has the property PETER1

:- table susan1/1.
 
susan1( Sum ) :-
    forall( ordered_summands(Sum, X, Y), peter1(X * Y) ).

Peter: “Really? So now I know the original numbers”.

PETER2: exactly one pair of factors giving Product gives a sum with the property SUSAN1

:- table peter2/1.
 
peter2( Product ) :-
    unique_solution( (ordered_factors(Product, X, Y), susan1(X+Y)) ).

Susan: “Now I know them too”.

SUSAN2: exactly one pair of summands giving Sum has a product with the property PETER2

:- table susan2/1.
 
susan2( Sum ) :-
    unique_solution( (ordered_summands(Sum, X, Y), peter2(X * Y)) ).

Question: What are the two numbers that Mister X thought of?

Unique solution

solve( X, Y ) :-
    unique_solution( mister_x(X, Y) ).

mister_x( X, Y ) :-
    two_integers( X, Y ),
    Sum is X + Y,
    Product is X * Y,
    peter1( Product ),
    susan1( Sum ),
    peter2( Product ),
    susan2( Sum ).

Supporting Predicates

ordered_summands( +Sum, ?X, ?Y )

when X ≤ Y and Sum = X+Y. NB: Since X≤Y it follows that X ≤ Sum/2.

ordered_summands( Z, X, Y ) :-
    Half is Z//2,
    between( 2, Half, X ),
    Y is Z - X,
    between( X, 98, Y ).

ordered_factors( +Product, ?X, ?Y )

when X ≤ Y and Product = X × Y. NB: Since X≤Y it follows that X ≤ √Product.

ordered_factors( Z, X, Y ) :-
    integer_sqrt( Z, SqrtZ ),
    between( 2, SqrtZ, X ),
    Y is Z // X,
    between( X, 99, Y ),
    Z =:= X * Y.

unique_factors( +Product )

when Product has exactly one pair of factors.

unique_factors( Product ) :-
    ordered_factors( Product, X, _Y ),
    \+ (ordered_factors(Product, X1, _Y1), X1 =\= X).

integer_sqrt( +N, ?Sqrt )

when Sqrt² ≤ N < (Sqrt+1)².

integer_sqrt( N, Sqrt ) :-
    Float is N * 1.0,
    sqrt( Float, FSqrt ),
    Sqrt is integer(FSqrt).

Load a small library of Puzzle Utilities.

:- ensure_loaded( misc ).

The code is available as plain text here.

Result

This program finds X and Y as 4 and 13.

Tabling

Using tabling, rather than explicit lemmas, can simplify code. A version adapted for XSB Prolog is available here.