Know, Don't Know Problem

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

Search

Search WWW

Search DelphiForFun.org

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 feedback 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.  Thanks

 


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.

Mensa Daily Puzzlers

For over 15 years Mensa Page-A-Day calendars have provided several puzzles a year for my programming pleasure.  Coding "solvers" is most fun, but many programs also allow user solving, convenient for "fill in the blanks" type.  Below are Amazon  links to the two most recent years.

Mensa 365 Puzzlers  Calendar 2017

Mensa 365 Puzzlers Calendar 2018

(Hint: If you can wait, current year calendars are usually on sale in January.)

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

Problem Description

Two integers, A and B, each between 2 and 100 inclusive, have been chosen.
The product, AB, 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:  

bullet 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.
bulletObservation 1: The product AB can't be the product of 2 primes, otherwise Dr. P would  know the solution.
bulletObservation 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.
bulletObservation 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. 
bulletAction 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 program for specifics.)
bulletObservation 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.)   
bulletAction 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
bulletAction 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 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 

bulletDownload source
bulletDownload  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. 

 

Original Date: August 10, 2002 

Modified: July 29, 2017

 
  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.