The Impossible Puzzle

The numbers are 4 and 13. First, I'll convince you that these are a valid solution, and leave for another post (or poster) to describe how to actually find the solution.

Note of course that if one knows both the sum and the product it does uniquely determine the two numbers.

Here's how it all goes down, chronologically, complete with inner monologues:

Me (whispered to Sam): "The sum is 17."

What Sam learns: They might be 2 and 15, 3 and 14, ..., or 8 and 9. They are one odd and one even; they can't both be prime. Paula will be whispered one of: 30, 42, 52, 60, 66, 70 or 72. None is a product of primes, so she won't know the numbers yet.

Me (whispered to Paula): "The product is 52."

What Paula learns: the numbers are either 4 and 13 or 2 and 26, so Sam has been whispered either 17 or 28.

Paula: "I don't know the numbers."

What Sam learns: nothing.

Sam: "I knew you didn't."

What Paula learns: his sum cannot be expressed as a sum of two primes -- therefore it must be odd (Goldbach conjecture). The numbers are 4 and 13! I've got it!

What Sam learns: she knows my sum is odd now. The possibilities are:

• If she was told 30, she knows that my sum is one of 11, 13 or 17.
• If 42, she knows my sum is 13, 17 or 23.
• If 52, she knows my sum is 17.
• If 60, she knows my sum is 17, 19 or 23.
• If 66, she knows my sum is 17, 25 or 35.
• If 70, she knows my sum is 17, 19 or 37.
• If 72, she knows my sum is 17 or 27.

Sam: "I don't either."

What Paula learns: nothing. (WE, the puzzle solvers, need to know this in order to eliminate other possibilities, as we'll get to later...)

Paula: "Ah, now I know them."

What Sam learns: Aha! Only if the product is 52 can she know my sum has to be 17.

Sam: "Now I know them too."

Hopefully this convinces you that 4 and 13 are a solution. How to find that solution is a subject for another post (perhaps you want to make it?).

Here's a short, simple, declarative Python program to deduce the numbers. Every variable prefixed with 'sam' is a set of sums, and every variable prefixed with 'paula' is a set of products.

from collections import defaultdict
sumsToProds = defaultdict(set)
prodsToSums = defaultdict(set)
for x in range(2, 100):
  for y in range(x+1, 100-x):
    s = x + y
    p = x * y
    sumsToProds[s].add(p)
    prodsToSums[p].add(s)

# Paula doesn't know iff the sum isn't unique for her product
paulaDoesntKnow = set([k for k, v in prodsToSums.items() if len(v) >= 2])
# Sam doesn't know iff the product isn't unique for his sum
samDoesntKnow = set([k for k, v in sumsToProds.items() if len(v) >= 2])
# Sam knows Paula doesn't know iff all of the products for his sum fall under 'Paula doesn't know'
samKnowsPaulaDoesnt = set([k for k in samDoesntKnow if sumsToProds[k] <= paulaDoesntKnow])
# Paula knows now iff the number of sums which fit her informational model are reduced to 1 by Sam's statement
paulaKnowsNow = set([k for k in paulaDoesntKnow if len(prodsToSums[k].intersection(samKnowsPaulaDoesnt)) == 1])
# Sam knows now iff the number of products which fit his informational model are reduced to 1 by Paula's statement
samKnowsNow = set([k for k in samKnowsPaulaDoesnt if len(sumsToProds[k].intersection(paulaKnowsNow)) == 1])

print samKnowsNow # set([17])
print sumsToProds[17].intersection(paulaKnowsNow) # set([52])
# Basic algebra yields 4 + 13 = 17, 4 * 13 = 52

Extra: Consider the parameterized problem P(N), where N is the exclusive upper limit of the sum of the two numbers. P(100) is solvable, and yields (4, 13). I was curious to see at what N, (or if there even was such an N), where P(N) is unsolvable. It turns out N exists! And N < 2000 - see if you can find it.

Using Goldbach's conjecture and similar logic in Bourrillion's post, we see that the sum must be one of the numbers that cannot be expressed as 2 + p, for any prime p. The first few of these numbers are 11, 17, 23, 27, 29, 35, 37.

We can list out these numbers and their possible products.

• 11: 18, 24, 28, 30

• 17: 30 , 42 , 52, 60 , 66 , 70 , 72

• 23: 42 , 60 , ...

• 27: 50, 72 , ...

• 29: 54, 78, ...

• 35: 66 , ...

• 37: 70 , ...

Now from the conversation, we know that

1. The product is unique to a certain sum, and

2. that the rest of the products that correspond to that sum appear in another sum's list.

The first observation follows from the fact that Paula is able to identify the sum -- it must appear on a single list. If Sam knows the product from this information, that means that the rest of his possible products are not unique; otherwise, Paula could not be able to pin down the sum.

Notice that from the numbers I have provided, all of 30, 42, 60, 66, 70, and 72, which are products in 17's list, appear on other lists, as indicated in bold. This leaves 52 -- does it appear on another list? No, because it is clear that the lists are increasing, and since it is not already listed elsewhere, it can never be listed again.

Therefore the sum is 17 and the product is 52, meaning the numbers are 4 and $\fbox{13}$ .

Definitions

$\begin{aligned} a,\:b&\in \{2;\:\ldots;\:99\}:&&\text{two distinct unknown numbers}\\[.5em] \hat{s}&:=a+b:&&\text{Sam's number, all possible values }s\text{ are collected in }S\\[.5em] \hat{p}&:=ab:&&\text{Paula's number, all possible values }p\text{ are collected in }P\\[.5em] \mathbb{P}&:=\{p\text{ prime},\: p<100\}:&&\text{set of the first 25 primes} \end{aligned}$ If $s\in S$ and $p\in P$ are generated by the same unknown numbers, we say " $s,\:p$ are connected".

By symmetry, it's enough to consider $a<b$ . Using the upper bound for the sum $\hat{s}<100$ , we find estimates for $S,\:P$ : $\begin{aligned} \hat{s}&=a+b>2a\geq 4; &&& b&=\hat{s}-a< 100-2=98 &&&\Rightarrow&&&& S&=\{5;\:\ldots;\:99\},& P&\subseteq\{2\cdot 3;\:\ldots;\:96\cdot 97\} \end{aligned}$ Then realize that if you know both $\hat{s},\:\hat{p}$ , you can calculate $a,\:b$ : Knowing one pair is equivalent to knowing the other!

Finally, notice there are some special products and sums that are connected to exactly one value. For example $p=39$ and $s=5$ : $\begin{aligned} p=39&=3\cdot 19 &\leftrightarrow&&3+13&=16;&&&&& s=5&=2+3&\leftrightarrow &&2\cdot 3&=6 \end{aligned}$ If Paula gets such a product, she can safely guess Sam's number, and vice versa! For such products and sums that are connected to only one value, we will say " $p$ determines $s$ " and " $s$ determines $p$ ", respectively.

The discussion step by step

Let's analyze the statements of Paula and Sam's discussion, step by step, to find out what they know about their numbers:

$\begin{aligned} &\text{Paula: "I don't know the numbers!"} &\Leftrightarrow&&&\text{"}\hat{p} \text{ doesn't determine }\hat{s}\in S\text{"} &\Leftrightarrow && \hat{s},\:\hat{p}&\in S_1,\:P_1&&(1)\\[1em] &\text{Sam: "I knew you didn't!"} &\Leftrightarrow&&& \text{"}\hat{s}\text{ isn't determined by any }p\in P\text{"} &\Leftrightarrow && \hat{s},\:\hat{p}&\in S_2,\:P_2&&(2)\\[1em] &\text{Sam: "I don't know either!"} &\Leftrightarrow&&& \text{"}\hat{s}\text{ doesn't determine }\hat{p}\in P_2\text{"} &\Leftrightarrow && \hat{s},\:\hat{p}&\in S_3,\:P_3&&(3)\\[1em] &\text{Paula: "Now I know them!"} &\Leftrightarrow&&& \text{"}\hat{p}\text{ determines }\hat{s}\in S_3\text{"} &\Leftrightarrow && \hat{s},\:\hat{p}&\in S_4,\:P_4&&(4)\\[1em] &\text{Sam: "Now I know them, too!"} &\Leftrightarrow&&& \text{"}\hat{s}\text{ is determined by exactly one }p\in P_3\text{"} &\Leftrightarrow && \hat{s},\:\hat{p}&\in S_5,\:P_5&&(5) \end{aligned}$

The shrinking sets $S_k,\: P_k$ contain the remaining sums and products that Paula and Sam had not been able to eliminate.

Proof

The conditions (1) - (3) are ridiculously tedious to test by hand - they would need every valid factorization of every product $p\in P$ and every valid partition of every sum $s\in S$ . Instead, we try to find efficient ways to eliminate some values from $S$ , as it as it contains much fewer elements than $P$ . We show conditions (1), (2) lead to (1'), (2'), respectively:

$\begin{aligned} \hat{p}&\neq p_1p_2,& \hat{p}&\neq p_1^3,& \hat{p}&\neq kp_3&&&\text{for any}&&&& p_1,\:p_2,\:p_3&\in\mathbb{P},& p_1&<p_2,& p_3 \geq 50&&&&&(1')\\[1em] \hat{s}&\neq p_1+p_2,& \hat{s}&\neq p_1^2+p_1,& \hat{s}&\leq 54&&&\text{for any}&&&&p_1,\:p_2,\:p_3&\in\mathbb{P},& p_1&<p_2&&&&&&(2') \end{aligned}$

To verify statement (1'), assume $\hat{p}$ is not of either of the three forms in (1'). In all cases, $\hat{p}=ab$ has exactly one valid factorization such that $a,\:b>1$ as well as $a < b$ . But using that single factorization, Paula would know both numbers - contradiction!

For statement (2'), assume $\hat{s}$ is not of either of the three forms in (2'). Then it is connected to a product of one of the forms: $\begin{aligned} p&=p_1p_2,&p&=p_1^3,& p=53(s-53) \end{aligned}$ In all cases, it is possible for Paula to know the numbers by (1'). But then Sam can't be sure that Paula did not know the numbers in the first place - contradiction!

• Conditions (2'), (3):

  We eliminate all $s>54$ from $S$ straight away. Then we calculate all sums $p_1+p_2\leq 54$ with primes $p_1<p_2$ and eliminate them from the remaining values. Even doing it by hand is fast (about 3min on paper), as most combinations are either out of bounds or dublicates.

  From the remaining list, we eliminate $6=2^2+2$ , and $51$ , because it is determined by $p=17\cdot 34$ , to end up with the following 10 sums: $\begin{aligned} \{11 ;\: 17 ;\: 23 ;\: 27 ;\: 29 ;\: 35 ;\: 37 ;\: 41 ;\: 47 ;\: 53\}&=S_2=S_3,&&& P_2&=P_3 \end{aligned}$ Even though it is a bit tedious, we test all of their 145 valid partitions to make sure none of the sums is determined by any of the products $p\in P$ they are connected to (about 15min on paper). The products we checked make up the set $P_2$

  Every sum $s\in S_2$ is connected to multiple products $p\in P_2$ , so we cannot eliminate any values with condition (3)!

• Condition (4):

  We need a way to identify sums $s\in S_3$ that are determined by products $p\in P_3$ . It's very helpful to check for two kinds: $\begin{aligned} s & \overset{?}{=} 2^m + p_1&\vee &&s & \overset{?}{=} 2^m + p_1p_2&&&p_1,\:p_2&\in\mathbb{P},&2&<p_1\leq p_2,&m>0 \end{aligned}$

  If we find a valid partition of the first kind, we know $s$ is connected to the product $p=2^mp_1$ . This product has only one valid factorization with an odd and an even number, so $p$ determines $s$ ! If we cannot find such a partition, we look for the second kind, as a product of the form $p=2^mp_1p_2$ has at most three valid factorizations with an odd and an even number and is unlikely to be connected to another sum.

  We find all $s\in S_3$ have (at least) one valid partition of the first kind. All $s\in S_3$ except the ones in the following list even have two of them! To find them, check if $s-2^m$ is prime, starting with $m=1$ and increase $m$ until you get to negative values.

  We now list the exceptions with their partitions of first and second kind, if possible: $\begin{array}{r | r | r | r | r } s & 17 & 29 & 41 & 53 \\\hline 2^m +p_1& 4+13& 16+13& 4+37& 16+37\\ 2^m+p_1p_2& & 4+25& 16+25& 32+21 \end{array}$

• Condition (5):

  After the last step, all $s\in S_3\setminus\{17\}$ can be determined by more than one $p\in P_3$ : They cannot satisfy (5)! To show that 17 does, we must verify it is determined by only one of the products it is connected to. We list all valid partitions of 17 and give an example of an alternative sum $s'\in S_3$ the product is connected to: $\begin{array}{r | r | r | r | r | r | r | r} s=17 & 2+15 & 3+14 & 4+13 & 5+12 & 6+11 & 7+10 & 8+9\\\hline s'\in S_3& 5+6 & 2+21 & & 3+20 & 2+33 & 2+35 & 3+24 \end{array}$

  We note: $s=17$ is determined by exactly one product $p=4\cdot 13=52$ , and it is the only solution: $\begin{aligned} s&=17,&p&=52=4\cdot 13=ab&\Rightarrow&&(a,\:b)=(4;\:\boxed{13}) \end{aligned}$

Here is a python code from Wikipedia -

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

 limit = 100
   #before they talk any x*y where 1<x<y<x+y<limit is allowed as P
   PAllowed1 = {} 
   for x in range(2, limit): 
       for y in range(x+1, limit-x): 
           if x*y not in PAllowed1: 
               PAllowed1[x*y] = 1 
           else:
               PAllowed1[x*y] += 1
   # when P says I don't know, only P's with PAllowed1[P]>1 are allowed 
   SNotAllowed1 = {}  
   for x in range(2, limit): 
       for y in range(x+1, limit-x): 
           if  PAllowed1[x*y] == 1 :
               SNotAllowed1[x+y] = 1  
   # when S says I don't know, only S's that are not in the domain of SNotAllowed1 are allowed 
   PAllowed2 = {} 
   for n in range(2, limit):
     if n not in SNotAllowed1:
       for x in range(2, n//2+1):
           p = x * (n-x)
           if p in PAllowed1 and PAllowed1[p] > 1:
               if p in PAllowed2:
                   PAllowed2[p] += 1
               else:
                   PAllowed2[p] = 1 
   # only the P's that can by split to two x,y where x+y is allowed in only 1 way are allowed, i.e., PAllowed2[P]==1      
   SAllowed2 = {}  
   for n in range(2, limit):
     if n not in SNotAllowed1:
       for x in range(2, n//2+1):
           if x*(n-x) in PAllowed2 and PAllowed2[x*(n-x)] == 1:
               if n in SAllowed2:
                   SAllowed2[n] += 1
               else:
                   SAllowed2[n] = 1
   # since S knows the answer now the split can only be done in one way, so only S where SAllowed2[S]==1
   for n in SAllowed2: 
       if SAllowed2[n] == 1:
           for x in range(2, n//2+1):
               if x*(n-x) in PAllowed2 and PAllowed2[x*(n-x)] == 1:
                  print '(S,P) = ( %d , %d ), (x,y)= ( %d , %d )' % (n, x*(n-x), x, n-x)