# Maths problem

**URL:** <https://boards.straightdope.com/t/maths-problem/485504>\
**Category:** Factual Questions\
**Created:** [February 12, 2009, 7:12am UTC](https://boards.straightdope.com/t/maths-problem/485504 "2009-02-12T07:12:51Z")\
**Posts on this page:** 20\
**Page:** 2

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [February 12, 2009, 8:57pm UTC](https://boards.straightdope.com/t/maths-problem/485504/21 "2009-02-12T20:57:21Z")

</div>

> [@Quercus](#):
>
> Or am I all wrong, here?

No, you are, so far as I can see, quite correct.

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [February 12, 2009, 9:03pm UTC](https://boards.straightdope.com/t/maths-problem/485504/22 "2009-02-12T21:03:51Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![MindWanderer](https://avatars.discourse-cdn.com/v4/letter/m/d78d45/32.png) [@MindWanderer](https://boards.straightdope.com/u/MindWanderer)\
**Post date:** [February 12, 2009, 9:41pm UTC](https://boards.straightdope.com/t/maths-problem/485504/23 "2009-02-12T21:41:09Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [February 12, 2009, 9:42pm UTC](https://boards.straightdope.com/t/maths-problem/485504/24 "2009-02-12T21:42:15Z")

</div>

Why have you set an upper limit of 20? The OP picks an upper limit of 100.

---

<div class="post-metadata">

**Author:** ![MindWanderer](https://avatars.discourse-cdn.com/v4/letter/m/d78d45/32.png) [@MindWanderer](https://boards.straightdope.com/u/MindWanderer)\
**Post date:** [February 12, 2009, 9:47pm UTC](https://boards.straightdope.com/t/maths-problem/485504/25 "2009-02-12T21:47:11Z")

</div>

Woops. I misread the question. I will take another look at it with the correct numbers.

---

<div class="post-metadata">

**Author:** ![Gus\_Gusterson](https://avatars.discourse-cdn.com/v4/letter/g/85f322/32.png) [@Gus\_Gusterson](https://boards.straightdope.com/u/Gus_Gusterson)\
**Post date:** [February 12, 2009, 9:48pm UTC](https://boards.straightdope.com/t/maths-problem/485504/26 "2009-02-12T21:48:09Z")

</div>

> [@Indistinguishable](#):
>
> Huh? What do you mean by this? What is “the answer” if not the original two 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.

---

<div class="post-metadata">

**Author:** ![MindWanderer](https://avatars.discourse-cdn.com/v4/letter/m/d78d45/32.png) [@MindWanderer](https://boards.straightdope.com/u/MindWanderer)\
**Post date:** [February 12, 2009, 10:36pm UTC](https://boards.straightdope.com/t/maths-problem/485504/27 "2009-02-12T22:36:06Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![MindWanderer](https://avatars.discourse-cdn.com/v4/letter/m/d78d45/32.png) [@MindWanderer](https://boards.straightdope.com/u/MindWanderer)\
**Post date:** [February 12, 2009, 10:49pm UTC](https://boards.straightdope.com/t/maths-problem/485504/28 "2009-02-12T22:49:31Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\
**Post date:** [February 12, 2009, 11:15pm UTC](https://boards.straightdope.com/t/maths-problem/485504/29 "2009-02-12T23:15:26Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![astro](https://avatars.discourse-cdn.com/v4/letter/a/9dc877/32.png) [@astro](https://boards.straightdope.com/u/astro)\
**Post date:** [February 13, 2009, 8:44am UTC](https://boards.straightdope.com/t/maths-problem/485504/30 "2009-02-13T08:44:07Z")

</div>

This is called “The Perfect Logicians” puzzle

[Solution (and explanation) here](http://stason.org/TULARC/self-growth/puzzles/339-logic-number-p.html)

---

<div class="post-metadata">

**Author:** ![Carmady](https://avatars.discourse-cdn.com/v4/letter/c/f04885/32.png) [@Carmady](https://boards.straightdope.com/u/Carmady)\
**Post date:** [February 13, 2009, 10:40am UTC](https://boards.straightdope.com/t/maths-problem/485504/31 "2009-02-13T10:40:25Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Carmady](https://avatars.discourse-cdn.com/v4/letter/c/f04885/32.png) [@Carmady](https://boards.straightdope.com/u/Carmady)\
**Post date:** [February 13, 2009, 11:47am UTC](https://boards.straightdope.com/t/maths-problem/485504/32 "2009-02-13T11:47:41Z")

</div>

> [@Indistinguishable](#):
>
> It’s easy to make brash simplifying hypotheses, stumble upon one potential answer, and then check that it actually works.

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.

---

<div class="post-metadata">

**Author:** ![shijinn](https://avatars.discourse-cdn.com/v4/letter/s/cc9497/32.png) [@shijinn](https://boards.straightdope.com/u/shijinn)\
**Post date:** [February 13, 2009, 3:03pm UTC](https://boards.straightdope.com/t/maths-problem/485504/33 "2009-02-13T15:03:27Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [February 13, 2009, 6:40pm UTC](https://boards.straightdope.com/t/maths-problem/485504/34 "2009-02-13T18:40:06Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [February 13, 2009, 6:47pm UTC](https://boards.straightdope.com/t/maths-problem/485504/35 "2009-02-13T18:47:27Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [February 13, 2009, 7:32pm UTC](https://boards.straightdope.com/t/maths-problem/485504/36 "2009-02-13T19:32:07Z")

</div>

(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).)

---

<div class="post-metadata">

**Author:** ![Hyperelastic](https://avatars.discourse-cdn.com/v4/letter/h/a3d4f5/32.png) [@Hyperelastic](https://boards.straightdope.com/u/Hyperelastic)\
**Post date:** [February 14, 2009, 12:40am UTC](https://boards.straightdope.com/t/maths-problem/485504/37 "2009-02-14T00:40:40Z")

</div>

Never mind.

---

<div class="post-metadata">

**Author:** ![Hyperelastic](https://avatars.discourse-cdn.com/v4/letter/h/a3d4f5/32.png) [@Hyperelastic](https://boards.straightdope.com/u/Hyperelastic)\
**Post date:** [February 14, 2009, 12:44am UTC](https://boards.straightdope.com/t/maths-problem/485504/38 "2009-02-14T00:44:21Z")

</div>

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=2_12  
24=3_8  
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 3_11=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 5_5=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, 2_9=18; 18 also equals 3_6, so the sum can’t be deduced  
11=3+8, 3_8=24; 24 also equals 2_12, so the sum can’t be deduced  
11=4+7, 4_7=28, 28 also equals 2_14, so the sum can’t be deduced  
11=5+6, 5_6=30 ; 30 also equals 2_15, 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]

---

<div class="post-metadata">

**Author:** ![Lumpy](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/lumpy/32/446_2.png) [@Lumpy](https://boards.straightdope.com/u/Lumpy)\
**Post date:** [February 14, 2009, 2:10am UTC](https://boards.straightdope.com/t/maths-problem/485504/39 "2009-02-14T02:10:07Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [February 14, 2009, 2:19am UTC](https://boards.straightdope.com/t/maths-problem/485504/40 "2009-02-14T02:19:31Z")

</div>

I think we can stop spoiler-boxing things now, no?

> [@Hyperelastic](#):
>
> I get a different answer than the linked sites. Maybe I’m misreading the question.  
> …  
> Ms can then say that the product is 24, because no other product has  
> just one non-deducible sum.

This is incorrect. If Ms has a sum of 11, then, in addition to the 3_8 = 24 solution for the product, Ms can’t be sure at the end that the product isn’t 2_9 = 18 or 4_7 = 28, instead. [The only other factorization of 18 is 3_6, 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 2_7 is a unique factorization. Similarly, the only other factorization of 28 is 2_14, 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.

[Previous page](https://boards.straightdope.com/t/maths-problem/485504.md?page=1)

[Next page](https://boards.straightdope.com/t/maths-problem/485504.md?page=3)