The solution of the problem of two sages and numbers from 1 to 100

Recently on Habré flashed an interesting task about the two wise men. Here I want to offer my own solution and tell you how to come to this decision. I recall the condition:

Some sultan had two wise men: Ali-ibn-Vali and Vali-ibn-Ali. Wanting to be convinced of their wisdom, the Sultan called the wise men to him and said: “I planned two numbers. Both are whole, each is greater than one, but less than a hundred. I multiplied these numbers and the result will tell Ali and at the same time Vali I will say the sum of these numbers. If you really are as wise as they say about you, you can find out the original numbers. ”
Sultan said Ali the work, and Vali - the amount. Wise men thought. The first to break the silence of Ali.
“I don’t know these numbers,” he said, lowering his head.
“I knew that,” said Vali.
“Then I know these numbers,” rejoiced Ali.
- Then I know! Exclaimed Vali.
And the wise men informed the amazed Sultan of the numbers that he had intended.
Call these numbers.

There is a similar task, which was also on Habré. It is much easier.
Birthday challenge:

Albert and Bernard just met Cheryl. They want to know when her birthday is. Cheryl offered them ten possible dates: May 15, May 16, May 19, June 17, June 18, July 14, July 16, August 14, August 15 and August 17. Then Cheryl told Albert the month of her birth, and Bernard - the day. After this dialogue took place.
Albert: I don't know when Cheryl has a birthday, but I know that Bernard doesn't know either.
Bernard: At first I did not know when Cheryl had a birthday, but I know now.
Albert: Now I also know when Cheryl has a birthday.
When is Cheryl's birthday?

Upon closer inspection, you can see that the two tasks are completely identical.
Some days correspond to several possible months, as well as some works correspond to several sums (for example, the product 60 corresponds to the sum 15 + 4 = 19, 12 + 5 = 17, etc.). Some months correspond to several days, as well as several works correspond to some sums (for example, the sum 10 corresponds to the works 6 * 4 = 24, 7 * 3 = 21, etc.). The meaning of the dialogue is also exactly the same.

This means that if we create a working algorithm for solving the birthday problem, we can use it for the wise men problem. The difference is only in the number of possible combinations of day-month and the amount-product that you want to sort. If the birthday can be calculated manually on paper, you need to use software to search for numbers from 1 to 100. Therefore, we first create an algorithm for a simpler task to make sure that it is correct, and then we substitute the original data from a more complex one.

For the solution, I used MATLAB. Yes, I shoot a cannon at the sparrows, but I often come across Matlab in my work, so let everyone use a tool that is familiar to him.
')
So the solution.

1. We write down the initial conditions: a vector with possible values ​​of days, a vector with possible values ​​of months and a rectangular matrix in which there are units on the places of possible combinations.

days = [14; 15; 16; 17; 18; 19]; months = [5; 6; 7; 8]; matrix = [ 0 0 1 1; 1 0 0 1; 1 0 1 0; 0 1 0 1; 0 1 0 0; 1 0 0 0 ]; 

2. Let us analyze the first phrase of Albert, who knows the month:

I don't know when Cheryl has a birthday, but I know that Bernard doesn't know either.

From it we can conclude that any days valid for this month may correspond to more than one month.
Such a situation is impossible for May (for if Bernard’s birthday is May 19, then he already knows the answer) and June (if the answer is June 18, Bernard also knows the exact date).
To exclude impossible months, we need to find the lines in which only one unit (days 18 and 19), find the columns where these units are (months 5 and 6) and cross out these columns.



On Matlab this action will look like this:

 unique_days = find(sum(matrix,2)==1); [~, months_with_unique_days] = find (matrix(unique_days,:)==1); months_with_unique_days = unique(months_with_unique_days); matrix(:,months_with_unique_days) = []; months(months_with_unique_days) = []; 

3. After the first sentence, Bernard, who knows the day, replied:

At first, I did not know when Cheryl had a birthday, but I know now.

So, the day that Bernard knows is only one month.
This situation is possible for the numbers 15, 16 and 17.
All rows of the matrix in which there is more than one solution or not one should be deleted.

 non_unique_days = find(sum(matrix,2)~=1); matrix(non_unique_days,:) = []; days(non_unique_days) = []; 

4. Albert, who knows the month, replied:

Now I also know when Cheryl has a birthday.

This means that in the remaining part of the matrix there is a column in which there is only one option. This column corresponds to July. We throw away all the columns, where more than one option.

 non_unique_months = find(sum(matrix)~=1); matrix(:,non_unique_months) = []; months(non_unique_months) = []; 

5. It remains to find in the remaining column one.

 days = days(matrix == 1); disp(days); disp(months); 

Answer: July 16th .


Now we will try to apply this algorithm for the problem with the sages.
We will replace the months with all possible sums of two numbers from 2 to 99. These will be integers from 4 to 198. We will replace days with all possible products of two numbers from 2 to 99. There are 2843 such products. After that, we will generate a matrix where intersections of possible sum-product pairs.

 months = 4:198; days = unique((2:99)'*(2:99)); matrix = false(length(days),length(months)); for i1 = 2:99 for i2 = 2:99 matrix(days==(i1*i2),months==(i1+i2)) = true; end; end; 

Run the program and get the answer: the product - 52, the sum - 17.
This corresponds to a pair of numbers 4 and 13 .