Recently I saw a math problem from a netizen (@cat D) on the boiling point of this website. After careful analysis, really feel that call a difficult ah, the brain is very easy to dry up…

The topic is as follows:

There are two integers x and y greater than 1, and a knows their product, and B knows their sum.


A: I don’t know what these numbers are!


B: I don’t know what these numbers are. I knew you didn’t!


A: Now I know.


B: I see.


What are these two numbers?

At first glance, what the hell?

Think for a long time, finally want to understand, this article is ready to use JS to solve it.





(Manually split the lines, make sure you know the answer right away?)







Let’s look at the correct answers first: 4 and 13.

Let’s check if this answer is correct (just check!) Understand the situation, by the way!

Put yourself in your shoes for the first time

Since the correct answers are 4 and 13, a knows 52, and a knows that 52 can be written either as 2 * 26 or 4 * 13. So a doesn’t know which of these numbers are possible.

B knows the number 17, but the summation of 17 (a word I coined) can be 2 + 15, 3 + 14, 4 + 13, 5 + 12, 6 + 11, 7+ 10, or 8 + 9. Now comes the crucial piece of information, and B is convinced that A doesn’t know the answer. This is b’s first perspective-taking, and the process of thinking is as follows:

If the answer is 2 and 15, then A knows 30, but 30 can be divided into 5 * 6 and 3 * 10, so A can’t be sure. Similarly, B verifies the other possibilities, including 3 and 14, 4 and 13, 5 and 12, 6 and 11, 7 and 10, 8 and 9, and deduces that A cannot know the correct answer. Because the factorization of their products is not unique.

Second empathy

Since B has already told A this key information, A can also reason backwards:

If it’s 2 and 26, then the sum is 28. If one of the factorization of 28 is 5 + 23, then B will verify whether the factorization of 5 * 23 is unique, and since it happens to be two prime numbers, the factorization must be unique. Then B won’t conclude that I don’t know the answer. So x and y can’t be 2 and 26, they’re 4 and 13. Here, must be thinking very clear.

Put yourself in your shoes for the third time

B see a actually got the answer through his words, he undertook a more complex reasoning, let me say slowly, can be carefully watched, did not speak clear words, see twice more, a little burn brain, paste!

At this point, B will think about the problem from A’s point of view:

To get the right answer, a must have eliminated all but the right answer. The exclusion condition is that only the corresponding factorization of the product of the sum of the correct answer is not unique at all. This condition is unique, which is what I told him earlier, “I knew you didn’t know.”

For example, the product of 2 and 15 is 30, and the other factorization of 30 5 times 6 is 11, and all the factorization of 11 2 + 9,3 + 8,4 + 7, and 5 + 6 are not unique. In this case, if the product is really 30, is 2 and 15 the right answer, or is 5 and 6 the right answer, so a doesn’t have a choice. So 2 and 15 are not the answer. Similarly, except for the pair 4 and 13, the rest may not enable A to get the answer.

Our empathy

(That’s just checking the answer. Now let’s figure out 4 and 13.)

Speaking of empathy, there’s also a third person in this question: you!

One of them knows that the product is 52, the other knows that the sum is 17. But we readers, that is two eyes a black ah, do not know two people know the number. The reader has less information than either of them, making it doubly difficult to come up with the right answer.

Our idea of empathy is to try to filter the correct answer from the first and second words in turn.

Finally writing code!!

Let’s say x is less than y. Let’s say they’re both less than 100 just to keep things simple.

First, let’s calculate all the possibilities for x and y:

const max = 100;
let sums = {};
let products = {};

for (var i = 2; i < max; i++) {
  let x = i;
  for (var d = 0; d < max - x; d++) {
    let y = x + d;

    let p = x * y;
    products[p] = products[p] || [];
    products[p].push({ x: x, y: y });
    
    let s = x + y;
    sums[s] = sums[s] || [];
    sums[s].push({ x: x, y: y }); }}Copy the code

Products is the set of factorized products of all numbers. For example, the value of products[12] is [{x: 2, y: 6}, {x: 3, y: 4}]. Similarly, sums are the decomposition of sums of all numbers.

A: I don’t know the answer.

Filter out the unique case of factorization in products:

for (let key in products) {
  if (products[key].length == 1) {
    deleteproducts[key]; }}Copy the code

B: I don’t know the answer.

Likewise, we’ll filter out the unique case of sum-decomposition in sums:

for (let key in sums) {
  if (sums[key].length == 1) {
    deletesums[key]; }}Copy the code

B: I knew you didn’t know!

For any possible sum value, the product corresponding to the decomposition of each sum should have multiple possible decomposition forms. We filter out the mismatch in sums:

for (let key in sums) {
  let pairs = sums[key];
  let flag = pairs.every(function(pair) {
    return (pair.x * pair.y) in products;
  });
  if(! flag) {deletesums[key]; }}Copy the code

A: Now I know.


B: I see.

We iterate over every key according to the last-place thinking process of b. The possible results are then determined according to the exclusion condition, that is, whether the factorization of the product corresponding to the factorization of the sum is unique.

for (let key in sums) {
  let pairs = sums[key]
  let r = pairs.filter(function(pair) {
    let ps = products[pair.x * pair.y];
    let r = ps.filter(function(p) {
      return (p.x + p.y) in sums
    })
    if (r.length == 1) {
      return true
    }
    return false
  });
  if (r.length == 1) {
    console.log(r)
  }
}
Copy the code

Write here, be regarded as finished, also don’t know I write clear have not… It’s a bit convoluted and a bit clumsy.

In addition, there is a small problem with the code, ps.filter is done by trick. So we’ve figured out 4 and 13. Of course, if you limit it to numbers less than 100, that’s just proof of existence. I’m afraid uniqueness needs to be proved mathematically, goldbach’s conjecture, right?

The process of writing this article reminds me of the scene when I saw the game theory, my brain hurts!

Finally, the complete demo address is given.