The Impossible Problem

  1. 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
     
  2. jcsd
  3. I assume , but you did not say that the numbers are integers.
     
  4. do they both know eachother value?
     
  5. <<2>> should reveal P's number to S.

    cookiemonster
     
  6. not the other way around?
    it reveals S's number to P.
     
  7. Er... Yeah.

    cookiemonster
     
  8. I think I have a solution, shall I post it?
     
  9. I think I might, as well. I'm getting 4 and 13.

    cookiemonster
     
  10. Zurtex

    Zurtex 1,123
    Science Advisor
    Homework Helper

    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.
     
  11. 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
     
  12. Zurtex

    Zurtex 1,123
    Science Advisor
    Homework Helper

    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.
     
    Last edited: Jul 15, 2004
  13. Njorl

    Njorl 875
    Science Advisor

    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
     
  14. 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>>
     
  15. 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?
     
  16. Gokul43201

    Gokul43201 11,141
    Staff Emeritus
    Science Advisor
    Gold Member

    "Don't know" implies multiple integer solutions for the repective equations : xy = P and x+y=S.
     
  17. 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
     
  18. 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?
     
  19. 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:
     
  20. 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
    [tex]x = \frac{1}{2}\left( S - \sqrt{S^2 - 4P} \right) \qquad y = \frac{1}{2}\left( S + \sqrt{S^2 - 4P} \right) [/tex]

    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 [itex]B \cap C[/itex] 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 [itex]A \cap D[/itex] has a single entry as well.

    cookiemonster
     
  21. 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).
     
Know someone interested in this topic? Share a link to this question via email, Google+, Twitter, or Facebook

Have something to add?