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

all      =.set~new
Call time 'R'
cnt.=0
do a=2 to 100
  do b=a+1 to 100-2
    p=a b
    if a+b>100 then leave b
    all~put(p)
    prd=a*b
    cnt.prd+=1
    End
  End
Say "There are" all~items "pairs where X+Y <=" max "(and X<Y)"
 
spairs=.set~new
Do Until all~items=0
  do p over all
    d=decompositions(p)
    If take Then
      spairs=spairs~union(d)
    dif=all~difference(d)
    Leave
    End
  all=dif
  end
Say "S starts with" spairs~items "possible pairs."
 
sProducts.=0
Do p over sPairs
  Parse Var p x y
  prod=x*y
  sProducts.prod+=1
  End
 
pPairs=.set~new
Do p over sPairs
  Parse Var p xb yb
  prod=xb*yb
  If sProducts.prod=1 Then
    pPairs~put(p)
  End
Say "P then has" pPairs~items "possible pairs."
 
Sums.=0
Do p over pPairs
  Parse Var p xc yc
  sum=xc+yc
  Sums.sum+=1
  End
 
final=.set~new
Do p over pPairs
  Parse Var p x y
  sum=x+y
  If Sums.sum=1 Then
    final~put(p)
  End
 
si=0
Do p Over final
  si+=1
  sol.si=p
  End
Select
  When final~items=1 Then Say "Answer:" sol.1
  When final~items=0 Then Say "No possible answer."
  Otherwise Do;            Say final~items "possible answers:"
                           Do p over final
                             Say p
                             End
    End
  End
Say "Elapsed time:" time('E') "seconds"
Exit
 
decompositions: Procedure Expose cnt. take spairs
  epairs=.set~new
  Use Arg p
  Parse Var p aa bb
  s=aa+bb
  take=1
  Do xa=2 To s/2
    ya=s-xa
    pp=xa ya
    epairs~put(pp)
    prod=xa*ya
    If cnt.prod=1 Then
      take=0
    End
  return epairs