The Impossible Problem: Torsten Sillke, Dec. 1997 ----------------------- Sum-Product Problem (Martin Gardner Version) Two numbers (not necessarily different) are chosen from the range of positive integers greater than 1 and not greater than 20. Only the sum of the two numbers is given to mathematician S. Only the product of the two is given to mathematician P. On the telephone S says to P, "I see no way you can determine my sum." An hour later P calls him back to say, "I know your sum." Later S calls P again to report, "Now I know your product." What are the two numbers? Martin Gardner, Mathematical Games, Scientific American, 241 (Dec. 1979) 22 -- the problem Mathematical Games, Scientific American, 242 (May 1980) -- 2nd postscript A discussion of this puzzle and variants can be found in (Sallow 1995). He give a table with all possible solution pairs for different upper bounds up to 100. The unique solution for the bound 20 is (2, 6). Lee Sallows; The Impossible Problem, The Mathematical Intelligenzer, 17:1 (1995) 27-33 mailto:SALLOWS@psych.kun.nl The Impossible Problem Revisited Again, The Mathematical Intelligenzer, 17:4 (1995) 4-6 ----------------------------------------------------------------------------- Sum-Product Problem (Freudenthal/Sprows Version) 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? Hans Freudenthal; Nieuw Archief Voor Wiskunde, Ser 3, 17 (1969) 152 -- the problem Nieuw Archief Voor Wiskunde, Ser 3, 18 (1970) 102-106 -- the solution David J. Sprows; Mathematics Magazine, 49:2 (March 1976) 96 -- Problem 977 Mathematics Magazine, 50 (1977) 268 -- the solution ----------------------------------------------------------------------------- Sum-Product Problem (Brian Smith Version) Well, we are all in agreement that S and P are wizards who know the sum and product, respectively, of two integers chosen from some range, most often {2,...,99}. The dialogue is: <<1>> Mr. P.: I do not know the two numbers. <<2>> Mr. S.: I knew you didn't. Neither do I. <<3>> Mr. P.: Now I know the two numbers. <<4>> Mr. S.: Now I know the two numbers. What are the two numbers? This is the one that appeared in Brian Smith's ``The Semantics of Clocks'' with the note ``This puzzle appeared in the AI community in the late 1970's but its origins or author seem to have been lost.'' I suspect the problem is not nearly so young. The assumption in these problems that is hardly ever mentioned is that the ground rules in the first paragraph are to be considered ``public knowledge''. That is to say, both P and S know the other knows these things, each knows the other knows he knows, and so forth. The most common fallacious solutions involve omitting the range of the numbers from the public knowledge. The problem as stated in the rec.puzzles article omits the second sentence of <<2>>, but I suspect the latter is an editing error rather than a case of addressing a different problem. < Dan Hoey, mail-fun 1993 > Brian Smith; The Semantics of Clocks, ?year? ----------------------------------------------------------------------------- Sum-Product Puzzle: (rec.puzzles logic/number problem) ==> logic/number.p <== Mr. S. and Mr. P. are both perfect logicians, being able to correctly deduce any truth from any set of axioms. Two integers (not necessarily unique) are somehow chosen such that each is within some specified range. Mr. S. is given the sum of these two integers; Mr. P. is given the product of these two integers. After receiving these numbers, the two logicians do not have any communication at all except the following dialogue: <<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. Given that the above statements are absolutely truthful, what are the two numbers? ==> logic/number.s <== The answer depends upon the ranges from which the numbers are chosen. The unique solution for the ranges [2,62] through [2,500+] is: SUM PRODUCT X Y 17 52 4 13 The unique solution for the ranges [3,94] through [3,500+] is: SUM PRODUCT X Y 29 208 13 16 There are no unique solutions for the ranges starting with 1, and there are no solutions for ranges starting with numbers above 3. A program to compute the possible pairs is included below. [...] = Jeff Kenton (617) 894-4508 = = jkenton@world.std.com = ----------------------------------------------------------------------------- Sum-Product Puzzle: (Kiltinen/Young unbounded version) The situation we explore involves choosing two integers r and s, both of with are at least 2. Their sum m=r+s is given to one mathematician, Sam, while their product n=r*s is given to another, Prudence. Suppose that after some thought, they exchange the following information: Scenario I: <<1>> P.: I do not know your sum, Sam. <<2>> S.: I knew you didn't, Prudence. <<3>> P.: Now I know your sum. <<4>> S.: And now I know your product. Do we now have sufficient information to deduce values for m and n? Yes but not uniquely. The smallest solution is m = 17 = 4 + 13 and n = 52 = 4*13. Other solutions (s,r,m,n) are (16,111,127,1776), (201,556,757,111756), and (421,576,997,242496). Scenario II: <<1>> P.: I do not know your sum. <<2>> S.: Thanks for that information. <<3>> P.: I still don't know your sum. <<4>> S.: Now I know your product. <<5>> P.: And now I know your sum. The reader is encouraged to verify that m=8 and n=16 is a solution for this puzzle. Scenario III: <<1>> P.: I do not know your sum. <<2>> S.: Thanks for that information. <<3>> P.: I still don't know your sum. <<4>> S.: Thanks for that information. <<5>> P.: Thanks for that information. <<6>> S.: Now I know your product. <<7>> P.: And now I know your sum. The reader may wish to find solutions for this bigger challange. [no solution given.] John O. Kiltinen, Peter B. Young; Goldbach, Lemoine, and a Know/Don't Know Problem (Sum knoledge is productive, product knoledge is better, but Goldbach and Lemoine determine the limits.) Mathematical Magazine, 58:4 (Sep. 1985) 195-203 ----------------------------------------------------------------------------- Sum-Product Puzzle: (Gosper/Schroeppel version) Three people, S, P, and the Settor, are in a room together, and can hear each other, are perfect reasoners, etc. The Settor thinks up two numbers between 2 and 99 inclusive. He tells the sum to S, and the product to P. He asks S "What are the two numbers?" S replies "I don't know." He asks P "What are the two numbers?" P replies "I don't know." At this point, S says "Now I know!" And then P says "Now I know!" What are the two numbers? I think I originally heard this from Gosper some years ago. "Richard Schroeppel" letter to math-fun from Nov. 1993 The solution given in math-fun are (3,4), (69,96), and (84,84). ----------------------------------------------------------------------------- Sum-Product Puzzle: (Hess version) Mathematicians S and P. Two positive integers, each greater than 1, are chosen. The sum is revealed to S; the product is revealed to P. Both S and P are given the information in this problem. The conversation between them goes as follows: <<1>> S: There is no way you can know my number. <<2>> P: I still don?t know your number. <<3>> S: I now know your number. What are the numbers S and P? email from Dick Hess on 4. Dec. 1997 ----------------------------------------------------------------------------- Sum-Sum of Squares Puzzle: (Hess version) Two positive integers <50 are choosen. The sum is revealed to A; the sum of the squares is revealed to B. Both A and B are given the information in this problem. The conservation between them goes as follows: <<1>> B: I can't tell what the numbers are. <<2>> A: I can't tell what the numbers are. <<3>> B: I can't tell what the numbers are. <<4>> A: I can't tell what the numbers are. <<5>> B: I can't tell what the numbers are. <<6>> A: I can't tell what the numbers are. <<7>> B: Now I can tell what the numbers are. What are the two numbers. The answers section only states: Through a long set of logical steps one can deduce that the numbers are 8 and 9. R. Hess; Puzzles from around the world, 1997, Problem 41 T. Ferguson; Mathematics Magazine, 56 (1983) 177 -- Problem 1173 Mathematics Magazine, 57 (1984) 180-181 -- Solution 1173 ----------------------------------------------------------------------------- Erich Friedman -- P and S are given the product and sum of two non-zero digits (1 to 9). 1. P says "I don't know the numbers". S says "I don't know the numbers". 2. P says "I don't know the numbers". S says "I don't know the numbers". 3. P says "I don't know the numbers". S says "I don't know the numbers". 4. P says "I don't know the numbers". S says "I don't know the numbers". 5. P says "I know the numbers". what are they? http://www.mathpuzzle.com/ at (2000-12-28) ============================================================================= Below there is a further variant, which was discussed in math-fun 1993. Note that the order of S and P have been changed. ----------------------------------------------------------------------------- D I S C U S S I O N from M A T H - F U N (1993) ----------------------------------------------------------------------------- From: "Richard Schroeppel" To: math-fun Subject: S & P puzzle I'm trying to recall the following puzzle. The answer depends on the detailed wording, so I'd like to get it right. I think I originally heard this from Gosper some years ago. An Approximate Version of The S & P Puzzle. Three people, S, P, and the Settor, are in a room together, and can hear each other, are perfect reasoners, etc. The Settor thinks up two numbers between 2 and 99 inclusive. He tells the sum to S, and the product to P. He asks S "What are the two numbers?" S replies "I don't know." He asks P "What are the two numbers?" P replies "I don't know." At this point, S says "Now I know!" And then P says "Now I know!" What are the two numbers? Rich ----------------------------------------------------------------------------- Date: Fri, 19 Nov 93 From: "cal" To: math-fun Subject: number puzzle on sum and product starting with the version rich gave, by construction the product is composite, so we (i.e., everybody) knows that we know the sum is ambiguous (though this doesn't seem like much of a restriction - perhaps the S and P questions are in the other order), even if we don't all know what it is we know the product is ambiguous, even if we don't all know what it is - this would greatly limit the choices among those choices, i guess there are very few that can be factored in two different ways with the same sum - since that fact determines the sum, it must be the case that there is only one pair that works that way - a number that has two different factorizations into integers between 2 and 99 (inclusive) that have the same sum - i imagine that a little algebra could find them now this isn't quite enough analysis to determine the proper sequence of questions oh, well more later, cal ---------------------------------------------------------------------------------- Date: Tue, 23 Nov 93 From: "Shel Kaphan" To: math-fun Subject: S&P Puzzle: SPOILER (with surprise ending!) I showed this puzzle to some friends, as it has been a favorite of mine since Rich showed it to me in 1977 or so... Here's an interesting result that Dan Bornstein came up with. It turns out that the upper bounds do matter -- they actually introduce two additional solutions! --Shel Kaphan >From Dan: I find these three solutions to the problem as stated: (3,4) (69,96) (84,84) Here's a breakdown of info for each possible sum (below). Part A is the different ways to get the sum of the two numbers when S knows nothing about P. Part B is the different ways that P can get the product when P knows that S doesn't know the pair. Part C is the different ways that S can get the sum knowing that P doesn't know the product. This can be either because for a given pair, there's only one unique factoring into two numbers or because all the other factorings have one or other of the numbers be out of the given range. Part D is the different ways that P can get the product knowing that S knows the pair. A solution is a pair such that sizeof(A) != 1 and sizeof(B) != 1 and sizeof(C) == 1 and sizeof(D) == 1. So, if there's only one solution and it's (3,4), where's the flaw in my reasoning (or my numbers)? Sum A B C D ------------------------- 4: 1 -- -- -- 5: 1 -- -- -- 6: 2 1 -- -- 7: 2 2 1 1 --> (3,4) ------------------------------------- SOLUTION (3,4): A: S knows nothing 7 = 2 + 5 7 = 3 + 4 B: P knows S doesn't know 12 = 2 * 6 12 = 4 * 3 C: S knows that P doesn't know 7 = 3 + 4 D: P knows that S knows 12 = 4 * 3 ------------------------------------- 8: 3 2 2 -- 9: 3 2 2 -- 10: 4 1 -- -- 11: 4 3 4 -- 12: 5 4 3 -- 13: 5 3 4 -- 14: 6 1 -- -- 15: 6 3 5 -- 16: 7 3 5 -- 17: 7 5 7 -- 18: 8 2 6 -- 19: 8 5 7 -- 20: 9 4 7 -- 21: 9 3 8 -- 22: 10 1 -- -- 23: 10 5 10 -- 24: 11 7 8 -- 25: 11 5 10 -- 26: 12 1 -- -- 27: 12 3 12 -- 28: 13 4 11 -- 29: 13 6 13 -- 30: 14 4 10 -- 31: 14 8 13 -- 32: 15 3 13 -- 33: 15 3 13 -- 34: 16 1 -- -- 35: 16 3 16 -- 36: 17 5 13 -- 37: 17 3 17 -- 38: 18 1 -- -- 39: 18 4 16 -- 40: 19 5 16 -- 41: 19 8 19 -- 42: 20 3 16 -- 43: 20 5 19 -- 44: 21 2 17 -- 45: 21 2 20 -- 46: 22 1 -- -- 47: 22 4 22 -- 48: 23 7 17 -- 49: 23 6 22 -- 50: 24 1 -- -- 51: 24 3 23 -- 52: 25 2 19 -- 53: 25 4 25 -- 54: 26 2 20 -- 55: 26 6 25 -- 56: 27 4 20 -- 57: 27 2 25 -- 58: 28 1 -- -- 59: 28 3 27 -- 60: 29 7 22 -- 61: 29 3 27 -- 62: 30 1 -- -- 63: 30 2 27 -- 64: 31 2 23 -- 65: 31 6 28 -- 66: 32 2 22 -- 67: 32 3 29 -- 68: 33 2 24 -- 69: 33 3 28 -- 70: 34 2 25 -- 71: 34 8 30 -- 72: 35 5 26 -- 73: 35 2 30 -- 74: 36 1 -- -- 75: 36 2 29 -- 76: 37 2 26 -- 77: 37 3 30 -- 78: 38 1 -- -- 79: 38 5 32 -- 80: 39 4 28 -- 81: 39 2 32 -- 82: 40 1 -- -- 83: 40 2 33 -- 84: 41 5 30 -- 85: 41 2 32 -- 86: 42 1 -- -- 87: 42 2 33 -- 88: 43 2 29 -- 89: 43 6 35 -- 90: 44 3 32 -- 91: 44 3 34 -- 92: 45 2 31 -- 93: 45 2 35 -- 94: 46 1 -- -- 95: 46 2 36 -- 96: 47 4 32 -- 97: 47 4 38 -- 98: 48 1 -- -- 99: 48 3 36 -- 100: 49 1 -- -- 101: 49 3 38 -- 102: 49 1 -- -- 103: 48 3 38 -- 104: 48 1 -- -- 105: 47 1 -- -- 106: 47 1 -- -- 107: 46 1 -- -- 108: 46 2 28 -- 109: 45 4 35 -- 110: 45 1 -- -- 111: 44 4 31 -- 112: 44 3 30 -- 113: 43 3 32 -- 114: 43 1 -- -- 115: 42 2 29 -- 116: 42 1 -- -- 117: 41 1 -- -- 118: 41 1 -- -- 119: 40 1 -- -- 120: 40 5 19 -- 121: 39 1 -- -- 122: 39 1 -- -- 123: 38 1 -- -- 124: 38 1 -- -- 125: 37 2 24 -- 126: 37 2 20 -- 127: 36 4 25 -- 128: 36 1 -- -- 129: 35 2 21 -- 130: 35 1 -- -- 131: 34 2 22 -- 132: 34 2 12 -- 133: 33 1 -- -- 134: 33 1 -- -- 135: 32 1 -- -- 136: 32 1 -- -- 137: 31 2 17 -- 138: 31 1 -- -- 139: 30 1 -- -- 140: 30 2 12 -- 141: 29 1 -- -- 142: 29 1 -- -- 143: 28 1 -- -- 144: 28 3 8 -- 145: 27 1 -- -- 146: 27 1 -- -- 147: 26 1 -- -- 148: 26 1 -- -- 149: 25 1 -- -- 150: 25 1 -- -- 151: 24 2 9 -- 152: 24 1 -- -- 153: 23 1 -- -- 154: 23 1 -- -- 155: 22 2 5 -- 156: 22 1 -- -- 157: 21 1 -- -- 158: 21 1 -- -- 159: 20 1 -- -- 160: 20 1 -- -- 161: 19 2 6 -- 162: 19 1 -- -- 163: 18 1 -- -- 164: 18 1 -- -- 165: 17 1 -- -- 166: 17 1 -- -- 167: 16 1 -- -- 168: 16 2 1 1 --> (84,84) ------------------------------------- SOLUTION (84,84): A: S knows nothing 168 = 69 + 99 168 = 70 + 98 168 = 71 + 97 168 = 72 + 96 168 = 73 + 95 168 = 74 + 94 168 = 75 + 93 168 = 76 + 92 168 = 77 + 91 168 = 78 + 90 168 = 79 + 89 168 = 80 + 88 168 = 81 + 87 168 = 82 + 86 168 = 83 + 85 168 = 84 + 84 B: P knows S doesn't know 7056 = 72 * 98 7056 = 84 * 84 C: S knows that P doesn't know 168 = 84 + 84 D: P knows that S knows 7056 = 84 * 84 ------------------------------------- 169: 15 1 -- -- 170: 15 1 -- -- 171: 14 1 -- -- 172: 14 1 -- -- 173: 13 1 -- -- 174: 13 1 -- -- 175: 12 1 -- -- 176: 12 1 -- -- 177: 11 1 -- -- 178: 11 1 -- -- 179: 10 1 -- -- 180: 10 1 -- -- 181: 9 1 -- -- 182: 9 1 -- -- 183: 8 1 -- -- 184: 8 1 -- -- 185: 7 1 -- -- 186: 7 1 -- -- 187: 6 1 -- -- 188: 6 1 -- -- 189: 5 1 -- -- 190: 5 1 -- -- 191: 4 1 -- -- 192: 4 1 -- -- 193: 3 1 -- -- 194: 3 1 -- -- 195: 2 1 -- -- 196: 2 1 -- -- 197: 1 -- -- -- 198: 1 -- -- -- -dan danfuzz@kaleida.com Will you dance with me, my little pickled herring? -- Legendary Pink Dots ---------------------------------------------------------------------------------- From the rec.puzzles FAQ-List part1. ==> logic/number.p <== Mr. S. and Mr. P. are both perfect logicians, being able to correctly deduce any truth from any set of axioms. Two integers (not necessarily unique) are somehow chosen such that each is within some specified range. Mr. S. is given the sum of these two integers; Mr. P. is given the product of these two integers. After receiving these numbers, the two logicians do not have any communication at all except the following dialogue: <<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. Given that the above statements are absolutely truthful, what are the two numbers? ==> logic/number.s <== The answer depends upon the ranges from which the numbers are chosen. The unique solution for the ranges [2,62] through [2,500+] is: SUM PRODUCT X Y 17 52 4 13 The unique solution for the ranges [3,94] through [3,500+] is: SUM PRODUCT X Y 29 208 13 16 There are no unique solutions for the ranges starting with 1, and there are no solutions for ranges starting with numbers above 3. A program to compute the possible pairs is included below. #include /* BEGINNING OF PROBLEM STATEMENT: Mr. S. and Mr. P. are both perfect logicians, being able to correctly deduce any truth from any set of axioms. Two integers (not necessarily unique) are somehow chosen such that each is within some specified range. Mr. S. is given the sum of these two integers; Mr. P. is given the product of these two integers. After receiving these numbers, the two logicians do not have any communication at all except the following dialogue: <<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. Given that the above statements are absolutely truthful, what are the two numbers? END OF PROBLEM STATEMENT */ #define SMALLEST_MIN 1 #define LARGEST_MIN 10 #define SMALLEST_MAX 50 #define LARGEST_MAX 500 long P[(LARGEST_MAX + 1) * (LARGEST_MAX + 1)]; /* products */ long S[(LARGEST_MAX + 1) + (LARGEST_MAX + 1)]; /* sums */ find(long min, long max) { long i, j; /* * count factorizations in P[] * all P[n] > 1 satisfy <<1>>. */ for(i = 0; i <= max * max; ++i) P[i] = 0; for(i = min; i <= max; ++i) for(j = i; j <= max; ++j) ++P[i * j]; /* * decompose possible SUMs and check factorizations * all S[n] == min - 1 satisfy <<2>>. */ for(i = min + min; i <= max + max; ++i) { for(j = i / 2; j >= min; --j) if(P[j * (i - j)] < 2) break; S[i] = j; } /* * decompose SUMs which satisfy <<2>> and see which products * they produce. All (P[n] / 1000 == 1) satisfy <<3>>. */ for(i = min + min; i <= max + max; ++i) if(S[i] == min - 1) for(j = i / 2; j >= min; --j) if(P[j * (i - j)] > 1) P[j * (i - j)] += 1000; /* * decompose SUMs which satisfy <<2>> again and see which products * satisfy <<3>>. Any (S[n] == 999 + min) satisfies <<4>> */ for(i = min + min; i <= max + max; ++i) if(S[i] == min - 1) for(j = i / 2; j >= min; --j) if(P[j * (i - j)] / 1000 == 1) S[i] += 1000; /* * find the answer(s) and print them */ printf("[%d,%d]\n",min,max); for(i = min + min; i <= max + max; ++i) if(S[i] == 999 + min) for(j = i / 2; j >= min; --j) if(P[j * (i - j)] / 1000 == 1) printf("{ %d %d }: S = %d, P = %d\n", i - j, j, i, (i - j) * j); } main() { long min, max; for (min = SMALLEST_MIN; min <= LARGEST_MIN; min ++) for (max = SMALLEST_MAX; max <= LARGEST_MAX; max++) find(min,max); } ------------------------------------------------------------------------- = Jeff Kenton (617) 894-4508 = = jkenton@world.std.com = ------------------------------------------------------------------------- END OF ARCHIVE ENTRY ----------------------------------------------------------------------------- Date: Sat, 27 Nov 1993 From: "Shel Kaphan" To: math-fun Subject: beating a dead S&P horse If we're sharing programs for this problem, here's the one I wrote to solve it. It follows the logic of the problem (the way it is stated anyway) a little more closely than the other program, but maybe isn't as general, though I don't quite get what his "lower limit" means anyway. ----------------------------------------------------------------------------- #include #include main() { int a,b; int s, p; for(s=4; s<= 198; s++) { if ((a=satisfiesRule4(s)) != 0) printf("winning sum %d (%d + %d)\n", s, a, s-a); } } /* Mr. S: I know! */ /* Given s, for all pairs (a,b), a+b=s, 2 <= a,b <= 99, true if exactly one pair satisfies rules 2 and 3 */ int satisfiesRule4(int s) { int a,b; int limit = s/2; int winner=0; if (!satisfiesRule2(s)) /* this is really necessary -- some false answers */ return 0; /* are produced without it. */ for(a=2; a<=limit; a++) { b = s-a; if (satisfiesRule3(a*b)) { if (winner) return 0; winner=a; } } return winner; } /* Mr. P: I know! */ /* Given p, for all pairs (a,b), ab=p, 2 <= a,b <= 99, true if exactly one pair satisfies rule 2 */ int satisfiesRule3(int p) { int i; int limit; int winner=0; limit = (int)sqrt((double)p); for(i=2; i<=limit; i++) { if (p%i == 0) { int j = p/i; if (!inRange(j)) continue; if (satisfiesRule2(i+j)) { if (winner) return 0; winner=1; } } } return winner; } /* Mr. S: I knew you didn't know */ /* Given s, for all pairs (a,b), a+b=s, 2 <= a,b <= 99, true if at least one of a or b is composite */ int satisfiesRule2(int s) { return isAlwaysSumOfComposite(s); } int inRange(int x) { return (2<=x && x<=99); } int isAlwaysSumOfComposite(int s) { int a; int limit = s/2; for(a=2; a<=limit; a++) { if (isPrime(a) && isPrime(s-a)) { return 0; } } return 1; } /* dumbest possible way to compute this, almost. */ int isPrime(int x) { int i; int limit; if (x<=3) return 1; limit = (int)sqrt((double)x); for(i=2; i<=limit; i++) { if ((x%i)==0) return 0; } return 1; } ----------------------------------------------------------------------------- Date: Sat, 27 Nov 1993 From: "Shel Kaphan" To: math-fun Subject: Re: S&P puzzle Beating this into the ground just a bit further... I modified the program I sent out to remove the upper limit. (Well, I set it to 10,000 and made a table for determining primality so it would finish while I'm still alive). I ran it out to S=5000. S is the outermost iteration in my algorithm. I determined that there are 15 pairs of numbers which solve the problem (up to S=5000, and it looks an awful lot like that's going to be it), and they have some similarities: 4 13 4 61 16 73 16 111 64 73 32 131 16 163 4 181 64 127 4 229 8 239 13 256 32 311 32 641 32 821 I *think* the program is correct. Notice that all the answers consist of a power of two and another number, which is a prime in all cases but one (16,111). Can anyone make a stab at explaining why that should be so? (Or, maybe just stab me for being wrong?!) Any opinions about whether there might be more solutions? ----------------------------------------------------------------------------- Date: Sat, 27 Nov 1993 From: "Shel Kaphan" To: math-fun Subject: S&P: spoke too soon The previous small number of solutions I mentioned had to do with the upper limit of 10000 I still had in part of the program (the "inRange" check). With no upper limit, it seems that there are more "exceptions", and also (of course) more solutions. I annotated the ones that are not {2^n, prime} 17 = 4 + 13 65 = 4 + 61 89 = 16 + 73 127 = 16 + 111 111 is a composite 137 = 64 + 73 163 = 32 + 131 179 = 16 + 163 185 = 4 + 181 191 = 64 + 127 233 = 4 + 229 247 = 8 + 239 269 = 13 + 256 305 = 64 + 241 343 = 32 + 311 427 = 8 + 419 457 = 8 + 449 547 = 128 + 419 569 = 256 + 313 583 = 71 + 512 613 = 101 + 512 637 = 128 + 509 667 = 8 + 659 673 = 32 + 641 697 = 128 + 569 733 = 32 + 701 757 = 201 + 556 201 is a composite 556 is a composite 779 = 256 + 523 787 = 128 + 659 817 = 8 + 809 821 = 64 + 757 853 = 32 + 821 929 = 256 + 673 967 = 128 + 839 977 = 40 + 937 40 is a composite 937 is a prime 989 = 256 + 733 997 = 421 + 576 421 is a prime 576 is a composite 1045 = 32 + 1013 1087 = 36 + 1051 36 is a composite 1051 is a prime 1117 = 8 + 1109 1207 = 16 + 1191 1191 is composite 1267 = 8 + 1259 1273 = 512 + 761 1289 = 256 + 1033 1297 = 8 + 1289 1327 = 8 + 1319 1345 = 128 + 1217 1357 = 128 + 1229 etc. ----------------------------------------------------------------------------- Date: Sun, 28 Nov 1993 From: "Shel Kaphan" To: math-fun Subject: Re: S&P: spoke too soon From: "John Conway" Date: Sun, 28 Nov 93 what IS this problem - I'm lost, but would like to know. JHC As per the restatement Rich recently posted: Mr. S. and Mr. P. are both perfect logicians, being able to correctly deduce any truth from any set of axioms. Two integers (not necessarily unique) are somehow chosen such that each is within some specified range. Mr. S. is given the sum of these two integers; Mr. P. is given the product of these two integers. After receiving these numbers, the two logicians do not have any communication at all except the following dialogue: <<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. This is different from the other version which I think Rich slightly mis-remembered, as I also had, in which <<2>> was "I don't know either". That problem had (3,4) as a solution (as well as (69,96) and (84,84) if the two numbers are limited to [2,99]). This one has (4,13) as a solution if the same limits are used, but lots of additional solutions if no upper limit is imposed. I'm still wondering if any of the more numerologically inclined can explain why the solutions are *usually* but not always (2^n, prime). BTW I have the answers up to S=8000 if anyone wants them. Shel ----------------------------------------------------------------------------- Date: Mon, 29 Nov 93 From: hoey To: math-fun Subject: Messrs S and P Well, we are all in agreement that S and P are wizards who know the sum and product, respectively, of two integers chosen from some range, most often {2,...,99}. The dialogue I've seen most often is: <<1>> Mr. P.: I do not know the two numbers. <<2>> Mr. S.: I knew you didn't. Neither do I. <<3>> Mr. P.: Now I know the two numbers. <<4>> Mr. S.: Now I know the two numbers. There are, of course, any number of variants of this statement, but this is the one that appeared in Brian Smith's ``The Semantics of Clocks'' with the note ``This puzzle appeared in the AI community in the late 1970's but its origins or author seem to have been lost.'' I suspect the problem is not nearly so young. The problem Rich set omitted the first sentence of <<2>>. The problem as stated in the rec.puzzles article omits the second sentence of <<2>>, but I suspect the latter is an editing error rather than a case of addressing a different problem. The assumption in these problems that is hardly ever mentioned is that the ground rules in the first paragraph are to be considered ``public knowledge''. That is to say, both P and S know the other knows these things, each knows the other knows he knows, and so forth. The most common fallacious solutions involve omitting the range of the numbers from the public knowledge. As I recall, there's a version in which the range has a lower bound but no upper bound. The interesting part there is that you need to actually prove something, rather than just write a program to check all the possible pairs. I seem to recall a variant that depends on Goldbach's conjecture, too. Dan Hoey Hoey@AIC.NRL.Navy.Mil ----------------------------------------------------------------------------- From - Thu Jan 29 10:21:13 1998 From: evan@scd.hp.com (Evan Whitney) Newsgroups: rec.puzzles Subject: Variation of Mr. P and Mr. S Date: 28 Jan 1998 17:00:01 GMT Here's a variation of Mr. P and Mr. S that I just made up. I believe the solution is unique and the problem completely defined. One logician, Mr. S, is told the sum of two integers. The other logician, Mr. P, is told the product of the same two integers. Mr. P knows that Mr. S knows the sum, and Mr. S knows that Mr. P knows the product. The following conversation ensues, you decide who is who: Mr. X: "I don't know what the two integers are." Mr. Y: "I knew you didn't know what they are." Mr. X: "I knew you knew that." Mr. Y: "This conversation could go on forever." Mr. X: "I still don't know what the integers are." Mr. Y: "Now I know what they are." Mr. X: "Now I know what they are, too." What are the two integers? Evan Whitney evan@scd.hp.com