In this post, I present the solution to the puzzle which I posted last year.
If you did not see the puzzle yet, you may want to try to solve it yourself before continue reading. Warning: the answer is straight below the picture!
The chosen numbers are 4 and 13. Gandalf knows their product, which is 52, and Saruman knows their sum, which is 17.
So, Gandalf thinks: "Which two numbers can get 52 when multiplied?" There are two possibilities:
52 = 4x13 = 2x26
Hence he says "I don't know the numbers" because he does not know which of these two pairs is chosen.
Saruman thinks in a similar way but he goes deeper. Of course, he also does not know the answer. There are even more possibilities of two numbers whose sum is 17. But he tries to figure out whether in any of those possibilities Gandalf in principle could know the answer. There are 7 options to decompose 17 into two terms (greater than 1). Let's consider the product of those terms:
2x15 = 30 = 3x10 = 5x6
3x14 = 42 = 2x21 = 6x7
4x13 = 52 = 2x26
5x12 = 60 = 2x30 = 3x20 = 4x15 = 6x10
6x11 = 66 = 2x33 = 3x22
7x10 = 70 = 2x35 = 5x14
8 x 9 = 72 = 2x36 = 3x24 = 4x18 = 6x12
Each of these products has different ways of factoring. So Saruman knows that whatever the answer is, Gandalf would not know it. Hence he says "I already knew that you didn't know".
Now Gandalf performs Saruman's task for both of his possibilities. He knows that Saruman has either 17 (4+17) or 28 (2+26). We've just performed the exercise for 17, let's do the same for 28. There are even more options:
2x26 = 52 = 4x13
3x25 = 75 = 5x15
4x24 = 96 = 2x48 = 6x16 = 8x12
5x23 = 115
6x22 = 132 = 2x66 = 4x33 = 11x12
7x21 = 147 = 3x49
8x20 = 160 = 2x80 = 4x40 = 5x32 = 10x16
9x19 = 171 = 3x57
10x18 = 180 = 2x90 = 3x60 = 4x45 = 5x36 = 6x30 = 9x20 = 12x15
11x17 = 187
12x16 = 192 = 2x96 = 3x64 = 4x48 = 6x32 = 8x24
13x15 = 195 = 3x65 = 5x39
14x14 = 196 = 2x98 = 4x49 = 7x28
In this case, we have two alternatives where both numbers are prime and therefore their product have unique factorization. So, if Saruman had 28, he would not be in a position to say what he said. Because then if the right answer was (5,23) or (11,17) Gandalf would know it.
Hence Gandalf knows that Saruman does not have 28. But that means that he has 17 as there are no other alternatives. Then Gandalf knows that the answer is (4, 13) and says "Now I know the numbers".
But how did Saruman know the answer? Basically now he has to repeat the last Gandalf's task for all the 7 options that he has. I would not repeat all the reasoning in whole details here, but the alternatives that Gandalf could rule out upon hearing Saruman's response are stricken out:
2x15 = 30 = 3x10 = 5x6
3x14 = 42 = 2x21 = 6x7
4x13 = 52 = 2x26
5x12 = 60 = 2x30 = 3x20 = 4x15 = 6x10
6x11 = 66 = 2x33 = 3x22
7x10 = 70 = 2x35 = 5x14
8 x 9 = 72 = 2x36 = 3x24 = 4x18 = 6x12
The only option where Gandalf would rule out all the alternatives except one is highlighted in bold. On all other lines, there are two different decompositions left. So only if the answer is (4, 13) Gandalf would be in a position to say that he knows the numbers. This way Saruman knows them as well.
As you can see it could not be a quick conversation as it requires a lot of calculations to be performed in mind. Unless they are really really wise men. There are actually other more sophisticated methods, which allow to solve the problem faster but hide the logic behind it. I don't present them here because they don't serve well as an explanation.
Okay, that is how our sages could solve the puzzle. But what about an external observer (us)? How can we solve it without knowing neither the product nor the sum, just hearing their conversation?
This requires even more enumeration. First, we know that at least one of the numbers is not prime, otherwise Gandalf would know the answer right away. Then, from Saruman's point of view, we know that their sum cannot be split into two prime numbers in any way.
From that we know that the sum is odd because every even number (at least up to 100) can be split into two prime terms (see Goldbach's conjecture). That means that one number is even and another one is odd. But anyway we can calculate all the potential sums that satisfy this condition and are less than 100. There are 24 of them: 11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53, 57, 59, 65, 67, 71, 77, 79, 83, 87, 89, 93, 95, 97. So we need to split each of these sums into all possible term pairs, multiply the pairs and remove those products which we encounter more than once (Otherwise Gandalf would not know which of two sums Saruman has).
It happens that the only product we will be left after removal is 52. It can be factorized as either 4x13 or 2x26, but only the first pair gives us odd and even numbers, and only 17, and not 28, is on our list of potential sums.
Hence the answer is 4 and 13.
P. S. Actually, there is a solution which (almost) avoids enumeration. It is described here, unfortunately in Russian. I'm not sure if there is a corresponding article in English.
