# 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

-
You forgot the hypothesis: $3 \leq x \leq y \leq 97$. –  Sigur Jul 1 '12 at 13:48
See people.sc.fsu.edu/~jburkardt/fun/puzzles/impossible_puzzle.html (and the link to solutions at the bottom of the page). –  Hans Lundmark Jul 2 '12 at 6:46

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? –  tomasz Jul 1 '12 at 15:04
He means $P$ is not the product of two primes. –  N. S. Jul 1 '12 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 '12 at 15:38
@Yuki: it could be the sum of two primes whose product isn't $P$. –  tomasz Jul 1 '12 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 '12 at 21:25
show 1 more comment

$\color{green}{(1)}$ If the sum $S$ can be written as the sum of two primes $p$ and $q$, then as far as Sam knows the product can be $pq$, and thus Polly could deduce the numbers $x$ and $y$, since $x=p$ and $y=q$ is the only possible factorization. However, Sam said: "You can't know what $x$ and $y$ are". This implies that the $S$ cannot be written as the sum of two primes.

So the first thing we do is look for an integer that cannot be written as the sum of two primes. The numbers $4,\dots,10$ can all be written as the sum of two primes: $$4=2+2 \\ 5=3+2 \\ 6=3+3 \\ 7=5+2 \\ 8=5+3 \\ 9=7+2 \\ 10=7+3 \\$$ However $11$ cannot: $$11=2+9 \\ 11=3+8 \\ 11=4+7 \\ 11=5+6 \\$$ So we try-out $S=11$. In this case the product $P$ is either $18$, $24$, $28$ or $30$.

$\color{green}{(2)}$ If $P = 18$, then Polly knows that $S$ is either $2+9=11$, or $3+6=9$. We have seen that $9$ can be written as the sum of two primes. Thus, when Sam says that Polly cannot know what $x$ and $y$ are, Polly considers $\color{green}{(1)}$, and concludes that the sum must be $11$. Polly then goes on Saying "That was true, but now I do".

$\color{green}{(3)}$ If $P = 24$, then Polly knows that $S$ is either $2+12=13$, $\,3+8=11$, or $4+6=10$. We have already seen that $10$ can be written as the sum of two primes, and so can $13 = 11+2$. Thus, when Sam says that Polly cannot know what $x$ and $y$ are, Polly considers $\color{green}{(1)}$, and concludes that the sum must be $11$. Polly then goes on Saying "That was true, but now I do".

By Considering both $\color{green}{(2)}$ and $\color{green}{(3)}$, after hearing Polly saying that she knows the numbers, Sam cannot conclude what they are, since they may be $3$ and $8$ (by case $\color{green}{(3)}$) or $2$ and $9$ (by case $\color{green}{(2)}$). However, we know that Sam goes on saying he also knows the numbers. Thus we must conclude that $S\neq11$. We continue as we did before, looking for an integer that cannot be written as the sum of two primes. We note that $12,\dots,16$ can all be written as the sum of two primes: $$12=7+5 \\ 13=11+2 \\ 14=11+3 \\ 15=13+2 \\ 16=13+3 \\$$ However $17$ cannot: $$17=2+15 \\ 17=3+14 \\ 17=4+13 \\ 17=5+12 \\ 17=6+11 \\ 17=7+10 \\ 17=8+9 \\$$

So we try-out $S=17$. In this case the product $P$ is either $30$, $42$, $52$, $60$, $66$, $70$ or $72$.

$\color{green}{(4)}$ If $P = 30$, then Polly knows that $S$ is either $2+15=17$, $\,3+10=13$, or $5+6=11$. We have already seen that $13$ can be written as the sum of two primes. Thus, when Sam says that Polly cannot know what $x$ and $y$ are, Polly considers $\color{green}{(1)}$, and concludes that the sum cannot be $13$. However Polly still remains with two possibilities ($17$ and $11$), and cannot conclude what the numbers $x$ and $y$ are. Thus we must conclude that $P\neq30$.

$\color{green}{(5)}$ If $P = 42$, then Polly knows that $S$ is either $2+21=23$, $\,3+14=17$, or $7+6=13$. We have already seen that $13$ can be written as the sum of two primes. However, $23$ cannot. We can see this by considering the fact that when writing $23$ as the sum of two integers they must have different parity. Thus one of them must be even. The only even prime is $2$, but writing $23=2+21$ is no good, since $21$ is not prime. Thus, when Sam says that Polly cannot know what $x$ and $y$ are, Polly considers $\color{green}{(1)}$, and concludes that the sum cannot be $13$. However Polly still remains with two possibilities ($23$ and $17$), and cannot conclude what the numbers $x$ and $y$ are. Thus we must conclude that $P\neq42$.

$\color{green}{(6)}$ If $P = 52$, then Polly knows that $S$ is either $2+26=28$, or $4+13=17$. We see that $28=23+5$ can be written as the sum of two primes. Thus, when Sam says that Polly cannot know what $x$ and $y$ are, Polly considers $\color{green}{(1)}$, and concludes that the sum must be $17$. Polly then goes on Saying "That was true, but now I do".

$\color{green}{(7)}$ If $P = 60$, then Polly knows that $S$ is either $2+30=32$, $3+20=23$, $4+15=19$, $5+12=17$, or $6+10=16$. We have already seen that both $17$ and $23$ cannot be written as the sum of two primes. Thus, when Sam says that Polly cannot know what $x$ and $y$ are, Polly cannot conclude what the numbers $x$ and $y$ are. Thus we must conclude that $P\neq60$.

$\color{green}{(8)}$ If $P = 66$, then Polly knows that $S$ is either $2+33=35$, $3+22=25$, or $6+11=17$. Applying the same reasoning we used in showing $23$ cannot be written as the sum of primes, we can show that $35$ cannot be written as the sum of two primes. Thus, when Sam says that Polly cannot know what $x$ and $y$ are, Polly cannot conclude what the numbers $x$ and $y$ are. Thus we must conclude that $P\neq66$.

$\color{green}{(9)}$ If $P = 70$, then Polly knows that $S$ is either $2+35=37$, $5+14=19$, or $7+10=17$. Applying the same reasoning we used in showing $23$ cannot be written as the sum of primes, we can show that $37$ cannot be written as the sum of two primes. Thus, when Sam says that Polly cannot know what $x$ and $y$ are, Polly cannot conclude what the numbers $x$ and $y$ are. Thus we must conclude that $P\neq70$.

$\color{green}{(10)}$ If $P = 72$, then Polly knows that $S$ is either $2+36=38$, $3+24=27$, $4+18=22$, $6+12=18$, or $8+9=17$. Applying the same reasoning we used in showing $23$ cannot be written as the sum of primes, we can show that $27$ cannot be written as the sum of two primes. Thus, when Sam says that Polly cannot know what $x$ and $y$ are, Polly cannot conclude what the numbers $x$ and $y$ are. Thus we must conclude that $P\neq72$.

By considering $\color{green}{(4)} - \color{green}{(10)}$, When Sam hears Polly saying she knows what $x$ and $y$ are, Sam must conclude that option $\color{green}{(6)}$ is the correct one i.e. $x = 4$ and $y = 13$. Sam goes on saying "Now I do too."

-