Last evening, I stumbled upon this interesting puzzle: http://en.wikipedia.org/wiki/Impossible_Puzzle.
Let me quote the problem statement from the Wikipedia article.

*Given are X and Y, two integers, greater than 1, are not
equal, and their sum is less than 100. S and P are two mathematicians; S
is given the sum X + Y, and P is given the product X × Y of these
numbers.
*- P says "I cannot find these numbers."
- S says "I was sure
that you could not find them."
- P says "Then, I found these
numbers."
- S says "If you could find them, then I also found
them."

What are these numbers?

I'll explain how I solved it. Without loss of generality, we can assume
X to be smaller than Y. X can not be greater than 49, otherwise the sum
X + Y wouldn't be less than 100. For example, if X is 50, the sum is 101
even for the smallest possible value of Y, i.e. Y = 51. Since, the sum
of X and Y is less than 100 and X can take a minimum value of 2, Y can
not be greater than 97. The smallest sum possible is 5 for X = 2 and Y =
3.

Let me explain these things once again, algebraically.

X < Y and X + Y < 100
⇒ X + 1 ≤ Y and X + Y ≤ 99
⇒ 2X + 1 ≤ X + Y ≤ 99
⇒ X ≤ 49

X > 1 and X + Y < 100
&rArr 2 ≤ X and X + Y ≤ 99
⇒ 2 + Y ≤ X + Y ≤ 99
⇒ Y ≤ 97.

Y > X and X > 1
⇒ Y ≥ X + 1 and X ≥ 2
⇒ Y ≥ 3

Y > X > 1
⇒ Y ≥ X + 1 and X ≥ 2
⇒ X + Y ≥ 2X + 1 ≥ 2 ⋅ 2 + 1 = 5

The above constraints automatically place some constraints on the
product XY.

X > 1 and Y > X
⇒ X ≥ 2 and Y ≥ X + 1
⇒ XY ≥ X(X + 1) ≥ 6

X + Y < 100
⇒ X + Y ≤ 99
⇒ Y ≤ 99 − X
⇒ XY ≤ X(99 − X)

^{d}⁄_{dX} X(99 − X)
= ^{d}⁄_{dX} 99X − X^{2}
= 99 − 2X

This value is positive for all real numbers X in the closed interval [2,
49]. So, X(99 − X) is monotonically increasing in this interval.
Therefore, the largest possible value of X(99 − X) is 49(99
− 49) = 2450.

Hence, XY ≤ 2450

Let me write down all the constraints we have found so far neatly.

- 2 ≤ X ≤ 49
- 3 ≤ Y ≤ 97
- 5 ≤ X + Y
≤ 99
- 6 ≤ XY ≤ 2450

Now, let us analyze what
the two mathematicians said.

P says "I cannot find these numbers."

If X and Y are two prime numbers, P can easily factor the product to
find the numbers X and Y. For example, if XY = 35, he can easily
determine that the two numbers are 5 and 7. The only other way of
factoring it is 1 × 35 but X = 1 is not allowed in this puzzle.

If XY is a cube of a prime number, he can find the two numbers as X =
∛(XY) and Y = [∛(XY)]^{2}. For example, if XY = 125,
he can say that the two numbers are 5 and 25.

If XY is a fourth power of a prime number, he can find the two numbers
as X = ∜(XY) and [∜(XY)]^{3}. For example, if XY =
81, he can say that the two numbers are 3 and 27. Factoring it as 9
× 9 is not useful because X = Y is not allowed in this puzzle.

It is not possible to find X and Y for any other type of product. For
example, if P is given 12, there is no way for him to know whether the
numbers are X = 2 and Y = 6, or X = 3 and Y = 4.

If you are not convinced with this demonstration, please wait for my
next blog post in which I will prove:

For any positive integer N, there exists only one pair of
positive integers a and b such that 1 < a < b and ab = N if and
only if N is a product of two different primes, a cube of a prime, or a
fourth power of a prime.

*Update: The blog post is now available: Factoring
step in Impossible Puzzle*
So, the information we get from the first sentence uttered by P is that
the product given to him is definitely neither a product of two primes
nor a cube of a prime nor a fourth power of a prime.

S says "I was sure that you could not find
them."

S can be sure that P wouldn't find them only if he has got a number that
can not be expressed as a sum of two primes or as a sum of a prime and
its square or a sum of a prime and its cube. So, if S is given 11, he
would be sure that P can not find X and Y. I wrote a Python program to
find all such sums.

Here is the output from the program: possible-sums.py

11 17 23 27 29 35 37 41 47 51 53 57 59 65 67 71 77 79 83 87 89 93
95 97

P says "Then, I found these numbers."
P realizes that if S was sure of what he said, then the sum S has got
can not be expressed as a sum of two primes, sum of a prime and its
square, or sum of a prime and its cube. From the output of the program
above, we saw that there are 24 such possible sums.

Now, P must have factored the product with him into two factors and
compared their sum with the numbers in this list of possible sums. He
must have found exactly one way of factoring (ignoring the ones that
involve 1 or equal factors) possible such that the sum of the factors
belonged to the list. Hence, he could decide that the pair of factors
from the only possible factoring were X and Y.

Let us take 24 as an example. 24 can be factored as 2 × 12, 3
× 8 and 4 × 6. However, 3 and 8 is the only pair of factors
which has a sum that belongs to the list of possible sums with S. So, if
P is given 24, he can determine that X = 3 and Y = 8.

However, if P is given 30, he would find that it can be factored in two
different ways such that their sum is a possible sum that S might have.
For example, if 30 is factored into 2 and 15, the sum of the factors is
17 which is a possible sum S might have. If it factored into 5 and 6,
their sum is 11 which again is a possible sum S might have. So, in such
a case, P can't determine whether X = 2 and Y = 15, or X = 5 and Y = 6.

So, P definitely has a product which can be factored into X and Y in
only one way such that X + Y is a possible sum that S might have. I
wrote another Python program to find all such products.

Here are the first 10 lines of output from the program: possible-products.py

If P has 18: X = 2, Y = 9, S has 11
If P has 24: X = 3, Y = 8, S has 11
If P has 28: X = 4, Y = 7, S has 11
If P has 50: X = 2, Y = 25, S has 27
If P has 52: X = 4, Y = 13, S has 17
If P has 54: X = 2, Y = 27, S has 29
If P has 76: X = 4, Y = 19, S has 23
If P has 92: X = 4, Y = 23, S has 27
If P has 96: X = 3, Y = 32, S has 35
If P has 98: X = 2, Y = 49, S has 51

S says "If you could find them, then I also found
them."
From the above output, we can see that there are certain sums that S
might have for which there are multiple possible products that might be
with P. For example, if S has 11, P might have 18, 24, etc. In such a
case S can not conclude on a particular product P has, and the values of
X and Y.

But since S said that he could also find X and Y, S certainly has a sum
for which there is exactly one possible product that P might have. The
program finds such sums and prints it in the end. Here are the last 10
lines of output.

If P has 2296: X = 41, Y = 56, S has 97
If P has 2310: X = 42, Y = 55, S has 97
If P has 2322: X = 43, Y = 54, S has 97
If P has 2332: X = 44, Y = 53, S has 97
If P has 2340: X = 45, Y = 52, S has 97
If P has 2346: X = 46, Y = 51, S has 97
If P has 2350: X = 47, Y = 50, S has 97
If P has 2352: X = 48, Y = 49, S has 97
X = 4 and Y = 13 has a unique sum.