Problem Description

Two integers, A and B, each between 2 and 100 inclusive, have been chosen.
The product, A×B, is given to mathematician Dr. P. The sum, A+B, is given to mathematician Dr. S. They each know the range of numbers. Their conversation is as follows:

P: "I don't have the foggiest idea what your sum is, S."
S: "That's no news to me, P. I already knew that you didn't know. I don't know either."
P: "Aha, NOW I know what your sum must be, S!"
S: "And likewise P, I have figured out your product!!"

What are the numbers?.

Background & Techniques

Here's a puzzle that seems impossible to solve at first glance.  In fact Martin Gardner called it "The Impossible Problem" in a 1979 Scientific American "Mathematical Games" article.  I haven't seen the article in any of his anthologies, but it is mentioned in the second reference below.   That reference also has includes probably a dozen variations of the problem, mostly from math and puzzle newsgroups. 

If you want to wok on the problem without a computer, you can reduce the upper limit of the number range to 20.  With the computer, as the upper limit is raised, the solution soon becomes non unique and S could not make his final statement.  

Here's my approach to solving the problem, lifted from the program:

• Observation 1: The product A×B can't be the product of 2 primes, otherwise Dr. P would figure out the numbers immediately.
• Observation 2: The product cannot be the cube of a prime otherwise there would only be one choice for A and B and Dr. P would have figured that out also.
• Observation 3: The sum A+B must not be expressible as sum of two primes, otherwise Dr. S could not have been sure in advance that Dr. P did not know the numbers. 
• Action 1: So Dr. S can make a list of all possible sums which pass the filters defined by the above three observations. (Call it SumList1)
• Observation 4: Since Dr. P says that he knows the numbers in his second response, there must be only one factorization of his product into two numbers whose sum is in Sumlist1 (which he was smart enough to build for himself once Dr. S told him that he did not know the numbers either.)
• Action 2: Dr. S is smart enough to make a second list, SumList2, of all possible A, B pairs that meet the criteria of Observation 4 once he knows that Dr. P had a unique factorization. Of these possible pairs, there must be only one whose sum occurs only once, otherwise Dr. S could not say that he knows the number also.
• Action 3: By keeping a count of how many times each unique sum occurs (and the numbers that form that sum) in Sumlist2, Dr. S finds one that only occurs one time. This lets him announce that he too knows the values of A and B.

Here are a couple of the best references I've found.  This  Dr. Math page is a reasonably understandable discussion.    And Torsten Sillke has put together this  good collection of references mainly from puzzle and mathematics newsgroup archives.

Notes for Programmers

The program is a pretty straightforward implementation of the above "Approach" list.    This is a case where deciding what to do was much harder than doing it.  I used the previously posted U_Prime unit from the  Prime Factors 1 program  unit to find prime factorizations and test for primality where necessary.    

There are less than 100 lines of code here (Beginners size), but I think I'll classify the program as Intermediate anyway so as not to scramble the brains of any true beginners that might tackle it.  

Addendum November 8, 2007:  Finally, an update!  One of the disadvantages of being a high achiever is amount of time spent finding answers to questions of little significance.  Kind of like climbers and their mountains - we do it because they are there.   The case in point is answering the question "If the upper limit of the know-don't know problem is increased, why do solutions appear which have values less than the previous lower limit?"  

A viewer wrote asking for a version of the program which would find solutions with integers up to 999.  He is (or was) involved in a Geo-Caching game which provided a coordinates clue in the form of the know-don't know puzzle.    It was a simple matter to increase the upper limit in the code; I sent him the results and he thanked me profusely.  I decided to post this new version just in case someone, somewhere, someday, would have a similar request.   While testing, I noticed results that did not seem correct.  With an upper limit of 400, there is only a single solution (4,13), the same solution that exists in the original problem.  But, increase the upper limit to 500, and a second pair of integers shows up (4,61).  In other words, the best that  S and P could conclude is that the numbers are either (4,13) or (4,61).    61 is less than 100 and way less than 400, so where's the bug?   Why isn't (4,61) and solution in the lower limit cases?  No bug; after many hours of "debugging", here's the explanation:  (Be forewarned - the following explanation is not easy to follow, no matter how much I tried to simplify it.) 

Observation 4 is the key: "... there must be only one factorization of P's product into two numbers whose sum is in Sumlist1".   Among all the pairs that P (or his computer) might have to check are those summing to 65.  (Remember, he knows his product, we do not.).  Product 244 has  4* 61 as the only factorization whose sum is on Sumlist1), so it add one to the count in SumList2[65],  "unique" factorizations A*B with A+B=65.  I'll use "unique" from now on to mean the only factorization of P into A*B with A+B on Sumlist1.  874 (19*46) also qualifies as "unique" unless the upper limit is above 437 in which case 2*437  is a second factorization.    Having two ways to factor 874 is enough to prevent incrementing the count of "unique" factorization of  A*B products with A+B=65.   And, since that was already set to 1 with the 4*61=244, 4+61=65 case, the 500 upper limit produces (4,61) as a solution.   If 400 is the upper limit, then 2*437 is not checked and 19*46 appears to be a "unique" factorization of 874.  In that case we have two sets of results (4,61) and (19,46) whose product has a unique factorization and which sum to 65.   This is enough to prevent it from being a solution.  Whew!

 Running/Exploring the Program 

• Download source
• Download  executable

Suggestions for Further Explorations

	Other variations of the problem could be added as additional Tabsheets.
	November 8, 2007 : Upper and lower range of numbers could be user inputs.  (Arrays would change from static to dynamic.)
	SumList1 and SumList2 form a single logical list and it should be quite easy to combine them.   I left them as separate lists simply because it  makes it easier to understand the process.