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.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.
What are 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."
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 − X2 = 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
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 97P 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 51S 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.