Sum and Product Puzzle

From Wikipedia, the free encyclopedia
  (Redirected from Impossible Puzzle)
Jump to: navigation, search

The Impossible Puzzle, also named Sum and Product Puzzle is a puzzle called "impossible" because it seems to lack sufficient information for a solution. It was first published in 1969 by Hans Freudenthal,[1] and the name Impossible Puzzle was coined by Martin Gardner.[2] The puzzle is solvable, though not easily. There exist many similar versions of puzzles.


X and Y are two different integers, greater than 1, with sum less than or equal to 100, with Y greater than X. S and P are two mathematicians; S knows the sum X+Y, P knows the product X*Y, and both are perfect logicians. Both S and P know the information in these two sentences. 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?


The solution has X and Y as 4 and 13, with P initially knowing the product is 52 and S knowing the sum is 17.

Initially P does not know the solution, since

52 = 4 × 13 = 2 × 26

and S knows that P does not know the solution since all the possible sums to 17 within the constraints produce similarly ambiguous products. However, each can work out the solution by eliminating other possibilities following the other's statements and that is enough for the reader to find the solution given the constraints.

Python code[edit]

Here is a Python program that proves that the above solution is unique.

from collections import Counter

all_pairs=set((a,b) for a in range(2,100) for b in range(a+1,100) if a+b<100)
def decompose_sum(s):
    return [(a,s-a) for a in range(2,int(s/2+1))]
_prod_counts=Counter(a*b for a,b in all_pairs)
unique_products=set((a,b) for a,b in all_pairs if _prod_counts[a*b]==1)
# Find all pairs, for which no sum decomposition has unique product
# In other words, for which all sum decompositions have non-unique product
s_pairs=[(a,b) for a,b in all_pairs if
    all((x,y) not in unique_products for (x,y) in decompose_sum(a+b))]
# Since product guy now knows, possible pairs are those out of above for which product is unique
product_pairs=[(a,b) for a,b in s_pairs if Counter(c*d for c,d in s_pairs)[a*b]==1]
# Since the sum guy now knows
final_pairs=[(a,b) for a,b in product_pairs if Counter(c+d for c,d in product_pairs)[a+b]==1]
print(final_pairs) # [(4, 13)]

Scala code[edit]

Here is a Scala program that proves that the above solution is unique.

object ImpossiblePuzzle extends App {
  type XY = (Int, Int)
  val step0 = for {
    x <- 1 to 100
    y <- 1 to 100
    if 1 < x && x < y && x + y < 100
  } yield (x, y)

  def sum(xy: XY) = xy._1 + xy._2
  def prod(xy: XY) = xy._1 * xy._2
  def sumEq(xy: XY) = step0 filter { sum(_) == sum(xy) }
  def prodEq(xy: XY) = step0 filter { prod(_) == prod(xy) }
  val step2 = step0 filter { sumEq(_) forall { prodEq(_).size != 1 }}
  val step3 = step2 filter { prodEq(_).intersect(step2).size == 1 }
  val step4 = step3 filter { sumEq(_).intersect(step3).size == 1 }

Mathematica code[edit]

Here is a Mathematica program that proves that the above solution is unique.

(* Store possible pairs in the form {x,y,x+y,x*y}. *)
n = 100;
t = Table[{x,y,x+y,x y},{x,n},{y,n}] // Flatten[#,1] &;
keep[tup_] :=  Module[{ x=tup[[1]], y=tup[[2]], xpy=tup[[3]] }, x<y && x!=y && x>1 && y>1 && xpy<=100]
t2 = Select[t,keep];

(* Partition the pairs by "same sum" (partition A) and "same product" (partition B). *)
A = GatherBy[t2, #[[3]] & ];
B = GatherBy[t2, #[[4]] & ];

(* For each singleton set in B, find it in A and delete the entire subset. *)
Bsingletons = Select[B, Length[#]==1 & ]  //  Flatten[#,1]&;
deleteThese = Select[A, MemberQ[#, Alternatives@@Bsingletons ]& ]  //  Flatten[#,1]&;
A2 = DeleteCases[A, Alternatives@@deleteThese, Infinity];
B2 = DeleteCases[B, Alternatives@@deleteThese, Infinity];

(* For each non-singleton set in B2, delete all its elements from A2. *)
Bnonsingletons = Select[B2, Length[#]>1 & ]  //  Flatten[#,1]&;
A3 = DeleteCases[A2, Alternatives@@Bnonsingletons, Infinity];

(* Now A3 should have only one singleton set left -- the answer. *)
Select[A3, Length[#]==1 & ] 

(* Returns {4,13,17,52} : the two numbers, their sum, and their product. *)

See also[edit]


  1. ^ Hans Freudenthal, Nieuw Archief Voor Wiskunde, Series 3, Volume 17, 1969, page 152
  2. ^ Gardner, Martin (December 1979), "Mathematical Games: A Pride of Problems, Including One That Is Virtually Impossible", Scientific American 241: 22–30 .

External links[edit]