I saw a math puzzle the other day on Hacker News. It reads as follows:

Two numbers are chosen randomly, both are positive integers smaller than 100. Sandy is told the sum of the numbers, while Peter is told the product of the numbers.

Then, this dialog occurs between Sandy and Peter:

Peter: I don’t know the numbers.
Sandy: I don’t know the numbers.
Peter: I don’t know the numbers.
Sandy: I don’t know the numbers.
Peter: I don’t know the numbers.
Sandy: I don’t know the numbers.
Peter: I don’t know the numbers.
Sandy: I don’t know the numbers.
Peter: I don’t know the numbers.
Sandy: I don’t know the numbers.
Peter: I don’t know the numbers.
Sandy: I don’t know the numbers.
Peter: I don’t know the numbers.
Sandy: I don’t know the numbers.

Peter: I do know the numbers.

What are the numbers?

At first glance this looks impenetrable, but I’d encourage you to give it a think if you’d like to. I’ll be walking through exactly how it works and how to solve it (with the help of a computer).

Spoilers below, be warned

Again, at first glance, it doesn’t look like any of this information would be helpful, but the trick is that each time they say they don’t know the answer, the other party is able to narrow down the options for what the numbers could be. If you do this enough times, there’s only one pair of numbers left, at which point Peter knows the answer.

I found it helpful to think about this in a few different ways. First, let’s say we have a list of all of the pairs of numbers – we can think about those as our candidates. To simplify, let’s say that the order doesn’t matter ((1, 2) is the same as (2, 1)) and we just keep track of one of the duplicates.

candidates: [
  (1, 1),
  (1, 2),
  (1, 3),
  (1, 4),
  ...
  (99, 99)
]

Let’s also imagine a big representation of all of the possible sums and products and the pairs of numbers that make up those sums and products. Let’s say they’re maps, where the keys are the sums/products and the values are lists of the pairs that make up those sums/products. Furthermore, let’s say that both Sandy and Peter have full knowledge of these maps.

sums: {
  2: [(1, 1)],  # The only pair that adds up to 2 is (1, 1)
  3: [(1, 2)],
  4: [(1, 3), (2, 2)],  # For 4, we have two pairs: (1, 3) and (2, 2)
  5: [(1, 4), (2, 3)],
  6: [(1, 5), (2, 4), (3, 3)],
  # And so on.
  ...
  198: [(99, 99)]
}

products: {
  1: [(1, 1)],  # The only pair that multiply together to make 1 is (1, 1)
  2: [(1, 2)],
  3: [(1, 3)],
  4: [(1, 4), (2, 2)],  # For 4, we have two pairs: (1, 4) and (2, 2)
  # And so on.
  ...
  9801: [(99, 99)]
}

The trick is in those entries that are only made up of a single pair.

Let’s look at Peter first. Peter knows the product of the two numbers. Peter can look up this product in the products map – if there is only one pair that makes up that product, then those must be the numbers! When Peter tells us that he doesn’t know the numbers, it means that the product must not be any product that only has one pair. This means that every time Peter doesn’t know, we can remove each pair that is the only pair for a product, and those pairs can be removed from the list of potential candidates.

Let’s look at those above lists and Peter’s first claim. At the start, we have a full list of candidate pairs, a full sums map, and a full products map. Because Peter knows the product, when he says “I don’t know the numbers”, it means that he looked at the possible pairs that made up this product and found multiple potential pairs – otherwise he would immediately know the numbers. This means that we can then disqualify products that are made up of one pair. 1 as a product, for instance, is only made from multiplying the pair (1, 1). Since we know that Peter doesn’t immediately know it as the solution, it means that it can’t be (1, 1).

Similarly, if the product was 9801, Peter would have immediately known the pair was (99, 99). Because he can’t yet say for certain, it means that the numbers must not be (99, 99).

We’re able to now remove all candidates that were the only factors that made up a product. For the first round, this is notably 1 times each prime and each prime multiplied by another prime that results in a number greater than 100. Importantly, we can also remove them and their products/sums from the products map and the sums map.

# After culling the candidates from the first round
candidates: [
  (̶1̶,̶ ̶1̶)̶,̶
  (̶1̶,̶ ̶2̶)̶,̶
  (̶1̶,̶ ̶3̶)̶̶,̶
  (1, 4),
  ...
  (̶9̶9̶,̶ ̶9̶9̶)̶
 ]

sums: {
  2̶:̶ ̶[̶(̶1̶,̶ ̶1̶)̶]̶,
  3̶:̶ ̶[̶(̶1̶,̶ ̶2̶)̶]̶,
  4: [(̶1̶,̶ ̶3̶)̶, (2, 2)],
  5: [(1, 4), (2, 3)],
  6: [(̶1̶,̶ ̶5̶)̶, (2, 4), (3, 3)],
  # And so on.
  ...
  198: [(99, 99)]
}

products: {
  1̶:̶ ̶[̶(̶1̶,̶ ̶1̶)̶]̶,̶
  2̶:̶ ̶[̶(̶1̶,̶ ̶2̶)̶]̶,̶
  3̶:̶ ̶[̶(̶1̶,̶ ̶3̶)̶]̶,̶
  4: [(1, 4), (2, 2)],
  # And so on.
  ...
  9̶8̶0̶1̶:̶ ̶[̶(̶9̶9̶,̶ ̶9̶9̶)̶]̶
}

# Note: the above uses strikethrough code - if it looks funny on your screen, I apologize!
# In that case, the culling is an exercise left to the reader.

This is the trick. Because the space of possible candidates has been reduced, it means the possible candidates that make up each sum and product have also been reduced. Let’s look at the updated candidates, sums, and products, filling in a few more previously omitted values:

candidates: [
  (1, 4),
  (1, 6),
  (1, 8),
  ...
  (88, 90)
]

sums: {
  4: [(2, 2)],
  5: [(1, 4), (2, 3)],
  6: [(2, 4), (3, 3)],
  # And so on.
  ...
  178: [(88, 90)]
}

products: {
  4: [(1, 4), (2, 2)],  # For 4, we have two pairs: (1, 4) and (2, 2)
  # And so on.
  ...
  7920: [(88, 90)]
}

Now, it’s Sandy’s turn to say that she doesn’t know the numbers. Because Sandy knows the sum, again it must mean that the sum can’t be any sum with only one pair as an option in sums, so we can again cull those pairs. In the updated sums structure, we can see that 4 is now only made up of a single candidate pair, (2, 2). If the sum was 4, Sandy would know immediately what the pair was, but since she doesn’t, it means the pair cannot be (2, 2), and we can remove it from the candidates.

Every round, we’re disqualifying potential candidates. Because we’re also able to remove them from the sums and products as potential options, it means that each protagonist is working on a new collection every time, giving a little more information every time they say they don’t know the number.

This pattern will continue