No, you are, so far as I can see, quite correct.
Though, when MindWanderer originally said “In order for Mr. P to not be able to figure out the sum, it must not be the case that both A and B are prime.”, they forgot to also rule out the possibility that A is prime and B is A^2. But this ends up being taken care of by your invocation of Goldbach’s Conjecture anyway.
Responses to Indistinguishable:
[spoiler]The whole goldberg stuff is beyond me. As to the rest.
I missed 11 on accident, and couldn’t edit in time. I stopped at 37 because its the highest relevant sum that can be produced with a and b within 2 - 20.
I created a quick program to get all the possible products, and nothing jumped out at me as a good answer but it may have bugs. There were dozens of products possible, and more than one for all sums possible.
[/spoiler]
Its probably just beyond my level of discrete math. I only know the basics of number theory.
But I found it to be a very interesting problem. Kinda like solving those complicated logic problems (liers and truthtellers and such) only with numbers in stead.
Why have you set an upper limit of 20? The OP picks an upper limit of 100.
Woops. I misread the question. I will take another look at it with the correct numbers.
I think he’s saying that the mathematicians have been given more information than we have been given, so if we can figure it out with less information we must be smarter than the “brilliant” mathematicians.
Info for the problem (now that I now the max for a and b is 100)
I ran a brute force algorithm generating possible products that can only be produced by value a and b’s that sum to a single sum among the list of acceptable sums.
I got quite a few results and grouped them by the one matching sum of a and b.
There are two interesting sums which have only a few matching products:
sum 29: with products 54 and 208
and sum 197: with products 9700 and 9702.
But let me backtrack so I know what I’m doing here:
Clue 1: Mp looks at the product he was given and says to Ms “Hmm, I have no idea what your sum could be…”
If the product was a product of two primes or a prime square, Mp would know.
Clue 2: Ms replies “Thats no news to me, I already knew you could not deduce the sum I was given…”
Ms knows based on her sum that Mp could not have a product of two primes, etc.
that means for all a within the bounds of 2 <= a <= 100 and 2 <= b <= 100, it is never the the case that both a is prime and s - a is prime.
The reason this is true, is if say there is some a and some s - a. They don’t have to be the ones that actually were given to Ms and Mp, just possibilities deducible by Ms, then its the case that Mp could have received the product (a * (s - a)), and because it was a product of two primes, there is only one way to decompose them into two numbers and then one possible sum.
Therefore if there is any case where they are both sums, Ms. can not consistently make that statement. And we are assuming both are consistent and infinitely smart i assume?
So s must exist such that no possibility of that exists. Which reduces it to all numbers two greater than a odd composite number, that are within 2 to 200 (100 + 100). Its a long list of possible sums. I took the full list from the Integer Encyclopedia (odd composite numbers, And then I added two to them all in my algorithm to get the possible sums)
Clue 3: And to that Mp replies “Ah ha, now I know what your sum is!”
So given the product p, that he has, he knows there is no other sum of a and b, such that a * b is p. Or a bit more formally,
There is no such c and d, such that c +d != a + b, yet c + d is in the set of valid sums discussed in clue 2, and c * d = p. So there is no other sum that can be found by changing the numbers multiplied.
This reduces the products possible to a very long list. Which is what I calculated in my little C# program.
Clue 4: And Ms responds, “And likewise I have now deduced your product…”
Now I will take back the list of exceptional products associated with sums that I had at the start and look again.
sum 29: with products 54 and 208
and sum 197: with products 9700 and 9702.
So here, I’m at a deadlock. If Ms has sum 29 or 197, she can at best guess from two products. And all the other sums have even worse guesses (some have more than 15 possibilities).
However it is possible that my algorithm has an error in it.
My algorithm, in essence, does the following:
Start with the set of possible sums. I took a web reference to odd composites, and imported all the ones less than or equal to 198, and put it into an array. As a first step I added 2 to all of these.
Then I take an index into this array. Then I take a possible value for A that leads to a consistent value for both A and B (so that they are in the range 2-100).
Then I take another index into the array, that must be different, and another A (A2 in this case), and once again make sure B2 is consistent with the range. These are 4 nested for loops. After the start of the first 2 for loops, I calculate the product p. I know the sum from the value of the indexed array.
I then track whether there is a second array index and second set of A, B, so that the sum is different (yet in the list of valid sums) and the product is the same. If that’s the case, I rule out the product. Then I put together all the allowed products with their sums and organize things.
Now that I think about it, the part you noticed that I failed to realize:
The a = s, b = s^2
Is another case that can’t be allowed, but I’m not sure how to incorporate that into the other clues. It may rule out certain other possibilities and give a sum with only one possible product.
Let me see how far I can work through this.
[spoiler]
Let’s translate the statements:
Mp: “I don’t know the sum” --> “A and B are not both prime”, because if they were, then A*B would only have one factorization, and Mp would know both numbers and their sum.
Ms: “I knew you wouldn’t know the sum” --> “A + B is not the sum of any two primes”, because if it were, then Ms couldn’t know that Mp didn’t have a number that was the product of two primes. This means that A + B is not even, and also that it’s not two more than a prime (that is, A + B is not 5, 7, 9, 13, 15, 19, 21, 25, 31, 33, 39, 43, 47, 49, 55, 61, 63, 69, 73, 75, 81, 85, 89, 91, 99, 103, 105, 109, 111, etc.).[/spoiler]…and continuing from there, when I have a chance to think about it some more.
This is called “The Perfect Logicians” puzzle
I got the answer (other than proving uniqueness) in about 10 minutes using just pen and paper.
Of course, that is only because the correct answer is the second thing you would probably try using guess and check.
If Ms knows the sum cannot be deduced, then the sum cannot be written as a sum of two primes.
This first happens at 11, 17, 23, 27, 29, 35, and 37.
If this allows Mp to deduce the sum, then there must be only one possible sum, given the product, which cannot be written as a deducible sum (in particular, a sum of two primes is deducible).
If this allows Ms to deduce the product, then there must be only one possible product, given the sum, which has only one possible sum which cannot be written as a deducible sum.
Sounds complicated, but if you just write out the possible sums and products you will get the answer.
11 cannot be the sum, because 28 and 24 are possible products, each of which has exactly one possible sum (11) which cannot be written as a sum of two primes.
The next guess is 17, which works. 4 times 13 = 52 is the only possible product which has just one possible sum (17) which cannot be written as a sum of two primes. In fact you never need to look past the first 7 such numbers I wrote above.
One last detail: We need to know that the 7 numbers I listed cannot be written as deducible sums in some other way. For example, 6 + 53 is deducible even though 6 is not prime, because 53 times 2 is more than 100. But since the 7 I listed are less than 50, this is not an issue.
After reading your solution, I realize I didn’t consider A is prime and B is A^2. Since such a sum would be even it doesn’t change anything, but it still means that my logic for deciding that the 7 (odd) numbers I listed could not be written as deducible sums was inadequate.
Also, I think there is a problem with your use of a simplifying hypothesis. Implicit in your statement that 4 and 13 works is the statement that 37 cannot be written as a deducible sum.
If it could, then Ms would not know if the numbers were 4,13 or 7,10.
However, even though 59 is not a sum of two primes or a prime and its square, 59 can still be written as the deducible sum 53 + 6.
So your method of checking did not actually show 4,13 was a solution to the original problem.
but…, if the numbers are 4 and 13, wouldn’t Mp know the two numbers a and b right away? 52 has factors 1,52 ; 2,26 ; 4,13. since it can’t be the first two pairs as the numbers are between 2 and 100 exclusive, he wouldn’t have made his first statement.
Sorry, I had said before that it doesn’t matter if we exclude 2 or not, but I shouldn’t have. My answer assumes the range is meant to include 2, not exclude it.
To Carmady: Yes, my reasoning was admittedly non-rigorous, given that the simplifying hypothesis actually changes things (as I think you correctly illustrate). Like I said, it allows us to stumble upon a potential candidate, but actually checking that that candidate works requires us to to test it properly. And my method gives no legitimate proof of uniqueness.
(That, of course, is in reference to my attempt to actually employ non-trivial reasoning. The exhaustive search code I first employed is perfectly legitimate (and incidentally gives (13, 16) as the only answer if we take the range as exclusive).)
Never mind.
I get a different answer than the linked sites. Maybe I’m misreading the question.
[spoiler]Mp is given the number 24 and reasons
24=212
24=38
24=4*6
2+12=14
3+8=11
4+6=10
So Mp can’t tell whether the sum is 14, 11 or 10.
But when Ms says, “I knew you couldn’t tell the sum”, Mp knows the sum
had to be 11. Because if it had been 14, Ms would have to consider that
14=3+11, and 311=33, and 33 has no other factorizations on [2,100],
which would reveal the sum as 14. And, if it had been 10, Ms would have
to consider that 10=5+5, and 55=25, and 25 has no other factorizations
on [2,100], which would reveal the sum as 10. Only the sum 11 allows Ms
to know the sum couldn’t be deduced from the product.
11=2+9, 29=18; 18 also equals 36, so the sum can’t be deduced
11=3+8, 38=24; 24 also equals 212, so the sum can’t be deduced
11=4+7, 47=28, 28 also equals 214, so the sum can’t be deduced
11=5+6, 56=30 ; 30 also equals 215, so the sum can’t be deduced
Ms can then say that the product is 24, because no other product has
just one non-deducible sum.
a=3, b=8. ab=24, a+b=11[/spoiler]
This is as far as I was able to follow it:
Ms says that he knew Mp wouldn’t know the answer. The only information Ms had beforehand was the sum of two unknown numbers. The only way that sum could give Ms any signficiant information would be if it was odd. That would tell Ms that one of the numbers was odd and one was even. (An even sum could have been the sum of either two evens or two odds). Ms knows that if the even number was a multiple of two, then Mp couldn’t possibly know which way the product factored. (Example 4N=2(2N), etc.) That leaves just the possibility that the even number is 2. If the sum was greater than 101, then it couldn’t be the sum of 2 plus a number less than 100. So if the sum is greater than 101, Ms can be completely confident that the product of the two unknown numbers can be factored more than one way.
Except that doesn’t prove the sum IS greater than 101, there might be other logic I’m missing which would leave Ms confident even with a lesser sum. Anyone?
I think we can stop spoiler-boxing things now, no?
This is incorrect. If Ms has a sum of 11, then, in addition to the 38 = 24 solution for the product, Ms can’t be sure at the end that the product isn’t 29 = 18 or 47 = 28, instead. [The only other factorization of 18 is 36, and 3+6 = 9 is not a guaranteed “non-deducible sum”; i.e., it is incompatible with Ms’s first statement, since it would allow for the alternative 2+7 = 9, and 27 is a unique factorization. Similarly, the only other factorization of 28 is 214, and 2+14 = 16 is incompatible with Ms’s first statement, since it would allow for the alternative 3 + 13, and 3*13 is a unique factorization.]
Thus, a = 3 and b = 8 will allow the first three statements to be made, but will falter on the fourth and last one.