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

 
(import (scheme base)
        (scheme cxr)
        (scheme write)
        (srfi 1))
 
;; utility method to find unique sum/product in given list
(define (unique-items lst key)
  (let ((all-items (map key lst)))
    (filter (lambda (i) (= 1 (count (lambda (p) (= p (key i)))
                                    all-items)))
            lst)))
 
;; list of all (x y x+y x*y) combinations with y > x
(define *xy-pairs* 
  (apply append
         (map (lambda (i)
                (map (lambda (j)
                       (list i j (+ i j) (* i j)))
                     (iota (- 98 i) (+ 1 i))))
              (iota 96 2))))
 
;; S says "P does not know X and Y"
(define *products* ; get products which have multiple decompositions
  (let ((all-products (map fourth *xy-pairs*)))
    (filter (lambda (p) (> (count (lambda (i) (= i p)) all-products) 1))
            all-products)))
 
(define *fact-1* ; every x+y has x*y in *products*
  (filter (lambda (i) 
            (every (lambda (p) (memq (fourth p) *products*))
                   (filter (lambda (p) (= (third i) (third p))) *xy-pairs*)))
          *xy-pairs*))
 
;; P says "Now I know X and Y"
(define *fact-2* ; find the unique X*Y
  (unique-items *fact-1* fourth))
 
;; S says "Now I also know X and Y"
(define *fact-3* ; find the unique X+Y
  (unique-items *fact-2* third))
 
(display (string-append "Initial pairs: " (number->string (length *xy-pairs*)) "\n"))
(display (string-append "After S: " (number->string (length *fact-1*)) "\n"))
(display (string-append "After P: " (number->string (length *fact-2*)) "\n"))
(display (string-append "After S: " (number->string (length *fact-3*)) "\n"))
(display (string-append "X: " 
                        (number->string (caar *fact-3*))
                        " Y: "
                        (number->string (cadar *fact-3*))
                        "\n"))
 