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:  

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!

April 19, 2013: Recognizing (finally) that the problem I was solving (not knowing sum or product) was is quite different from the problem the Drs. S and P had to solve (knowing sum or product), I modified the above text and added a "Walkthrough" page to the program showing the logic that the professors must have used in reaching their conclusions.

April 23, 2013: One more update to Version 3.1 today added a second "Walk-through" page, this one interactive, taking any sum and product and stepping through the analysis from each professor's point of view.  This was motivated by a viewer who doubted that the validity of the second solution for the 500 upper limit case.  To eliminate the possibility that of a bug in the original solver code, I needed to step through as the Professors would have done.  The size of the numbers makes this an order of magnitude harder than the first "Walk-through" and justified writing the additional code.        

  Running/Exploring the Program 

Suggestions for Further Explorations