Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This is one of the most beautiful and difficult puzzles I have encountered. I have talked to several people, but I still don't know the solution - I do however know that the solution exists.

Someone imagined two positive whole numbers. Both numbers are greater than $1$, and less than $21$. That person tells the sum of those two numbers to mathematician A, and the product of those two numbers to mathematician B. Couple of days later, A and B talk to each other:

A: There is no way for you to find the sum.
B: But I know the sum now!
A: And now I know the product.

Which two numbers have person imagined?

share|improve this question
2  
I suspect your question is slightly inaccurate based on mathematik.uni-bielefeld.de/~sillke/PUZZLES/logic_sum_product –  picakhu Nov 17 '11 at 15:59
    
@picakhu: What's inaccurate? Looks like the same question to me. –  joriki Nov 17 '11 at 16:01
    
@joriki, its 4 statements vs 3. The first statement is important. –  picakhu Nov 17 '11 at 16:05
3  
This is well known –  Marc van Leeuwen Nov 17 '11 at 16:05
1  
My favorite version of this problem, with a unique solution (unlike the OP's version), is the "Mediterranean version", which I read in this paper: A teacher says to students $P$ and $S$: "I've secretly chosen two positive integers $x$ and $y$ with $x \le y$. I've told their sum $s=x+y$ only to $S$, and their product $p=xy$ only to $P$." $S$ then says to $P$, "You can't determine $s$", to which $P$ replies, "In that case $s=136$". Determine $x$ and $y$. –  r.e.s. Nov 17 '11 at 18:03

4 Answers 4

up vote 1 down vote accepted

There is in fact no solution to this puzzle. Martin Gardner realized this after presenting it in Scientific American:

'As hundreds of readers have pointed out, the "impossible problem" given in this department for December turned out to be literally impossible.' (For this quote and an explanation, see here.)

For the puzzle to have a solution, there would have to be an admissible sum such that no matter how it is split up into two admissible addends, the resulting product also has at least one other admissible factorization. The following short Java program checks that there is no such admissible sum.

public class SumAndProduct {
    final static int min = 2;
    final static int max = 20;

    public static void main (String [] args) {
        outer:
        for (int sum = min + min;sum <= max + max;sum++) {
            for (int i = min;i <= max;i++) {
                int j = sum - i;
                int product = i * j;
                int nfactorizations = 0;
                for (int a = min;a <= max;a++) {
                    int b = product / a;
                    if (min <= b && b <= max && a * b == product)
                        nfactorizations++;
                }
                nfactorizations = (nfactorizations + 1) / 2;
                if (nfactorizations == 1)
                    continue outer;
            }

            System.out.println ("sum " + sum + " can't be determined");
        }
    }
}

Note that the solution $(2,6)$ given on this page linked to by picakhu is incorrect. The sum is $8$, which could be the result of $(3,5)$, which has the unique factorization $3\cdot5$ that would allow B to deduce the sum $8$. The solution originally claimed by Martin Gardner was $(4,13)$.

share|improve this answer

As joriki noted this problem is impossible.

The reason it is impossible is that there are multiple solutions and so the mathematicians would not be able to declare that they had discovered each over's numbers.

The conversation gives us additional constraints on the solutions. In order for mathematician A to declare that there is no way that B could determine his sum that means he has ascertained that:

  1. His sum is NOT the sum of two primes.
  2. His sum can never be created using two numbers whose product has a unique factorisation in the interval [2, 20] i.e. 20+20=40, => 20*20=400 (I believe the upshot of this is that the sum must be less than 13 as 13=2+11 and 11*2 = 22 > 20)

(Please note I did the following on paper and may have made a mistake somewhere.)

From the bounds of the problem we know that the possible sums range from 4 to 40 inclusive. Using the first constrain we can eliminate many of these. If take all possible combinations of adding two primes (in the interval [2, 20]) and eliminate those sums we are left with the following as possible sums:

11, 17, 23, 25, 27, 29, 31, 33, 35, 37, 39, 40

Applying constraint 2 we find that the sum must be 11. This allows mathematician B to declare "But I know the sum now!"

In order for there to no unique factorisation we must be able to create the sum (11) using a non-prime in the interval [2, 20]. To find the solutions we must subtract each non-prime from the sum. For each valid solution the result will be in the interval [2, 20]. This leads to the following set of four solutions.

  1. (4, 7) Product: 28 = 2 * 14.
  2. (5, 6) Product: 30 = 3 * 10 = 2 * 15
  3. (3, 8) Product: 24 = 4 * 6 = 2 * 12
  4. (2, 9) Product: 18 = 3 * 6

Note: joriki's java code is incorrect. Rather than proving that there are no solutions it in fact finds many false positives.

When running the program "can't be determined" is never output meaning the program does find what it believes are solutions.

'j' is not tested to check whether it is in range, creating many false positives.

sum = 15 has a unique factorisation 3*5, but the program counts 2 factorisations in the form of 3*5 & 5*3. This means that nfactorizations ends up being 1 and thus creating a false positive.

Even when these bugs are fixed the program tests for cases such as sum = 7 and finds the solution (3, 4). This also is wrong as mathematician A could not look at the sum, 7 and conclude that mathematician B would not be able to find the sum. This is because 7 can be formed by adding 2 and 5, both of which are prime. B would be able to look at his product of 10 and deduce that the numbers are 2 and 5 and that the sum is 2+5=7.

share|improve this answer

A reference:
A. K. Austin, "A calculus for know/don't know problems" Mathematics Magazine Vol. $49$, No. $1$, Jan., 1976

share|improve this answer

I think I found two different solutions to this problem:

$(4,13)$

$(16,19)$

I believe these are all possible solutions to the problem as stated.

joriki, are these not valid solutions? If so, could you explain why?

share|improve this answer
    
If we bound the problem by requiring that the sum is less than 100 and remove the restriction that the numbers are less than 21, only (4,13) is a solution. The less than 21 restriction makes (16,19) an additional solution. –  Brian Dec 1 '11 at 2:58
1  
(4, 13) is not a solution because the second player knows the sum is 17, since there is a unique factorization of 52 into two factors in {2, ..., 20}. Similarly with (16, 19). –  Charles Dec 1 '11 at 21:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.