Register to reply

The Impossible Problem

by gravenewworld
Tags: impossible
Share this thread:
gravenewworld
#1
Jul14-04, 08:26 PM
P: 1,404
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
Phys.Org News Partner Mathematics news on Phys.org
'Moral victories' might spare you from losing again
Fair cake cutting gets its own algorithm
Effort to model Facebook yields key to famous math problem (and a prize)
rayjohn01
#2
Jul14-04, 08:45 PM
P: 284
I assume , but you did not say that the numbers are integers.
MathematicalPhysicist
#3
Jul15-04, 12:08 AM
P: 3,215
Quote Quote by gravenewworld
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 eachother value?

cookiemonster
#4
Jul15-04, 12:47 AM
P: 991
The Impossible Problem

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

cookiemonster
MathematicalPhysicist
#5
Jul15-04, 12:54 AM
P: 3,215
Quote Quote by cookiemonster
<<2>> should reveal P's number to S.

cookiemonster
not the other way around?
it reveals S's number to P.
cookiemonster
#6
Jul15-04, 12:54 AM
P: 991
Er... Yeah.

cookiemonster
zefram_c
#7
Jul15-04, 02:11 AM
P: 260
I think I have a solution, shall I post it?
cookiemonster
#8
Jul15-04, 02:18 AM
P: 991
I think I might, as well. I'm getting 4 and 13.

cookiemonster
Zurtex
#9
Jul15-04, 05:08 AM
Sci Advisor
HW Helper
P: 1,123
Quote Quote by cookiemonster
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
#10
Jul15-04, 06:46 AM
P: 991
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
#11
Jul15-04, 07:07 AM
Sci Advisor
HW Helper
P: 1,123
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
#12
Jul15-04, 07:36 AM
Sci Advisor
P: 875
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
#13
Jul15-04, 12:23 PM
P: 260
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
#14
Jul15-04, 04:20 PM
P: 1,370
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
#15
Jul15-04, 05:14 PM
Emeritus
Sci Advisor
PF Gold
Gokul43201's Avatar
P: 11,155
"Don't know" implies multiple integer solutions for the repective equations : xy = P and x+y=S.
cookiemonster
#16
Jul15-04, 05:15 PM
P: 991
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
#17
Jul15-04, 05:58 PM
P: 1,370
Quote Quote by cookiemonster
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 [itex]A \cup B[/itex] right? Why do I care what P or S say afterwards when I have the set of solutions?
fourier jr
#18
Jul15-04, 06:32 PM
P: 948
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:


Register to reply

Related Discussions
A seemingly impossible problem Introductory Physics Homework 6
Impossible problem? [Varibles ONLY] Introductory Physics Homework 2
A seemingly impossible problem from my teacher! Precalculus Mathematics Homework 3
Impossible Problem Introductory Physics Homework 2
Impossible vector problem. Help! Introductory Physics Homework 8