Register to reply 
The Impossible Problemby gravenewworld
Tags: impossible 
Share this thread: 
#1
Jul1404, 08:26 PM

P: 1,408

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 


#2
Jul1404, 08:45 PM

P: 284

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



#3
Jul1504, 12:08 AM

P: 3,243




#4
Jul1504, 12:47 AM

P: 988

The Impossible Problem
<<2>> should reveal P's number to S.
cookiemonster 


#5
Jul1504, 12:54 AM

P: 3,243

it reveals S's number to P. 


#6
Jul1504, 12:54 AM

P: 988

Er... Yeah.
cookiemonster 


#7
Jul1504, 02:11 AM

P: 260

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



#8
Jul1504, 02:18 AM

P: 988

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


#9
Jul1504, 05:08 AM

Sci Advisor
HW Helper
P: 1,123

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. 


#10
Jul1504, 06:46 AM

P: 988

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 


#11
Jul1504, 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. 


#12
Jul1504, 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 


#13
Jul1504, 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>> 


#14
Jul1504, 04:20 PM

P: 1,367

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?



#15
Jul1504, 05:14 PM

Emeritus
Sci Advisor
PF Gold
P: 11,155

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



#16
Jul1504, 05:15 PM

P: 988

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 


#17
Jul1504, 05:58 PM

P: 1,367




#18
Jul1504, 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 