Solving the Impossible Problem: A Mathematical Challenge

[gravenewworld]

The Impossible Problem!

I thought this might be a little fun, my professor gave us this problem for extra credit a while back, and he published it in some math journal with the title "The impossible problem." Can any of you guys solve it?

Let x and y be two numbers with 1 < x < y and x+y <= 100.
Suppose S is given the value x+y and P is given the value x*y.

<<1>> Mr. P.: I do not know the two numbers.
<<2>> Mr. S.: I knew that you didn't know the two numbers.
<<3>> Mr. P.: Now I know the two numbers.
<<4>> Mr. S.: Now I know the two numbers.

What are the two numbers?

PS...Don't be cheap and look up the answers online

 

[rayjohn01]

I assume , but you did not say that the numbers are integers.

 

[MathematicalPhysicist]

I thought this might be a little fun, my professor gave us this problem for extra credit a while back, and he published it in some math journal with the title "The impossible problem." Can any of you guys solve it?

Let x and y be two numbers with 1 < x < y and x+y <= 100.
Suppose S is given the value x+y and P is given the value x*y.

<<1>> Mr. P.: I do not know the two numbers.
<<2>> Mr. S.: I knew that you didn't know the two numbers.
<<3>> Mr. P.: Now I know the two numbers.
<<4>> Mr. S.: Now I know the two numbers.

What are the two numbers?

PS...Don't be cheap and look up the answers online

do they both know each other value?

 

[cookiemonster]

<<2>> should reveal P's number to S.

cookiemonster

 

[MathematicalPhysicist]

<<2>> should reveal P's number to S.

cookiemonster

not the other way around?
it reveals S's number to P.

 

[cookiemonster]

Er... Yeah.

cookiemonster

 

[zefram_c]

I think I have a solution, shall I post it?

 

[cookiemonster]

I think I might, as well. I'm getting 4 and 13.

cookiemonster

 

[Zurtex]

I think I might, as well. I'm getting 4 and 13.

cookiemonster

That's the correct answer, I run a puzzles and riddles forum and this problem came up recently. Was great fun trying to solve.

I've seen the problem around, the limits change quite a bit (e.g the number is less than 50 or 100 or 7000). From what work I've done I know the top limit must be 80 or greater, I don't think there is any other stable solution so I think you can go as high as you want.

 

[cookiemonster]

Guess I'll write up a quick, but not exactly complete, solution, then.

For starters, P does not know the solution straight off, therefore there are multiple factors of P. This implies that both x and y are not prime and that P is not the product of two primes.

Taking the fact that x and y are not prime further, we see that S is not the sum of two primes. This eliminates all even values for S.

We can impose another restriction on x and y by noting something about P, i.e. that P cannot be written as 2p, p prime. If such were the case, there would be two factorizations, {1,2p} and {2,p}, but since 1<x<y, the first factorization is not valid and P can then determine both x and y. This means that if x = 2, y != p.

Using this restriction, exclude all values of S that are 2 more than a prime.

The set of possible values of S is now limited to: 11,17,23,27,29,35,37,41,47,51,53,57,59,65,67,71,77,79,83,87,89,93,95,97,
i.e. that if S is one of the above numbers, P may not be able to determine x and y and statement <<2>> might be satisfied.

Let F = {f,g} be a factor pair of P and the set of all possible values of F the factorizations of P. One and only one F in this set must have a sum that is in the set of possible values of S. This condition is necessary to ensure that <<3>> is true, i.e. that once S reveals <<2>>, P can eliminate all possibilities but the correct answer. An easy way to force this is to let x = 4 and y = p. We then have F1={2,2p} and F2={4,p}. The sum of F1's elements is necessarily even and therefore not in S. The sum of F2's elements is necessarily odd and can be in S for a properly chosen p.

Start testing p's, starting from the lowest possible. p = 7 -> P = 28, F1 = {2,14}, F2 = {4,7}. Possible x,y doubles that can be guessed from S are {2,9}, {3,8}, {4,7}, {5,6} with corresponding products 18, 24, 28, and 30. Check to ensure that 28 is the only one in which <<2>> implies <<3>>.

P = 18, F1 = {2,9}, F2 = {3,6} with F1's sum being 11 and F2's being 9. We note that only F1's sum is in the set of S, which implies that <<1>> is false and in turn that <<2>> is false. Therefore p != 7.

Repeat with 11 to determine that p != 11, and finally repeat with 14 and note that it is in fact true.

Note that this solution does not prove that 4,13 is the only solution and does not give complete insight into the problem. I went off and did other things once I found 4,13, so if anybody wants to complete it, they're welcome to.

cookiemonster

 

[Zurtex]

The problem I got was:

There are 2 integers greater than 1 and less than 80. They may or may not be equal. S knows the sum of the two numbers, and P knows their product.

S says, "I don't know what the two numbers are and it's impossible for you to know”

P says, "In that case I know what they are."

S then says, "In that case, so do I."

What are the 2 numbers?

Here is my solution if it gives a little more insight:


1. S does not know what x and y are (the two numbers), this means these statements can not be true:

x + y = 4
x + y = 5
x + y = 157
x + y = 158

2. S knows P does not know the two numbers, this means that whatever number S has it can not expressed as the sum of two numbers which P would then be able to deduce with the given information. So here are the circumstances where P would know the numbers from the given information:

a ) Either x or y is a prime greater than half the upper bound of the numbers (thought I'd spotted a mistake here but it's actually fine so carrying on). So it restricts the lowest sum which is (41 + 2) 43 to the highest sum (79 + 79) 158. Now it is possible to just look at combinations where the sum is less than 43 and greater than 5.

b ) If x and y are both prime numbers

c ) If x is a prime and y is its square, or if y is a prime and x is its square

3. Going through all the numbers one at a time you find that, 11, 17, 23, 27, 29, 35, and 37 are the numbers which S could know satisfy the above condition.

4. Given these numbers we can then work out all possible products, e.g: 17 = 5 + 12, product: 5*12 = 60. So here are all of them:

For 11:

18
24
28
30

For 17:

30
42
52
60
66
70
72

For 23:

42
60
76
90
102
112
120
126
130
132

For 27:

50
72
92
110
126
140
152
162
170
176
180
182

For 29:

54
78
100
120
138
154
168
180
190
198
204
208
210

For 35:

66
96
124
150
174
196
216
234
250
264
276
286
294
300
304
306

For 37:

70
102
132
160
186
210
232
252
270
286
300
312
322
330
336
340
342

5. P is able to work out what the two numbers are, given P has one of these numbers and knows the sum is one of: 11, 17, 23, 27, 29, 35, and 37 then P can work out given any of the products assuming they do not appear twice. So highlighted in bold are all numbers that appear more than once.

6. Finally we are given the piece of information that S is able to conclude what the two numbers are if P knows two numbers are. We know the numbers make one of the products above and is non bold, as there is only one left over solution for where the sum is 17 then we know that:

x + y = 17
xy = 52

x or y = 4
y or x = 13



If anyone needs me to explain anything further I'm happy to.

 

[Njorl]

I read about this problem in Scientific American sometime in the early eighties. Computers were used to verify 4 and 13 as the only solutions below 1 billion. Given the increase in speed, it should probably not be difficult to find any solutions for several more orders of magnitude. I wonder if anyone has done it.

Njorl

 

[zefram_c]

Here's a short expansion on cookiemonster's approach:
We have found that the set of possible sums is 11,17,23,27,29,35,37,41,47,51,53,57,59,65,67,71,77 ,79,83,87,89,93,95,97 so far. But we can rule out half of these. Suppose that P=610=61*5*2. P knows that he has to group the factors into two such that their sum is under 100. He can only do that if he chooses 61 and 10. Their sum is 71. Hence if the sum was 71, it would be possible for P to resolve the numbers without any other information if his number happens to be 610. Hence we rule out 71 as a possible sum for which S can assert <<2>> We can similarly rule out all sums greater than 53, so we need consider only 11,17,23,27,29,35,37,41,47,51,53 . From here on, I programmed the computer to find the pairs as indicated; only 4 and 13 allow both <<3>> and <<4>>

 

[e(ho0n3]

Confused?

Can someone explain to me what the relevance of the conversation between P and S is? I don't understand this at all. What does it mean for either S or P to "know" the two numbers?

 

[Gokul43201]

"Don't know" implies multiple integer solutions for the repective equations : xy = P and x+y=S.

 

[cookiemonster]

S is given the number x+y. P is given the number xy.

P now wants to know all the possible values of x and y as far as he can tell. He knows that the two values x and y must multiply to yield xy, so he looks at the factors of xy. Each factor pair (excluding (1)(xy)) yields a possible x,y double, so all the factor pairs of xy are the possible values of x and y as far as P can tell.

S wants to know all the possible values of x and y as far as he can tell. He knows that the two values x and y must add to yield x+y, so he makes the equation x + y = S and solves for one of them, e.g. y = S - x. Now he starts putting in values of x to get a corresponding value for y. This is how he generates his x,y doubles.

When S says that he knew that P cannot pin down the two numbers, he's giving away information about what S is. Note that for every double P generates, he can then work up with these doubles to figure out what S would be in such a case, and S can work up from his doubles to figure out what P would be. S can only say that he knew P doesn't know what the two numbers are for only certain values of x+y. Note that some conditions necessary for these values are given in each solution.

When S says <<2>>, P looks at his possible doubles and figures out for which one can S actually say that. There must be only one possibility in order for <<3>> to be true, so this further limits x and y. And when P says <<3>>, he is saying that saw only one possible factor in which S could say that, not two or three or more, so S can look at his possibilities and see which ones allow P to say that and thereby eliminate possibilities.

cookiemonster

 

[e(ho0n3]

When S says <<2>>, P looks at his possible doubles and figures out for which one can S actually say that. There must be only one possibility in order for <<3>> to be true, so this further limits x and y. And when P says <<3>>, he is saying that saw only one possible factor in which S could say that, not two or three or more, so S can look at his possibilities and see which ones allow P to say that and thereby eliminate possibilities.

I'm still confused? So can S look at P's possibilities and vice versa? Let A = {(x,y) : x + y = S} and B = {(x,y) : xy = P} with the constraints implied. I'm figuring that when S says <<2>> the number of possibilites becomes $A \cup B$ right? Why do I care what P or S say afterwards when I have the set of solutions?

 

[fourier jr]

WTF! how in the world do you guys figure out that stuff?! I guess I could sit here for a couple hours until I can follow the whole solutions... :surprise:

 

[cookiemonster]

S does not know what xy is and P does not know what x+y is. However, P can make a list of possible values of x+y that would still satisfy xy and S can make a list of possible values of xy that would still satisfy x+y. <<2>> gives information to P about x+y, which P can then use to eliminate some possibilities. <<3>> gives information to S about xy, which S can then use to eliminate possibilities.

Note that if ever P determines x+y or S determines xy, they can immediately determine the solution, as it's then a 2-variable 2-equation problem with solution
$$x = \frac{1}{2}\left( S - \sqrt{S^2 - 4P} \right) \qquad y = \frac{1}{2}\left( S + \sqrt{S^2 - 4P} \right)$$

However, before <<2>> or <<3>>, P cannot uniquely determine S and S cannot uniquely determine P, so they cannot solve the system. They can only reduce it to a few possibilities.

In your notation, let C = {(x,y) : <<2>>==TRUE}. <<3>> implies that $B \cap C$ has a single entry, which therefore uniquely determines (x,y) for P. Furthermore, let D = {(x,y) : B s.t. <<3>>==TRUE}. <<4>> implies that $A \cap D$ has a single entry as well.

cookiemonster

 

[e(ho0n3]

S does not know what xy is and P does not know what x+y is. However, P can make a list of possible values of x+y that would still satisfy xy and S can make a list of possible values of xy that would still satisfy x+y. <<2>> gives information to P about x+y, which P can then use to eliminate some possibilities. <<3>> gives information to S about xy, which S can then use to eliminate possibilities.

So S doesn't know what P is and vice versa right? Does S know that he the sum of two numbers? Does P know he is the product of two numbers? You'll have to forgive me, as I am slow (i.e. a retard).

WHAT information is being given? S says "I knew that you didn't know the two numbers." So what? Who cares if he KNEW? Wouldn't it be better to KNOW what S knows. Suppose S and P are ignorant of their formulation. If S KNOWNS that P = xy for some x and y, then S can determine the pairs of numbers (x, y) such that P = xy. If P KNOWS that S = x + y for some x and y, the P can determine the pairs (x, y) such that S = x + y, and once both of them share this information (i.e. "Hey S, I have these pairs, what do you have?"), then they can both determine what the correct pair is (or pairs are).

 

[cookiemonster]

Suppose S is given the value x+y and P is given the value x*y.

Not retarded, just got to read more carefully. =]

WHAT information is being given? S says "I knew that you didn't know the two numbers." So what? Who cares if he KNEW? Wouldn't it be better to KNOW what S knows. Suppose S and P are ignorant of their formulation. If S KNOWNS that P = xy for some x and y, then S can determine the pairs of numbers (x, y) such that P = xy. If P KNOWS that S = x + y for some x and y, the P can determine the pairs (x, y) such that S = x + y, and once both of them share this information (i.e. "Hey S, I have these pairs, what do you have?"), then they can both determine what the correct pair is (or pairs are).

Sure, it'd be just great if they each told each other what they'd have. But then the problem would be absolutely trivial, and there'd be no point in it! Plus that's simply not how the problem goes. The point is to determine a solution based on the minimum information possible. S and P don't need to tell each other exactly the number they have, that's more information than necessary. All they need to say are <<2>> and <<3>> in order to determine a unique solution.

cookiemonster

 

[e(ho0n3]

OK, I read this whole thread again. I interpret the conversation as:

<<1>> S knows he is a sum of two numbers and P knows he is the product of two numbers but they don't know which two and they don't know each other.
<<2>> S tells P that he (S) is the sum of two numbers.
<<3>> P tells S that he (P) is the product of two numbers.
<<4>> There is enough information to determine a solution.

Is this right?

 

[cookiemonster]

No. S knows that he's given x + y and P knows that he's given xy from the get-go.

Take the statements at face value. There's nothing hiding.

cookiemonster

 

[Phantom]

very confusing