Task[edit]
Solve the "Impossible Puzzle":


X and Y are two different whole numbers greater than 1. Their sum is no greater than 100, and Y is greater than X. S and P are two mathematicians (and consequently perfect logicians); S knows the sum X+Y and P knows the product X*Y. Both S and P know all the information in this paragraph.
The following conversation occurs:

 S says "P does not know X and Y."
 P says "Now I know X and Y."
 S says "Now I also know X and Y!"
What are X and Y?


Guidance
It can be hard to wrap one's head around what the three lines of dialog between S (the "sum guy") and P (the "product guy") convey about the values of X and Y.

So for your convenience, here's a break-down:





 Quote

 Implied fact


 1)

 S says "P does not know X and Y."

 For every possible sum decomposition of the number X+Y, the product has in turn more than one product decomposition.


 2)

 P says "Now I know X and Y."

 The number X*Y has only one product decomposition for which fact 1 is true.


 3)

 S says "Now I also know X and Y."

 The number X+Y has only one sum decomposition for which fact 2 is true.

Terminology:

 "sum decomposition" of a number = Any pair of positive integers (A, B) so that A+B equals the number. Here, with the additional constraint 2 ≤ A < B.
 "product decomposition" of a number = Any pair of positive integers (A, B) so that A*B equals the number. Here, with the additional constraint 2 ≤ A < B.


Your program can solve the puzzle by considering all possible pairs (X, Y) in the range 2 ≤ X < Y ≤ 98, and then successively eliminating candidates based on the three facts. It turns out only one solution remains!

See the Python example for an implementation that uses this approach with a few optimizations.

See also
   Wikipedia:   Sum and Product Puzzle

#lang racket
(define-syntax-rule (define/mem (name args ...) body ...)
  (begin
    (define cache (make-hash))
    (define (name args ...)
      (hash-ref! cache (list args ...) (lambda () body ...)))))
 
(define (sum p) (+ (first p) (second p)))
(define (mul p) (* (first p) (second p)))
 
(define (sum= p s) (filter (lambda (q) (= p (sum q))) s))
(define (mul= p s) (filter (lambda (q) (= p (mul q))) s))
 
(define (puzzle tot)
  (printf "Max Sum: ~a\n" tot)
  (define s1 (for*/list ([x (in-range 2 (add1 tot))]
                         [y (in-range (add1 x) (- (add1 tot) x))])
               (list x y)))
  (printf "Possible pairs: ~a\n" (length s1))
 
  (define/mem (sumEq/all p) (sum= p s1))
  (define/mem (mulEq/all p) (mul= p s1))
 
  (define s2 (filter (lambda (p) (andmap (lambda (q)
                                           (not (= (length (mulEq/all (mul q))) 1)))
                                         (sumEq/all (sum p))))
                     s1))
  (printf "Initial pairs for S: ~a\n" (length s2))
 
  (define s3 (filter (lambda (p) (= (length (mul= (mul p) s2)) 1))
                   s2))
  (displayln (length s3))
  (printf "Pairs for P: ~a\n" (length s3))
 
  (define s4 (filter (lambda (p) (= (length (sum= (sum p) s3)) 1))
                     s3))
  (printf "Final pairs for S: ~a\n" (length s4))
 
  (displayln s4))
 
(puzzle 100)