# The Impossible puzzle ("Now I know your product")

I am trying to figure out this impossible problem by Martin Gardener and still havent found a suitable solution or link to it

Two mathematicians S and P are discussing two unknown integers, both greater than 1. S knows only the sum of the numbers, whereas P knows only their product.:

S: "I see no way you can determine my sum." P (after a suitable delay): "That didn't help me. I still don't know your sum." S (after another delay): "Now I know your product." What are the two numbers?

I have seen the answers on the xkcd wiki link for this at http://wiki.xkcd.com/irc/Talk:Puzzles#The_Sam_And_Polly_Problem say 13 and 16 and it checks out mathematically but then there are more ambiguous responses and most of the attempts seem brute force rather than logic.

My question is two fold

1. How to solve this problem logically?

2. Are there more answers then 13,16 or this answer is the only one even as the upper bound k(upper bound on answer) shifts higher

Let $x,y$ be integers greater than $1$, $P=xy$ and $S=x+y$.
Write $P=x_1\cdots x_n$, product of not necessarily distinct primes. If $n=2$, then necessarily $S=x_1+x_2$, so, if $S$ isn't the sum of two primes (this case), knowing $P$ tells nothing about $S$.
Then, we know that $n\ge 3$ and $S$ isn't the sum of two primes ($S$ isn't even, in particular, and then necessarily $P$ is even.).

So, necessarily $x$ is even and $y$ is odd. If we write $P=2^k p_1$, where $p_1$ is any prime, then necessarily $x=2^k$ and $y=p_1$, so, in this case $S$ would be known. Then, in this case, $P=2^k p_1\cdots p_m$, with $m>1$ and $p_i$ prime (since in this case knowing $P$ tells nothing about $S$).

So $S$ is odd and the set $\{xy:x+y=S,x,y>1\}$ contains one and only one number of the form $P=2^kp_1\cdots p_m$, with $p_i$ prime and $m>1$.

.......................................................................................

Sam (to Polly): "You can't know what x and y are."
Polly (to Sam): "That was true, but now I do."
Sam (to Polly): "Now I do too."

So, in this case we have $S$ odd, isn't the sum of two primes, and the set $\{xy:x+y=S,x,y>1\}$ contains one and only one number of the form $2^kp$, with $p$ odd prime, $k>1$, and $P=2^kp$, $x=2^k$, $y=p$. This excludes several possibilities and the rest is brute force (and we need an upper bound for $x$ and $y$).

• Why can't $S$ be a sum of two primes? Either way, aren't you assuming Goldbach's conjecture? Jul 1, 2012 at 15:04
• He means $P$ is not the product of two primes. Jul 1, 2012 at 15:20
• @tomasz: oopss... I assumed Goldbach's conjecture... (but if we have an upper bound for $x$ and $y$, then it's proved =p (by brute force... =p)). And if $S$ was the sum of two primes, then Polly would know $S$, which doesn't happen.
– Yuki
Jul 1, 2012 at 15:38
• @Yuki: it could be the sum of two primes whose product isn't $P$. Jul 1, 2012 at 15:47
• @tomasz: but if $S$ is the sum of two primes, then Sam would say "Maybe you know what $x$ and $y$ are", since in this case one of the possibilities is $P$ be the product of two primes, and if $P=p_1p_2$, $p_1,p_2$ primes, then necessarily $x=p_1$ and $y=p_2$, cause $x,y>1$.
– Yuki
Jul 1, 2012 at 21:25

Formally one can define: \begin{align} &A_x=\{(a,b) \in\mathbb{N}^2 : a+b=x,\,\,1<a\le b\} \\ &B_x=\{(a,b) \in\mathbb{N}^2 : ab=x,\,\,1<a\le b\} \\ &C_x=\{ab : (a,b)\in A_x\} \\ &D_x=\{a+b : (a,b)\in B_x\} \\ &R=\{p,\,pq,\,p^3 \,:\, p,q\,\text{ are prime}. \} \\ &T=\{x : C_x \cap R=\emptyset\} \end{align} Then the problem becomes finding the unique value $S\in\{4,...,100\}$, such that the following statement holds: $$S\in T\,\text{ and }\,\exists!P\in C_S\,:|D_P \cap T|=1$$ Then $S$ is our sum, and the unique value $P$ in the above statement is our product. With some effort we can find these values, by simple brute force search.

We look for an appropriate $S$. The smallest value in $\{4,...,100\}$ that is in $T$ is $11$. This can be seen as follows: $$2\cdot 2\in R \text{ and } 2\cdot 2\in C_{4} \text{, Therefore } 4\notin T \\ 3\cdot 2\in R \text{ and } 3\cdot 2\in C_{5} \text{, Therefore } 5\notin T \\ 3\cdot 3\in R \text{ and } 3\cdot 3\in C_{6} \text{, Therefore } 6\notin T \\ 5\cdot 2\in R \text{ and } 5\cdot 2\in C_{7} \text{, Therefore } 7\notin T \\ 5\cdot 3\in R \text{ and } 5\cdot 3\in C_{8} \text{, Therefore } 8\notin T \\ 7\cdot 2\in R \text{ and } 7\cdot 2\in C_{9} \text{, Therefore } 9\notin T \\ 7\cdot 3\in R \text{ and } 7\cdot 3\in C_{10} \text{, Therefore } 10\notin T$$ While: $$A_{11} = \{(2,9), (3,8), (4,7), (5,6)\} \text{, and so }\,\,C_{11} = \{18, 24, 28, 30\}$$ We proceed to check if there if there exists a unique $P\in C_{11}$, for which $|D_P \cap T|=1$. Looking at $D_{18}=\{9,11\}$, and $D_{24}=\{10,11,13\}$, and noting that $11\cdot 2\in R$ and $11\cdot 2\in C_{13}$, Therefore $13\notin T$, we see: $$|D_{18}\cap T| = |\{11\}| = 1\,\text{ and }\,|D_{24}\cap T| = |\{11\}| = 1$$ So we have more than one value that satisfies the statement. However we required that the value be unique, so we must conclude that $S\neq 11$. The next value in $T$ after $11$ is $17$. This can as can be seen as follows: $$7\cdot 5\in R \text{ and } 7\cdot 5\in C_{12} \text{, Therefore } 12\notin T \\ 7\cdot 7\in R \text{ and } 7\cdot 7\in C_{14} \text{, Therefore } 14\notin T \\ 13\cdot 2\in R \text{ and } 13\cdot 2\in C_{15} \text{, Therefore } 15\notin T \\ 13\cdot 3\in R \text{ and } 13\cdot 3\in C_{16} \text{, Therefore } 16\notin T$$ While: $$A_{17} = \{(2,15),(3,14),(4,13),(5,12),(6,11),(7,10),(8,9)\},\,C_{17} = \{30, 42, 52, 60, 66, 70, 72\}$$ As before, we proceed to check if there if there exists a unique $P\in C_{17}$, for which $|D_P \cap T|=1$. Let us first write out the sets $D_i$ for all $i\in C_{17}$: \begin{align} &D_{30} = \{11, 13, 17 \} \\ &D_{42} = \{13, 17, 23 \} \\ &D_{52} = \{17, 28 \} \\ &D_{60} = \{16, 17, 19, 23, 32 \} \\ &D_{66} = \{17, 25, 35 \} \\ &D_{70} = \{17, 19, 37 \} \\ &D_{72} = \{17, 18, 22, 27, 38 \} \\ \end{align} Next, we note the following: A quick way to check if an odd number $k$ can be written as the sum of two primes is to check if $k-2$ is prime. This is because the primes in the sum must have different parity, and the only even prime is $2$. By definition, if $k$ cannot be written as $(1)$ the sum of two primes, nor as $(2)$ $p^2 + p$ for some prime $p$, then $k\in T$. The first few values for $p^2 + p$ are: $$\begin{array}{c|c} p & p^2+p \\ \hline 2 & 6 \\ 3 & 12 \\ 5 & 30 \\ 7 & 56 \\ \end{array}$$ Using the data in this table along with our observation regarding the way odd itegers must be written as the sum of primes, we conclude that $23, 27, 35, 37 \in T$, and therefore: $$|D_i \cap T| > 1$$ for $i \in \{30,42,60,66,70,72\}$. Finally, we see that $23\cdot 5\in R$ and $23\cdot 5\in C_{28}$, Therefore $28\notin T$, so that: $$|D_{52}\cap T| = |\{17\}| = 1$$ Therefore our unique product is $P = 52$, and the answer to the puzzle is $4$ and $13$.