Solving the Impossible Puzzle (with code)

Also known as the Sum and Product Puzzle, the Impossible Puzzle is a logic puzzle that requires you to determine two numbers based on some constraints and a conversation between a pair of people: one who knows only the sum of the two numbers, and another who knows only their product. The puzzle may seem impossible to solve at first, but it’s not, and in this article we’ll walk through some (Python) code that does just that.

The Puzzle

x and y are whole numbers each greater than 1, where y is greater than x, and the sum of the two is less than or equal to 100.

• y > x > 1
• x + y ≤ 100

Sam knows only the sum of the two numbers (x + y), while Peter knows only their product (x * y). The following conversation takes place between them.

Sam: “I don’t know x and y, and I know that you don’t know them either.”

Peter: “I now know x and y.”

Sam: “I also now know x and y.”

The question: What are x and y?

The Solution

First, let’s import some convenient libraries and set some initial variables for the constraints on x and y.

`import jsonfrom collections import OrderedDict# Set initial variablesMIN_X = 2MAX_SUM = 100# Determine range of possible values for xMAX_X = MAX_SUM/2–1  # since y > x, x < MAX_SUM/2X_RANGE = range(MIN_X, MAX_X+1)  # 2 to 49, inclusive`

Next, we build a list of possible and impossible products based on Sam’s first assertion that Peter does not know the two numbers. This assertion entails that the product cannot be uniquely reached (otherwise Peter would know the two numbers), i.e. there have to be multiple factor pairs that can be multiplied to reach the product.

`# Build possible_products and impossible_products with products that cannot and can be reached uniquelyproduct_range = range(MIN_X*(MIN_X+1), MAX_X*(MAX_X+1))possible_products = OrderedDict()impossible_products = OrderedDict()for p in product_range:  factor_pairs = []  for x in X_RANGE:    for y in range(x+1, MAX_SUM-x+1):      if x*y == p:        factor_pairs.append((x, y))  if len(factor_pairs) > 1:    possible_products[p] = factor_pairs  elif len(factor_pairs) == 1:    impossible_products[p] = factor_pairs[0]`

We can also determine from Sam’s first assertion that his sum cannot be broken into factors of any impossible product, which we can use to build a list of possible sums.

`# Build possible_sums, remove sums of impossible product factor pairspossible_sums = range(MIN_X+MIN_X+1, MAX_SUM+1)for x,y in impossible_products.values():  if x+y in possible_sums:    possible_sums.remove(x+y)`

Next, we only keep products that can be reached by multiplying components of this list of possible sums, and also employ Peter’s assertion that he now knows the two numbers by further only keeping products that have exactly one factor pair remaining.

`# Only keep products in possible_products that can be reached from possible_sumsfor p, pairs in possible_products.items():  i = 0  while i < len(pairs):    if pairs[i][0] + pairs[i][1] not in possible_sums:      del pairs[i]      i -= 1    i += 1  if len(pairs) != 1:    del possible_products[p]`

We can now employ Sam’s last assertion that he also now knows the two numbers by counting the number of occurrences of each sum to find the one that only has a single occurrence.

`# Find occurrences of each sumsum_occurs = OrderedDict()for p, pairs in possible_products.items():  for x, y in pairs:    s = x + y    if s in sum_occurs:      sum_occurs[s].append((x, y))    else:      sum_occurs[s] = [(x, y)]`

And finally, we can look up the components of the singly occurring sum to arrive at our answer for x and y: 4 and 13.

`# Find and print the answer, the sum with only a single occurrenceprint([components for s, components in sum_occurs.items() if len(sum_occurs[s]) == 1][0][0])> (4, 13)`

More Possibilities

This puzzle has different solutions for different constraints on x and y, e.g.

• y > x > 2
• x + y ≤ 125

The same code can also be used to solve the puzzle with these constraints by simply adjusting the initial variables as follows.

`MIN_X = 3MAX_SUM = 125`

Re-running the rest of the code yields 13 and 16 for x and y.

Note that this problem isn’t solvable with just any constraints, in which cases it’s actually impossible :)

Working @ aramse.io, delivering cloud-native solutions to help companies streamline DevOps

More from Shubham Sakhuja

Working @ aramse.io, delivering cloud-native solutions to help companies streamline DevOps

Solving Optimization Problems with JAX

Get the Medium app