An old puzzle about two numbers
 

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 :smile:

I assume that only one pair of numbers have a product which
can be formed in more than one way and the sum of the two numbers
is the same for more than one case. Does this make sense?
I'll try it in Basic.

David

Lets say the two numbers are a, b, with a<b.
The first statement means the two numbers a,b are not both prime, their product is not the cube of a prime, and for at least two k|a*b with 1<k<100, a*b/k is < 100. I.e., a*b wasn't 2*31*59, as that would only allow a=59, b=62.
The second statement means that the sum Mersenne was given can be written in more than one way as a+b with such a,b. Also, the sum isn't 198 or 197.

It may be possible to solve it from there with an exhaustive search.

Alex

[Spoiler]
The first numbers that spring to mind are 4 and 3. Giving the product 12 and the sum 7.

12 can be expressed as 4*3 or 6*2 so Fermat could not define them.
7 can be expressed as 4+3 or 5+2 likewise for Mersenne.
The statement did say the numbers where greater than 1 and other numbers would not give such a simple addition.

[/Spoiler]

I have not thought this completely through but it seems to give a quick solution.

Regards
Patrick

But Fermat said he *knew* that Mersenne knows that Fermat can't figure out the numbers. If Fermat had been given the product 12, he would have known that Mersenne must have been given the sum 7 or 8. With the sum 7, Mersenne could not have known for certain that Fermat was stuck, as it might have admitted a=2, b=5, which Fermat could have solved...

Nice little mind twister.

Alex

So I guess the sum a+b was an odd number, as any even number can (conjecturally) be written as the sum of two primes, and a+b-2 must not be prime.

Alex

Ah! I see what you mean. I thought it was too easy.

Regards
Patrick

[b]akruppa[/b] is on the right way :)

[Spoiler]
The two numbers are 9 and 21. Product 189 - Sum 30.
[/Spoiler]

Taking Alex's lead, I used Excel and filtered out:
All Evens.
All primes.
All products of two primes.
All numbers where n-2 was prime.

I then factorized the remaining numbers and created a permutation of all the ways you can sum the numbers. There where 2 products that had the same sum with one being a cube. This is all Fermat needed to know to solve this.

Regards
Patrick

The answer (9, 21) is wrong :)

I saw this puzzle on the net and the following line is included:

Both are unequal to 1 and the sum of them is less than 100.

This is different than XYYXF's statement. I don't know if this is supposed to be part of this puzzle or not.

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

[spoiler] 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
[/spoiler]

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

Sum and product.
 

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

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

Alex

Kindly enlighten me Alex
Thank you
Mally

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 [B]not[/B] 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

Contradiction!
 

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



[QUOTE=XYYXF;99054]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:[/QUOTE]


[QUOTE=akruppa;99223]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 [B]not[/B] 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[/QUOTE]

Kindly clarify

Mally

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

Alex

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

David

[QUOTE=XYYXF;99054]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 :smile:[/QUOTE]So there's the solution (spoiled). :)

[Color="#F0F0FF"]Let the numbers be A and B. So, Fermat knows A*B, Mersenne knows A+B.

Let's call the product [B]simple[/B] if there's exaclty one way to split it into two efficients (greater than 1 and less than 100), and [B]non-simple[/B], 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: [b]{11, 17, 23, 27, 29, 35, 37, 41, 47, 53}[/b], let's call this set [b]X[/b]. 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 [b]X[/b]. 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 [b]X[/b]. Let's call such products as [b]Fermat products[/b].

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 [b]X[/b] => 2*9 is not a Fermat product;
11 = 3+8; 3*8 = 4*6; 4+6 = 10 is not in [b]X[/b] => 3*8 is not a Fermat product;
11 = 4+7; 4*7 = 2*14; 2+14 = 16 is not in [b]X[/b] => 4*7 is not a Fermat product;
11 = 5+6; 5*6 = 3*10; 3+10 = 13 is not in [b]X[/b] => 5*6 is not a Fermat product;

and so on for 17, 23 and other numbers from [b]X[/b].

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

In the end, we find only three Fermat products:

[b]102[/b] = 2*51 = 3*34 = 6*17, with sums of factors [b]53[/b], [b]37[/b] and [b]23[/b] respectively;
[b]286[/b] = 11*26 = 13*22, with sums of factors [b]37[/b] and [b]35[/b] respectively;
[b]322[/b] = 14*23 = 7*46, with sums of factors [b]37[/b] and [b]53[/b] 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 [b]286[/b], the sum is [b]37[/b], and the numbers are [b]11[/b] и [b]26[/b].[/color]

[QUOTE=Kees;99207]I am missing something, but do not know what[/QUOTE]You are missing 53 as a possible sum :wink:

41*12 = 82*6 :wink:

Hmm :blush:
accept solution


Kees

[QUOTE=XYYXF;99293]So there's the solution (spoiled). :)

[Color="#F0F0FF"]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.
[/color][/QUOTE]

I'm having trouble with this solution, because of the following:

[spoiler]Mersenne would know the solution if there is only one non-simple product among the n*(A+B-n), so Mersenne only knows that there must be at least two non-simple solutions among the products n*(A+B-n), not that all of these products must be non-simple.[/spoiler]

[b]philmoore[/b], [spoiler]if there is at least one simple product, then, from Mersenne's point of view, there will be a chance that namely this product was reported to Fermat, so Fermat knows A and B.[/spoiler]

[QUOTE=akruppa;99282]So please tell us what the values xy and x+y are.

Alex[/QUOTE]

Of the many answers up to 100 take arbitrary values for x and y keeping in mind that x + y should be even and the discriminant a +ve square and insert in the given eqn.

Thus x = 4 +- 1 i.e. 5 or 3 and correspondingly y =3 or 5

Another is x = 7 or 3 and y = 3 or 7 resp.

The eqn suits negative values also.

Take x = 3 and y = -5 or x = - 5 y= 3.

I have not pursued further for both -ve values . I presume it can be done.

Mally

We have already established that x+y are not even. Read Fermat's and Mersenne's conversation again. Also, it is sufficient that the discriminant is an integer square for the solutions to be integers.

You have just shown that your equation can be used to find x and y, given x+y and xy. We already know that. You still haven't said anything about how to find x+y and xy from Fermat's and Mersenne's conversation. Not that it matters any more, as XYYXF has posted the solution by now.

Alex

I see, I overlooked the "Of course you know" prefacing Fermat's first statement, and was making the problem harder!