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

 
# syntax: GAWK -f SUM_AND_PRODUCT_PUZZLE.AWK
BEGIN {
    for (s=2; s<=100; s++) {
      if ((a=satisfies_statement3(s)) != 0) {
        printf("%d (%d+%d)\n",s,a,s-a)
      }
    }
    exit(0)
}
function satisfies_statement1(s,  a) { # S says: P does not know the two numbers.
# Given s, for all pairs (a,b), a+b=s, 2 <= a,b <= 99, true if at least one of a or b is composite
    for (a=2; a<=int(s/2); a++) {
      if (is_prime(a) && is_prime(s-a)) {
        return(0)
      }
    }
    return(1)
}
function satisfies_statement2(p,  i,j,winner) { # P says: Now I know the two numbers.
# Given p, for all pairs (a,b), a*b=p, 2 <= a,b <= 99, true if exactly one pair satisfies statement 1
    for (i=2; i<=int(sqrt(p)); i++) {
      if (p % i == 0) {
        j = int(p/i)
        if (!(2 <= j && j <= 99)) { # in range
          continue
        }
        if (satisfies_statement1(i+j)) {
          if (winner) {
            return(0)
          }
          winner = 1
        }
      }
    }
    return(winner)
}
function satisfies_statement3(s,  a,b,winner) { # S says: Now I know the two numbers.
# Given s, for all pairs (a,b), a+b=s, 2 <= a,b <= 99, true if exactly one pair satisfies statements 1 and 2
    if (!satisfies_statement1(s)) {
      return(0)
    }
    for (a=2; a<=int(s/2); a++) {
      b = s - a
      if (satisfies_statement2(a*b)) {
        if (winner) {
          return(0)
        }
        winner = a
      }
    }
    return(winner)
}
function is_prime(x,  i) {
    if (x <= 1) {
      return(0)
    }
    for (i=2; i<=int(sqrt(x)); i++) {
      if (x % i == 0) {
        return(0)
      }
    }
    return(1)
}
 