Two wise men and two number (solution explained)

in #steemstem5 years ago

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.

Sort:  




This post has been voted on by the SteemSTEM curation team and voting trail in collaboration with @curie.

If you appreciate the work we are doing then consider voting both projects for witness by selecting stem.witness and curie!

For additional information please join us on the SteemSTEM discord and to get to know the rest of the community!

Congratulations @jent! You have completed the following achievement on the Steem blockchain and have been rewarded with new badge(s) :

You got more than 10 replies. Your next target is to reach 50 replies.

Click here to view your Board
If you no longer want to receive notifications, reply to this comment with the word STOP

Do not miss the last post from @steemitboard:

SteemWhales has officially moved to SteemitBoard Ranking
SteemitBoard - Witness Update

Support SteemitBoard's project! Vote for its witness and get one more award!

STOP

Notifications have been disabled. Sorry if I bothered you.
To reactivate notifications, drop me a comment with the word NOTIFY

There is a mistake in my explanation. I apologize for that. This part is not quite correct:

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. It happens that the only product we will be left after removal is 52.

Actually, there are more products which we will encounter only once, e. g. 18. But they won't serve as the right solution, because it is not a sufficient condition. We need to select a sum which has a single decomposition to terms which product factorization give us a unique pair of numbers whose sum is in on our list.

This is quite complicated so I present it in the form of pseudo-code for better understanding:

For each sum from our list:

  1. Decompose it into a pair of terms in all possible ways
  2. For each pair of terms:
    2.1. Calculate their product
    2.2. Factorize the product into a pair of factors in all possible ways
    2.3. For each pair of factors calculate their sum
    2.4. If only one of these sums is in our list, then mark the product as a potentially good one (this condition allows Gandalf to know the numbers).
  3. If only one of the products is marked as a potentially good, that is the right product and the right sum (only this condition allows Saruman to know the numbers).
  4. Otherwise start over with the next item from the list.

Coin Marketplace

STEEM 0.29
TRX 0.12
JST 0.034
BTC 64158.52
ETH 3293.13
USDT 1.00
SBD 4.46