Sum and Product Puzzle

The Sum and Product Puzzle, also known as the Impossible Puzzle because it seems to lack sufficient information for a solution, is a logic puzzle. 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

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:

What are X and Y?

Solution

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

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

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

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).

(* 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. *)

MATLAB code

Here is a MATLAB program to verify the pair is unique.

[x,y] = ndgrid(2:100 ,2:100);
ind=triu(true(size(x)),1);  % indices which satisfy x<y
x=x(ind);y=y(ind);

A = sparse(x+y, x.*y,1); % create (sparse) array with potential (sum,product) pairs
clear x,y;
A(101:end,:) = []; % x+y <= 100

% OK, let's start processing
pn = sum(A) == 1;% P knows the number
sn = A * pn' > 0; % S does not know P does not know the number
A(sn,:) = 0; % clear entries which do not meet the first condition
pn = sum(A) > 1; % P does not now know the number
A(:,pn) = 0; % clear entries which do not meet the second condition
sn = sum(A,2) > 1; % S does not now know the number
A(sn,:) = 0; % clear entries which do not meet the third condition
[s, p] = find(A); % find non-zero entries
dis = (s.^2 - 4*p) .^ (1/2); % dis = ((x+y)^2-4xy)^.5 = |x-y| = y-x
[(s-dis)/2  (s+dis)/2] % display x and y as an r by 2 array, where r is the number of solutions.

See also

References

  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

This article is issued from Wikipedia - version of the Friday, May 06, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.