Shared publicly  - 
 
I choose two different whole numbers, both greater than 1, whose sum is less than 100. I whisper their sum to Sam and their product to Paula. They then have the following conversation:

Paula: I don’t know the numbers.
Sam: I knew you didn’t. I don’t either.
Paula: Ah, now I know them.
Sam: Now I know them too.

Which two numbers had I chosen?

Note: assume Paula and Sam were told all the relevant information above; when their conversation begins the only thing they don't know (besides the numbers themselves) is exactly which number was whispered to the other. And, of course, assume they are actually correct about the above. :-)

~~~~~

This "simple" little puzzle, concocted by Hans Freudenthal in the 1960s, is now commonly (and appropriately) known by the name The Impossible Problem. In fact, you can Google that very phrase to learn more, but be careful: spoilers abound.

Amazingly, it really is solvable!
7
3
Manuel Klimek's profile photoGuga Moura's profile photoAnthony Zana's profile photoKevin Bourrillion's profile photo
17 comments
 
(As for me, I got as far as finding two numbers that work, which really broke my head, but I didn't go on to verify that there really was no other solution, instead just taking the problem's word for it that the solution is unique.)
 
I have the opposite problem  I think I see the solution, but my brain is too tired to devise a non-iterative algorithm or perform the iteration. 
 
Kevin: I think you are missing one crucial piece of the problem (which if I remember correctly required the constraint that the Sum be less than 100) Otherwise I'm not sure if my patience to test all the combinations will last :)
 
Presumably Paula and Sam know what the other has been told? I.e. not the numbers themselves, but that one knows the product and the other knows the sum...
 
This makes no sense and these kinds of problems makes my head asplode.
 
Are the two numbers guaranteed to be different?
 
+Gustavo Moura Oops. Yes, it's stated that they're different. I should be more careful when restating problems like this.
 
Wow, you really got me caught up for many hours there. I built a little python program to brute force it, but got stuck multiple times when I didn't realize how to introduce the next step into the solution.
Now I don't know whether I want to Google it and verify my (seemingly unique) solution or waste some more time making sure that my solution is actually correct. Aaaaargh.
 
+Manuel Klimek I can confirm that deciding how to recognize what a correct solution looks like was the hard part, after which it wasn't too hard to find it without need of a program.
 
+Kevin Bourrillion - really? you must be better at math than I am :) Even knowing the correct solution (I googled my numbers and found the problem :) I have no idea how I would verify this without a program.
 
+Kevin Bourrillion - still waiting for an explanation :) How did you find it without a program? Even the first step of getting all sums that have at least one partition whose product has only one possible factorization within the rules seems hard to get to manually. Did you find some mathematical approach?
 
+Manuel Klimek Well, here's how I started. With Sam's first statement Paula knows that all number pairs with this sum (S) yield a product (P) with at least 3 prime factors. So S can't be expressible as the sum of two primes. Ergo S can't be even (Goldbach), so it has to be 2 greater than an odd composite (11, 17, 23, 27, 29, 35, 37, 41...), and the two numbers must be an even and an odd. 
 
Thanks to citing Goldback I can follow you until the step where you exclude even numbers. I don't understand the next logical step (the last one is clear again). Where do you get "2 greater than an odd composite" from? (thanks for explaining btw, this is fun :)
 
+Manuel Klimek Because (a) it has to be odd, and (b) it can't be 2 greater than a prime, or it would again be the sum of two primes! Yes, it is fun.
 
/me facepalms. Of course. Heh, ok, I give up. 20 lines of python FTW, no thinking necessary :P
Add a comment...