blinkdagger

MMM #12 Winner

The results are in, and the winner for MMM #12 is Anneleen Van Geenhoven! She will be receiving a $10 Amazon gift certificate. We only had 9 submissions this time, but a whopping 2500+ visits. This was a challenging problem so thanks to everyone who participated!

Correct Submissions
Lieven Marchand
Kinks

Before We Tell You The Answer

Perhaps you needed a little help to solve the problem. If you are still up for solving the Martian problem consider the following hints.

Hints:

1. The dialogue can be interpreted as a series of problem statements. For example: Dan: Quan, you don’t know what X and Y are. implies that the product is not a unique product. We are also told that the numbers are greater than 2. So products like 12, 15, etc… cannot be the product told to Quan because there exist only one pair of factors that are greater than 2 for 12: 3×4 and 15: 3×5, making them ‘unique’.
2. You can proceed to decipher the problem statements to eliminate pairs of numbers that do not meet the requirements.
3. Again we are not looking for unique sum or product. If it is unique Quan and Dan would know the two numbers!
4. The answer is not 4 and 13! 4 and 13 is the answer for the range of numbers 2 to 99. But we specifically said that the numbers 2 and 99 are not included. If you google for the answer you would probably find 4 and 13

The Answer

The two numbers are 13 and 16

Here is Anneleen’s explanation:

We can already conclude a lot of things from the first statement of Dan (and the fact that Quan admits he was right).

1) The most interesting thing is that the sum of the numbers x and y needs to be odd, in other words, that one of x and y is odd, and that the other one is even. Here is why: suppose the sum of the 2 numbers is even. Then it can be written as the sum of 2 prime numbers in some way. (This is the Goldbach’s conjecture, which is not yet proved as far as I know, but we are only working with numbers smaller than 100, and for those numbers this property holds anyway.) So, if Dan has been told an even number as sum, then he thinks that it is possible that x and y are exactly those primes (or 1 of those combinations, because the ‘decomposition’ in 2 primes is not at all unique). But in this case, the product of these 2 numbers is easily factorisable, so that Quan knows the 2 numbers immediately. So, Dan could never be sure that Quan doesn’t know the 2 numbers.

2) Likewise, the sum of the numbers can not be 4 more than a prime number. Let’s suppose that the sum x+y equals 4+p, where p is a prime number. Then Dan thinks that it is possible that {x, y} = {4, p}, but then the product xy = 4p, and this can be composed in only 1 way (because 2 is not allowed). So in this case also, Dan couldn’t be sure that Quan doesn’t know the numbers x and y.

3) It’s also not possible to have a sum which is 57 or more: otherwise the sum x+y could also be written as the sum of 53 and another number larger than 2, but when 53 is a factor of the product, Quan should know the numbers x and y, because 53 is a prime, and it can’t be multiplied by another factor because then it would exceed 98.
(So the reason why this argument holds is that 53 is the smallest prime which is larger than 98/2 = 49).

4) For any prime p larger than 10, the sum can’t be 3p, because otherwise p and 2p could be the numbers x and y, but in this case Quan would know x and y immediately: 2p^2 can’t be factorised in another way in 2 numbers (larger than 2 and smaller than 99). So, the following sums are also impossible: 33, 39, 51, 57, …

So, the sum x+y has to be one of the following:
13, 19, 25, 29, 31, 37, 43, 49, 53, 55

(The other way around, with any of these sums, it is also possible to prove that Dan’s first statement (about Quan knowing nothing) is right.)

Now let’s define the property P as follows:
We say that a number N has property P if and only if there is only 1 way to write this number as a product of 2 factors, (larger than 2 and smaller than 99) where these factors have as sum one of the numbers in the list above.

Now we have the following conditions:
1) After the first statement of Dan, Quan knows the two numbers. This means that the product he got needs to have property P.
2) Moreover, also Dan knows the numbers after Quan says he knows. In other words, for the sum Dan got, there can only be 1 possible decomposition s = a+b, for which the product ab has property P.

Let’s consider all the foregoing sums:
13: this can be 4+9 (the product 36 has property P)
or 3+10 (30 has property P)
and there are still other possibilities, but all that’s important is that condition 2 is not satisfied here
19: 3+16 or 4+15 (48 and 60 both have property P) or …, so condition 2 doesn’t hold
25: 3+22 or 6+19 are both possible (66 and 114 have property P), so condition 2 doesn’t hold
29: I’ll let this one open for a moment
31: 4+27, 5+26, (108 and 130 satisfy P) so condition 2 doesn’t hold
37: 3+34, 4+33 (102 and 132 satisfy P) so condition 2 is not satisfied
43: 6+37, 8+35 (222 and 280 satisfy P) so 2 is not satisfied
49: 6+43, 8+41 (258 and 328 satisfy P) so 2 is not satisfied
53: 4+49, 6+47 (196 and 282 satisfy P) so 2 is not satisfied
55: 5+50, 8+47 (250 and 376 satisty P) so 2 is not satisfied

So, from condition 2 we get that the sum needs to be 29. Now let’s check condition 1 for all possible sums of 2 terms to get 29:
3+26, product 78 = 6.13 doesn’t have property P
5+24, product 120 = 3.40 doesn’t have P
7+22, product 154 = 11.14 doesn’t satisfy P
9+20, product 180 = 4.45 doesn’t satisfy P
11+18, product 198 = 9.22 doesn’t satisfy P
13+16, product 208 satisfies P
15+14, product 210 = 10.21 doesn’t satisfy P
17+12, product 204 = 4.51 doesn’t satisfy P
19+10, product 190 = 5.38 doesn’t satisfy P
21+8, product 168 = 7.24 doesn’t satisfy P
23+6, product 138 = 3.46 doesn’t satisfy P
25+4, product 100 = 5.20 doesn’t satisfy P

So, we see that the given scenario is only possible when x = 13, and y = 16 (or vice versa of course).