As of October, 2016, Embarcadero is offering a free release
of Delphi (Delphi
10.1 Berlin Starter Edition ). There
are a few restrictions, but it is a welcome step toward making
more programmers aware of the joys of Delphi. They do say
"Offer may be withdrawn at any time", so don't delay if you want
to check it out. Please use the
link to let me know if the link stops working.
Support DFF - Shop
If you shop at Amazon anyway, consider using
this link. We receive a few cents from each purchase.
Support DFF - Donate
If you benefit from the website, in terms of
knowledge, entertainment value, or something otherwise useful,
consider making a donation via PayPal to help defray the
costs. (No PayPal account necessary to donate via credit
card.) Transaction is secure.
e-mail with your comments about this program (or anything else).
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
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?.
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
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:
| Note that even though there
are similarities, our problem, finding the solution or solutions
to the problem without knowing either the sum or product of the two
numbers is a much larger problem than the professors faced. |
|Observation 1: The product A×B can't be the product of 2 primes, otherwise Dr. P would
know the solution.|
|Observation 2: The product also cannot be the cube of a prime otherwise there would only be one choice for
A and B (p2 * p) and Dr. P would have figured that out also.|
|Observation 3: The sum A+B given to Dr. S 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 we will make a list of all possible sums which pass the filters defined by
the above three observations. Call it SumList1. (Dr.
S at this point would need only to examine pairs of numbers that sum to
his given value. See the "Walkthrough" page in the
|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.
(Dr. P at this point only knows the pairs of numbers which sum to the
two term factorizations of the product he was given. See the
program Walkthrough page in the program for specifics.)
|Action 2: Once he knows that Dr. P had a unique
factorization, Dr. S is smart enough to make a second list from
his first sum list keeping those that meet the criteria of Observation 4. Of these
possible pairs, there must be only one whose sum occurs in only one
way, otherwise Dr. S could not say that he knows the number also.
We will do the same thing with our larger sum list |
|Action 3: For our solution, by keeping a count of how many times each unique sum occurs
(and the numbers that form that sum) in Sumlist2, we find
unique sums. |
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
good collection of references mainly from puzzle and mathematics
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
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
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, "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.
for Further Explorations
variations of the problem could be added as additional Tabsheets.
||November 8, 2007 :
and lower range of numbers could be user inputs. (Arrays would
change from static to dynamic.)
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.
Date: August 10, 2002
February 18, 2016