An old puzzle about two numbers

[philmoore]

Can both numbers be the same, or are they necessarily different?

[Kees]

S=a+b, P=ab
If P contains a primefactor >47 then Fermat knows the factorisation because 2p>100. So when Fermat says that Mersenne knows that he cannot know, he is implying that the sum Mersenne has got is smaller than 55, because 55=53+2 and in that case Fermat could have known. We can also apply Goldbach's conjecture (as it is certainly verified upto 100, to find that the sum must be odd, because otherwise it COULD have been written as the sum of two primes and then Fermat would have known the answer instantly.
This leaves the sumset reduced to
5,7,...,53
we can filter out all p+2 because that would give a unique factorisation as well.
This leaves us with
S in {11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53}
We can eliminate 51 because
51=17+34 and then Fermat would have had the product P=2*17*17 and he would have known because 17*17>100
Likewise 53=41+12, here Fermat sees P=3*4*41 and he knows how to split these too.
This leaves {11,17,23,27,29,35,37,41,47}
By saying that he knows that Mersenne knows he cannot know, he is confirming that his primefactorisation can split into two numbers leaving this sum. But how could he have known that Mersenne knew that ? If for example he has received the product 172=2*2*43 he cannot decide that Mersenne knows he cannot find out. For all he knows Mersenne has S= 88 (2+86) and then he could have known.
Along this line, we can eliminate some more.
41=37+4 =>P=2*2*37=148 => S=41 or S=76 but 76 would not allow such a conclusion.
37=6+31 => P=2*3*31=186 => S=37 or S=65 or S=95
35=6+29 => P=2*3*29=174 => S=35 or S=61 or S=89
29=6+23 => P=2*3*23=138 => S=29 or S=49 or S=71
27=4+23 => P=2*2*23=92 => S=27 or S=48
23=4+19 => P=2*2*19=76 => S=23 or S=40

This leaves 11 and 17, but even here the reasoning works:

17=4+13 => P=2*2*13=52 S=17 or S=28
11=4+7 => P=2*2*7=28 =>S=11 or S=16
This leaves us at a dead end: when Fermat says that he knows that Mersenne knows he cannot know the answer, he is lying: either Mersenne has a number that is even (and then he cannot decide), a number larger than 53 and then he cannot know or one in the list, but Fermat cannot know that...
I am missing something, but do not know what

[Kees]

Having thought a little more I think that the question was ill-posed. As Fermat does not lie (or does he ?), the real discussion must have been something like this:

Fermat: I do not know the answer
Mersenne: I knew that
Fermat: then I know
Mersenne: then so do I

Please tell me if I am mistaken

Kees

[mfgoode]

Apart from the play on words which could alter the sense of the problem this is a plain algebraic one and is known since antiquity. It was found and solved on a clay tablet with cuneiform writing from Southern Iraq in 1700 B.C.

In modern terms the problem posed by this tablet is given by :

Given x+y and and xy : find x and y.

The solution is



x =
(x + y)/2 +- sqrt.{ [(x+y)/2] ^2 - xy}
y =


Mally

[akruppa]

Mally, you completely missed the point of the problem at hand.

Alex

[mfgoode]

Kindly enlighten me Alex
Thank you
Mally

[akruppa]

Your equation requires given xy and x+y, and tells x and y. The very point of this puzzle is that x+y and xy are not given, but must be deduced from the vague hints in Fermat's and Mersenne's conversation which impose restrictions on x+y and xy. This is the hard part, solving for x and y is trivial.

Alex

[mfgoode]

The following are in direct contradiction but even then, in my opinion as per my eqn many solutions can be given.

Originally Posted by XYYXF

Two integers are chosen. It is known than both of them are greater than 1 and less than 100. It's also known that Mersenne was informed of their sum, while Fermat was informed of their product. So, the following conversation between them took place:

Originally Posted by akruppa

Your equation requires given xy and x+y, and tells x and y. The very point of this puzzle is that x+y and xy are not given, but must be deduced from the vague hints in Fermat's and Mersenne's conversation which impose restrictions on x+y and xy. This is the hard part, solving for x and y is trivial.

Alex

Kindly clarify

Mally

[akruppa]

So please tell us what the values xy and x+y are.

Alex

[davieddy]

I don't wish to muddy the waters further, but it is crucial
to understand that x and y are integers.

David

[XYYXF]

Originally Posted by XYYXF

Two integers are chosen. It is known than both of them are greater than 1 and less than 100. It's also known that Mersenne was informed of their sum, while Fermat was informed of their product. So, the following conversation between them took place:

Fermat: Of course you know that I'm not able to find the numbers chosen...
Mersenne: You are right. And I can't find them too...
Fermat: But I've just found them!

What numbers were chosen, and how did Mersenne and Fermat draw their conclusions?

Of course both of them were honest

So there's the solution (spoiled). :)

Let the numbers be A and B. So, Fermat knows A*B, Mersenne knows A+B.

Let's call the product simple if there's exaclty one way to split it into two efficients (greater than 1 and less than 100), and non-simple, if there are more ways.

Mersenne knows than Fermat can't find A and B, i.e. that A*B is non-simple. But Mersenne was informed only about A+B. It means that every product n*(A+B-n), where both n and A+B-n are less than 100 and greater than 1, is non-simple.

There are only 10 such sums: {11, 17, 23, 27, 29, 35, 37, 41, 47, 53}, let's call this set X. It's not hard to build this set. Just take {4, 5, 6, ..., 197, 198} and strike out:

1) 198 and 197, because 99*99 and 99*98 are simple;
2) all from 54 to 196, because we may choose an appropriate prime from 53 to 97 as a value of n, so n*(A+B-n) is automatically simple;
3) all remaining evens, with respect to Goldbach;
4) all numbers of the form p+2, where p is prime, because 2*p is simple;
5) all numbers of the form 3*p, where p is prime greater than 10, because p*(2*p) is simple in this case.

After all, only 10 candidates remain, so we just verify that there are no simple products n*(A+B-n) where both n and A+B-n are greater than 1 and less than 100.

Going ahead. The first Fermat's phrase "Of course you know that I'm not able to find the numbers" tell us that Fermat knows that A+B is in X. But Fermat has only the product A*B, so it means that every possible pair of factors (both must be in the range 2 - 99) has the sum from X. Let's call such products as Fermat products.

It's not too hard to find all of them, e.g., as here:

11 = 2+9; 2*9 = 3*6; 3+6 = 9 is not in X => 2*9 is not a Fermat product;
11 = 3+8; 3*8 = 4*6; 4+6 = 10 is not in X => 3*8 is not a Fermat product;
11 = 4+7; 4*7 = 2*14; 2+14 = 16 is not in X => 4*7 is not a Fermat product;
11 = 5+6; 5*6 = 3*10; 3+10 = 13 is not in X => 5*6 is not a Fermat product;

and so on for 17, 23 and other numbers from X.

You may use that all numbers in X are odd and are less than 55 to speed up the search.

In the end, we find only three Fermat products:

102 = 2*51 = 3*34 = 6*17, with sums of factors 53, 37 and 23 respectively;
286 = 11*26 = 13*22, with sums of factors 37 and 35 respectively;
322 = 14*23 = 7*46, with sums of factors 37 and 53 respectively.

So, Fermat tells to Mersenne that A*B is a Fermat product, i.e. 102 or 286 or 322. But Mersenne still can't find A and B, so it means that A+B can't be equal to 23 or 35, and the only possible cases for A+B are 37 and 53.

But this information wouldn't have helped Fermat to find A and B if the product had been 102 or 322, because both 37 and 53 would have fit as A+B.

So the product is 286, the sum is 37, and the numbers are 11 и 26.