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.

Puzzle[edit]

X and Y are two different integers, greater than 1, with sum less than or equal to 100. 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?

Solution[edit]

The solution has X and Y as 4 and 13 (or vice versa), 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.

Detailed solution[edit]

Mathematician P

P knows p=52. P suspects (2,26) and (4,13). P knows s=28 or s=17.

If s=28:

S would suspect (2,26), (3,25), (4,24), (5,23), (6,22), (7,21), (8,20), (9,19), (10,18), (11,17), (12,16), and (13,15).
S would know if (5,23) or (11,17), P would know the numbers.
S would not be able to say "P does not know X and Y."

If s=17:

S would suspect (2,15), (3,14), (4,13), (5,12), (6,11), (7,10), and (8,9).
S would know that P would not know the numbers.
S would be able to say "P does not know X and Y."

Therefore, when S says "P does not know X and Y", P eliminates (2,26) and learns (4,13) is the answer.

Mathematician S

S knows s=17. S suspects (2,15), (3,14), (4,13), (5,12), (6,11), (7,10), and (8,9). S knows p is 30, 42, 52, 60, 66, 70, or 72.

When P says "Then, I found these numbers," S knows his statement eliminated all but one possibility for P.

S simulates P's thinking

Only Case 3 eliminates all but one possibility for P. This is how S decides (4,13) is the answer.


The above solution is a verification, not a solution. It verifies that if P is given 52 and S is given 17, then P would could know and S would know. But, it has not established that (4,13) is the only answer. After the second question is answered, (i.e. S saying "I know you couldn't know"), is 52 necessarily the product P was given?

The answer to this is yes. An excel spreadsheet can be used to find the solution.

If x and y are the numbers, the two equations are x+y=S and xy=P. Solving for y and substituting gives x2-Sx+P=0

The excel spreadsheet looks for integer solutions for each S and P. Column B contains the sums (starting at row 4), row 3 contain the products (starting at C). A large table is created with sums down the side and products across the top. Sums can count by 2, displaying only the odd sums.

Formula in the middle of a large table is:

IF($B4^2-4*C$3>0,($B4+SQRT($B4^2-4*C$3))/2,"") $B4 is the sum at left, S. C$3 is the product at top, P. (The dollar signs allow copying to the right and down, fixing the references to S and P)

The formula refers to the quadratic formula, which says if b2-4ac is positive, show the solution for x (one of the numbers), otherwise leave blank. The formula gives the largest of the two factors of the product.

The above formula shows decimal factors, so another IF statement can filter out the non-integers. The easiest thing to do is to use a second table that refers to the first with this formula:

IF($B56<>C$55+1,IF(C4<>"",IF(INT(C4)<>C4,"",C4),""),"") This filters out one group of impossible answers, and puts either a blank or the original integer into the parallel table. The net results is only integer value factors showing for each S and P.

It turns out that every row for a sum that's 2 past a prime represents a sum where S would not be sure that P can't know. That's because for such a row, the a possible product exists that would be 2 x prime #, and S would have to credit P with knowing the two factors. Ignore such rows.

Along the row for sum 17 under product 52 is the number 13. There are no other numbers in the same column that have odd factors for 52, and 13 is the only number for which this is the case.

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 }
  println(step4)
}


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]

References[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]