5
$\begingroup$

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?

$\endgroup$
8
  • 2
    $\begingroup$ I suspect your question is slightly inaccurate based on mathematik.uni-bielefeld.de/~sillke/PUZZLES/logic_sum_product $\endgroup$ – picakhu Nov 17 '11 at 15:59
  • $\begingroup$ @picakhu: What's inaccurate? Looks like the same question to me. $\endgroup$ – joriki Nov 17 '11 at 16:01
  • $\begingroup$ @joriki, its 4 statements vs 3. The first statement is important. $\endgroup$ – picakhu Nov 17 '11 at 16:05
  • 3
    $\begingroup$ This is well known $\endgroup$ – Marc van Leeuwen Nov 17 '11 at 16:05
  • 1
    $\begingroup$ 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$. $\endgroup$ – r.e.s. Nov 17 '11 at 18:03
1
$\begingroup$

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)$.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

If the range is [2..20] then there is no solution. If the range is [2..62] then (4,13) IS solution. Why?

In the range [2..62] first we find those sums that can produce only products that can originate from more then one sum. Those are: 11, 17, 23, 27, 29, 35 and 37. This is set of possible sums in the solution - all other sums produce at least one product which can only be produced from one sum therefore allowing A to guess the sum. Lets call this set set PS.

Now we examine each of the members in this set:

  1. Find all products that this set produces.
  2. For every product found check if that product can be produced from at least two memebers of set PS. These are NOT solutions because A then could not guess the sum.
  3. For every product found check if that product can be produced from exactly one member of set PS and ALSO from some other sum outside of set PS. These are possible solutions because A can guess the sum.

All we need is to find member of PS for which there is only one possible sollution and all others are not solutions.

It happens that 17 is the only sum for which this is true:

Sum 17 generate these products: 30,42,52,60,66,70,72 1. Product 30 can originate from sums 11,13 and 17 - not solution 2. Product 42 can originate from sums 13,17 and 23 - not solution 3. Product 52 can originate from sums 17 and 28 - SOLUTION 4. Product 60 can originate from sums 16,17,19,23, and 32 - not solution 5. Product 66 can originate from sums 17,25 and 35 - not solution 6. Product 70 can originate from sums 17,19 and 37 - not solution 7. Product 72 can originate from sums 17,18,22,27 and 38 - not solution

A knows product is 52 and it can originate from 17 and 28 B tells him "You cannot know the sum" - this tells A that sum is 17 because only sums for which B can make such a claim are 11, 17, 23, 27, 29, 35 and 37 and of these 17 is correct for A. A tells "Now I know the sum" - this tells B that product is 52 because all other products - 30,42,60,66,70,72 can also be created from other possible sums - 11, 23, 27, 29, 35 and 37. Only 52 can be created from ONE possible SUM - 17 and therefore B tells "Now I know the product"

$\endgroup$
0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ – Brian Dec 1 '11 at 2:58
  • 1
    $\begingroup$ (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). $\endgroup$ – Charles Dec 1 '11 at 21:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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