From: "James S.W. Wong" To: "M. K. Kwong \(Man Kam\)" , "Anton Zettl" , "Qingkai Kong" Subject: A Puzzle Date: Mon, 9 Sep 2002 17:04:56 +0800 Dear Man Kam, Tony and Qing-Kai, My good friend Professor David Liu just retired as President of Taiwan's Tsing Hua University and is now a Visiting Professor of Computer Science at the City University of Hong Kong. David was formally chair professors at MIT and University of Illinois, Urbana. He challenged me with the following puzzle: "Two numbers x and y, 1 Subject: A puzzle To: zettl@math.niu.edu (Anton Zettl), rusin@math.niu.edu (Dave Rusin), kong@math.niu.edu (Qingkai Kong), kwong@nwsgpa.ih.lucent.com, jsww@chinnethonkwok.com Date: Tue, 10 Sep 2002 20:46:42 -0500 (CDT) Dear James, Man Kam, Tony, Qingkai: Tony shared the puzzle with me at lunch today. After discussing my solution with Tony and Qingkai I thought it might be worthwhile writing it up. =================================================== We will assume x and y must be integers. Now I know. Since A is not able to determine x and y from the product his knowledge of the product p alone, p=x.y cannot have both x and y prime. When B declares that he knew that A would not be able to determine x and y from knowledge of the product alone, he reveals that the sum s = x + y cannot be written as the sum of two primes. By Goldbach's conjecture for even numbers up to 100 (or by quick survey of them) we know that s must be odd. It is also the case that s cannot be written as s = 2 + q where q is a prime. Thus the list L of candidates for s is not too large L: 11, 17, 23, 27, 29, 35, 37, 41, .... 3 is not on the list since both x and y are greater than 1. Next to each value of s = x + y on the list we will write all possible products p = x.y as follows: s = 11 : 2.9 = 18 3.8 = 24 4.7 = 28 5.6 = 30 * s = 17 : 2.15 = 30 * 3.14 = 42 * 4.13 = 52 5.12 = 60 * 6.11 = 66 * 7.10 = 70 * 8.9 = 72 * s = 23 : 2.21 = 42 * 3.20 = 60 * 4.19 = 76 etc. s = 27 : 2.25 = 50 3.24 = 72 * etc. s = 29 : 2.27 = 54 etc s = 35 : 2.33 = 66 * 3.32 = 96 etc. s = 37 : 2.35 = 70 * 3.24 = 102 etc. s = etc. In making this expanded list we have marked with a " * " each product p which appears next to more than one sum s. We know that the p = 52 next to s = 17 will not get a * since all of the products I didn't check are larger than 52. When A declares "Now, I know" this means that the product p (whatever it is) turns up next to only one s. Thus A knows p and s and so x and y. Next in order for B to be able to also declare "Now, I know", it must be the case that the list of products next to his s must have only one product without a *. (s = 17 is an example of such behavior.) Since now B knows s and p, he knows x and y. When C declares "Now, I know", we do too, because in order for C to know the answer, there must be only one s for which there is only one p without a *. Since s = 17 has one and only one unstarred product p=52, we do not have to make all the lists (as C must have done to find the values for s and p), we know that x + y = 17 and x.y = 52. Thus x and y must be 4 and 13. Remark. In order to make their declaration neither A nor B needed to make the whole list. A had to factor his p into every product of two integers greater than one. Then he took the sums of these two integers and looked at the list L of candidates. Since only one of the sums was on the list he was able to declare. (If more than one of the sums had been on the list L, A would not have been able to claim he knew the values of x and y.) Similarly, once B knows that A's product was such that one and one one of the sums appeared on L he merely computed the list of products next to his known s, and then checked which of these products could not be factored as more than one product u.v such that u + v was on the list L. Alas poor C had to complete the full list of ALL products next to each s to see that the s = 17 and p = 52 was unique. Then he knew the answer. We were lucky, C did most of the work. Once we knew that C knew, then we knew that the s = 17 and p = 52 had to be the answer. Is this the easiest solution? If you find a better one (or error in this!), please let me know. Bill Blair ============================================================================== From: kwong@nwsgpa.ih.lucent.com Subject: Re: A puzzle To: blair@math.niu.edu (Bill Blair) Date: Tue, 10 Sep 2002 23:04:27 -0500 (CDT) Cc: zettl@math.niu.edu (Anton Zettl), rusin@math.niu.edu (Dave Rusin), kong@math.niu.edu (Qingkai Kong), kwong@nwsgpa.ih.lucent.com, jsww@chinnethonkwok.com, blair@math.niu.edu Dear All, I didn't expect that this puzzle will generate such intense interest. I guess most of us pretty much think along similar lines. I just want to add a couple of ideas that may simplify the argument a little by eliminating a few more cases right at the beginning. May I use the traditional math conventions? Lemma 1. The product cannot have a prime factor >= 29. Proof. If xy has a prime factor p >= 29, then p must be a factor of either x or y. Without loss of generality (our standard math terminology :), let p be a factor of x. But x < 51, so x must be p. This contradicts the assumption that A does not know x and y. ||| Lemma 2. xy cannot be 49 x 49. Proof. If A is given 49 x 49, s/he should know right away the answer because 49, 49 is the only possible solution (no other 2 numbers both < 51 can have that product). Lemma 3. The sum x+y must be < 31. Proof. B knows that A cannot be given 2 x 29 (because if so A should know x and y right away). The only way B can know that is because the sum given to him/her is not 2+29. Likewise, the sum cannot be 3+29, ..., 50+29. Apply the same argument using 47 in place of 29, we see that the sum cannot be 47+33, ..., 47+50. So far we have eliminated the cases of 31 to 97 for x+y. By Lemma 2, B knows that the product cannot be 49 x 49, because the sum s/he sees is not 98. x+y cannot be 100, otherwise A or B will know that x and y must be both 50. Similarly x+y cannot be 99, because the solution will obviously be 49 and 50. ||| As Bill already pointed out x+y cannot be the sum of 2 primes (see the additional note below): after eliminating these (from 5 to 30), what's left are the 5 cases: x+y = 11, 17, 23, 27, and 29 The rest will be as explained by Bill. ******************************************************************** By the way, we cannot simply apply Goldbach's conjecture (I used the same argument too at first, but then I found a slight flaw) to eliminate all even cases from x+y. We need a stronger form: namely, An even numbers < 100 can be eliminated if it is the sum of 2 odd primes, both less than 51. For instance, we cannot eliminate 98 just because it is the sum of 2 primes 11 + 87 (the problem requires that both x and y be < 51). In fact, we cannot eliminate 98 by using this line of argument because it is not the sum of 2 primes both < 51. That is why I need Lemma 2 to eliminate 98. ******************************************************************** Once again in the spirit of a mathematician, I offer the following slight strengthening of the result: We can relax the restriction 1 < x, y < 51 to 1 < x, y < 60. and I conjecture that we can still push the upper bound further. Lemma 1 still works, and perhaps Lemma 2 as well (I did not have time to check the whether we can eliminate the additional case x+y = 101 ... 120), but my guess is that we can. man ============================================================================== Date: Wed, 11 Sep 2002 01:52:20 -0500 (CDT) From: rusin@math.niu.edu To: blair@math.niu.edu Subject: Re: A puzzle Bill, I'm confused. We're trying to determine which of the 1225 pairs {x,y} is consistent with the data. Everyone who hears A's first pronouncement knows that the possible values for the product p are somewhat reduced; p must be NON-uniquely factorizable as a product of two integers in (1, 51). I count 266 possible values for p, corresponding to 707 of the initial pairs. (12=2*6=3*4, 16=2*8=4*4, ...) Now, you correctly point out that B's assertion "I knew you wouldn't know!" greatly limits the possible values of the sum. But I think it limits the values even more than you are suggesting. For example, the sum _cannot_ be 37: if B saw that the sum were 37, he could think, "Well, it is possible that the numbers are 6 and 31, in which case, if A sees that the product is 126, he will know immediately what x and y are." In fact, if I did this correctly, the ONLY possible values for the sum are 11, 17, 23, 27, and 29. In every other case, B would not be so cocksure on his first response. I think this means that more information is available after B's first pronouncement than you were expecting. So everyone, even our observer C, has the sum s nearly pinned down after B's first statement. This means A is almost surely able to finish: knowing the product p and the five possible values for s, he has only to see if there is a unique s for which X^2 - s X + p has two integer roots in the right range. The fact that A _does_ announce he knows x and y limits p to those among the 266 prior candidates which satisfy the condition of the previous paragraph. I find that there are 32 such values of p which are attached to a unique such quadratic. So everyone (even observer C) has reduced the problem to picking the right pair from among just 32 remaining choices. Here they are, showing x,y,s,p: [2, 9, 11, 18], [3, 8, 11, 24], [4, 7, 11, 28], [4, 13, 17, 52], [6, 11, 17, 66], [7, 10, 17, 70], [4, 19, 23, 76], [5, 18, 23, 90], [6, 17, 23, 102], [7, 16, 23, 112], [10, 13, 23, 130], [11, 12, 23, 132], [2, 25, 27, 50], [4, 23, 27, 92], [5, 22, 27, 110], [7, 20, 27, 140], [8, 19, 27, 152], [9, 18, 27, 162], [10, 17, 27, 170], [11, 16, 27, 176], [13, 14, 27, 182], [2, 27, 29, 54], [3, 26, 29, 78], [4, 25, 29, 100], [6, 23, 29, 138], [7, 22, 29, 154], [8, 21, 29, 168], [10, 19, 29, 190], [11, 18, 29, 198], [12, 17, 29, 204], [13, 16, 29, 208], [14, 15, 29, 210] Here's the rub: It seems to me that this makes B unable to assert, "I now know the numbers" on the second round, no matter what the two values were! NONE of the five values for the sum s corresponds to a unique pair among these 32. You state that the pair {4,13} is a solution, but I am not sure. I agree, A would see '52' and say "I can't tell". THen B would see '17' and, as I agreed above, would say "I knew you couldn't tell". Then A would think, ah, the sum must be one of those 5 numbers, and would deduce that the pair is {4,13}. BUT -- how does that help B next? Holding '17' as the sum is not sufficient to rule out the possibility that the pair is {7,10}. I think you argued that if the numbers were 7,10 then A wouldn't know what the pair is, because A would see only the product '70', and would not be able to determine whether the pair is {7,10} or {2,35}. But I say that A COULD rule out the latter case. I believe that A knows that the sum CANNOT be 37, for if B had seen that the sum were 37, he would not have made his confident claim, as noted above. And more generally, B would have no certainty in the final move. I believe every one of these 32 would lead to the appropriate responses from A, then B, then A. So what is B to do? He only knows that {x,y} is one of these 32 pairs, and knows what the sum is (one of the 5 values). IN NO CASE is it true that this information is sufficient to determine the solution. It is very easy for me to generate all 1225 pairs in Maple and then to filter out subsets consistent with one or another set of observations. I just can't seem to make the calculations jive with your claim. dave ============================================================================== From: Bill Blair Subject: Re: A puzzle To: kwong@nwsgpa.ih.lucent.com Date: Wed, 11 Sep 2002 09:37:46 -0500 (CDT) Cc: blair@math.niu.edu (Bill Blair), kong@math.niu.edu (Qingkai Kong), zettl@math.niu.edu (Anton Zettl), rusin@math.niu.edu (Dave Rusin), jsww@chinneyhonkwok.com Man: Thanks for your e-mail. The application I tried to make of Goldbach is clearly wrong and I'd have to eliminate the evens by a survey and ad hoc methods as in your lemma 2. I follow your argument to get the short list L: 11, 17, 23, 27, 29, but I do not see how to use my argument to finish. In particular, with the short list, how can B eliminate p = 66 = 6.11 and p = 70 = 7.10 as possibilities for the product known to A? Dave rusin also has some concers which I have not as yet had time to think about. It is clear that I need to think harder about the puzzle. Bill P.S. I also mistyped James's e-mail address when I sent my 'solution' last night. When it came back I resent it to the correct address. I believe the address in your e-mail repeats the wrong address. Sorry for the multiple errors. ============================================================================== From: kwong@nwsgpa.ih.lucent.com Subject: Re: A puzzle - again To: nwsgpb!kwong@hoemail2.firewall.lucent.com (kwong) Date: Wed, 11 Sep 2002 11:23:45 -0500 (CDT) Cc: blair@math.niu.edu (Bill Blair), zettl@math.niu.edu (Anton Zettl), rusin@math.niu.edu (Dave Rusin), kong@math.niu.edu (Qingkai Kong), kwong@nwsgpa.ih.lucent.com, jsww@chinnethonkwok.com Bill et al, I have a few minutes to spare this morning. If anyone is still interest, here are some more ideas. It will be interesting to see how high one can push the upper bound beyond u = 50. I did some quick thinking and was convinced that it can at least be pushed to 105. As we have seen, u puts an upper limit on the list L (Bill's notation) via Lemmas 1, 2, and 3. As one increases u, one must increase the value of the prime factor used in Lemma 1 - e.g. if u = 105, then xy cannot have a prime factor >= 53. Then Lemma 2 will have to be modified also to give a larger upper bound to L - in this case, it will be 55. Once we have this, Goldbach's conjecture can be used to eliminate all even numbers in L (here we do not run into the flaw as pointed out in the last email, because L is bounded above by 55, so a decomposition of an even number into 2 primes must have both primes < 105), as well as those of the form 2 + p. So the modified L for this case is now: L: 11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53 and Bill's arguments with the (*)-notation subcases can still be used to eliminate everything from L except the case 17 and the same result holds. So now let's do the reverse engineering (this is a catch phrase I pick up in Lucent). If we want to push u higher, we need to know how far we can eliminate the additional cases added to L. Equivalently, if we look at the ultimate sequence L(inf): 11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53, ... obtained by eliminating all (2+p)-form odd numbers. We want to know which is the smallest term beyond 17 for which there exist only 1 (*)-subcase. Once we know that, we can work backwards to figure out what value of u we need to exclude from L. I haven't found this least term yet - anyone interested in trying? ******************************************************************** Here is another idea that may be useful in searching for this least term. Basically, if we can find 2 (*)-subcase for a term, it can be eliminated. So we can look for sufficient conditions for a (*)-subcase. The following is one such condition and it is merely a restatement of something implicit in all the solutions. More new sufficient condition one can find will help also. - Perhaps feed these into a computer for a speedy serach. Let us denote a general term in L by s (sum). Lemma 4. If s can be written as a sum of a prime p and a power of 2 (>= 4), then s = p + 2^n is a (*) subcase. Proof. If A is given p x 2^n, s/he has more than 1 way of factoring the product. But p x 2^n is the only one that will given a sum allowable in the L choices; any other factorization will give an even sum and we know that L does not contain even numbers. ||| Now armed with Lemma 4, we can eliminate the following cases because each has at least 2 (*)-subcases 11 = 4 + 7 = 8 + 3 23 = 4 + 19 = 16 + 7 27 = 4 + 23 = 8 + 19 ... Not all s can be so eliminated, e.g. 29. But at least the above is applicable to a large number of situations. ******************************************************************** Just another thought, the student C is actually a superfluous red herring. Can one create a more complex problem by requring C to say something that has true implications? I'm happy to be able to take a short break and do something more mind-refreshing. Best wishes, man ============================================================================== Date: Wed, 11 Sep 2002 11:52:05 -0500 (CDT) From: rusin@math.niu.edu To: blair@math.niu.edu, jsww@chinneyhonkwok.com, kong@math.niu.edu, kwong@nwsgpa.ih.lucent.com, richard@math.niu.edu, rusin@math.niu.edu, zettl@math.niu.edu Subject: Re: A puzzle I believe I must disagree with the solutions given so far. I think there is _no solution_ to the problem as posed. It is clear that this is a finite problem with a lot of special cases to consider. I'm lazy, so I used Maple to help. We are to determine the values of two integers. We get successively greater pieces of information which allow us to reduce the number of pairs each time. However, IT SEEMS TO ME THAT NO PAIR OF INTEGERS IS CONSISTENT WITH ALL THE DATA. Here is my reasoning. "Two numbers x and y, 1=0 then if dis=floor(evalf(sqrt(dis)))^2 then if (t-sqrt(dis))>2 and (t+sqrt(dis))<102 then xx:={op(xx), [solve(X^2-t*X+v)]}: fi:fi:fi:od: if nops(xx)=1 then G:={op(G), xx[1]}: fi: od: So! After three statements from the players we have gone from 1225 candidate pairs first to 707 pairs, then 46, then 32. Here is my complaint: among the 32 pairs which remain, there are NO circumstances under which student B can now say, "I know the pair." Student B knows only (i) that the pair is one of these 32 pairs, and (ii) the sum of the pair. The only way B could know the pair now is if there is a sum which occurs only once. But this does not happen. There are five possible sums (11,17,23,27,29) and each occurs multiple times among the 32 remaining possible pairs: Here are the [x,y,x+y,x*y] : [2,9,11,18],[3,8,11,24],[4,7,11,28], [4,13,17,52],[6,11,17,66],[7,10,17,70], [4,19,23,76],[5,18,23,90],[6,17,23,102],[7,16,23,112],[10,13,23,130], [11,12,23,132], [2,25,27,50],[4,23,27,92],[5,22,27,110],[7,20,27,140],[8,19,27,152], [9,18,27,162],[10,17,27,170],[11,16,27,176],[13,14,27,182], [2,27,29,54],[3,26,29,78],[4,25,29,100],[6,23,29,138],[7,22,29,154], [8,21,29,168],[10,19,29,190],[11,18,29,198],[12,17,29,204],[13,16,29,208], [14,15,29,210] So I believe there is NO SOLUTION to the original problem. I have an explanation which I can provide for why {4,13} is NOT a solution but will not include it here for brevity. I would also like to point out that if we keep the same script but change "51" to other numbers "N" then we get a whole sequence of problems. I do not believe it is true that these problems are linearly ordered in the natural way; that is, I think problem N may be resolvable without problems N+1 nor N-1. Maybe I'm missing something obvious; I haven't done the experiments. dave ============================================================================== From: kwong@nwsgpa.ih.lucent.com Subject: Re: A puzzle To: rusin@math.niu.edu Date: Wed, 11 Sep 2002 13:49:14 -0500 (CDT) Cc: blair@math.niu.edu, jsww@chinneyhonkwok.com, kong@math.niu.edu, kwong@nwsgpa.ih.lucent.com, richard@math.niu.edu, zettl@math.niu.edu Dave, I used to use Maple a lot for my work. Too busy today to be even trying to understand your email but I'll try when I have time later. Your findings concur with what Bill found about the 2 remaining cases that cannot be dealt with - and as I remarked in my last email - the original puzzle appears to have an internal contradiction. Can you check with your program what if N is increased to say 90. I believe that (4,13) will then be a solution. If your findings disagree with that, I'd be interested in figuring out what might possibly be wrong with the arguments so far? mk ============================================================================== Date: Wed, 11 Sep 2002 14:51:24 -0500 (CDT) From: rusin@math.niu.edu To: kwong@nwsgpa.ih.lucent.com Subject: Re: A puzzle Cc: blair@math.niu.edu, jsww@chinneyhonkwok.com, kong@math.niu.edu, richard@math.niu.edu, rusin@math.niu.edu, zettl@math.niu.edu > Can you check with your program what if N is increased to say 90 Yes, but I cannot also THINK about it because I have to go to a meeting :-( . Amazingly, it looks to me like if the maximum integer is 90 there IS a unique solution. WHen B reports confidently that A could not have known the answer from the product alone, I believe this means the sum of the two integers is one of {11, 17, 23, 27, 29, 35, 37, 41, 47} When, next, A reports that this information suffices to give him the answer, I compute that there are 74 pairs for which this is true (out of the 120 pairs which have a sum in the indicated set and a product which would have confused A the first time. Of those 74 pairs, the sums can indeed be any of the nine numbers just listed. But all of those sums occur multiplie times, with the exception of 17, which can occur only for the pair {4,13}. So in this case it appears to be true that the problem is completely solvable. I don't see how we would use B's first assertion that he cannot solve the problem, nor C's final conclusion that he can. I will try to revisit this more cleanly later. dave ============================================================================== From: kwong@nwsgpa.ih.lucent.com Subject: Re: A puzzle To: rusin@math.niu.edu Date: Wed, 11 Sep 2002 15:16:38 -0500 (CDT) Cc: kwong@nwsgpa.ih.lucent.com, blair@math.niu.edu, jsww@chinneyhonkwok.com, kong@math.niu.edu, richard@math.niu.edu, zettl@math.niu.edu Dave, Thank you for the new info. I believe that as long as 35 and 37 are allowed in the short list of L and L does not run too long, then (4,13) is a valid solution. Your Maple program can be very helpful in investigating how much further we can still extend the problem. man ============================================================================== Date: Wed, 11 Sep 2002 17:37:50 -0500 (CDT) From: richard@math.niu.edu To: blair@math.niu.edu, kong@math.niu.edu, rusin@math.niu.edu Subject: The ABC problem The Problem: Two numbers x and y, 1 < x, y < 51. A was told the product xy, B was told the sum x+y, and C was told nothing. When asked what x and y are, the following conversation took place: A: I do not know. B: I knew that you would not know, but I do not know either. A: Now I know. B: Now I know. C: Now I know. What are x and y? Solution: Let I = [2, 50] and let "number" mean positive integer. Part I. Let S be the set of all sums for which B can say "I knew that A would not know x and y." Equivalently, S = {n: for every partition a, b in I with n = a+b, there exists a second pair c, d in I with ab = cd} Clearly S is a subset of [4, 100]. It is easier to discover what numbers do not lie in S. (i) Since Goldbach's conjecture has been verified for large bounds, we know that every even number between 4 and 50 can be written as a sum of two primes in I. Clearly, A would be able to uniquely determine x and y when given a product of two primes, such as 21 = 3 x 7. So we can rule out all even numbers up to 50 as members of S. (ii) A can uniquely factor any product of the form pk where p is a prime, 25 < p < 50, and k is any number in I, since any way of factoring pk besides x,y = p,k will result in a factor > 50. The corresponding sum p+k cannot lie in S. Using the smallest prime > 25, p = 29, this argument implies that no integers in the interval [31, 79] lie in S. Using the largest prime < 50, p = 47, we can rule out those integers in the interval [49, 97]. (iii) At the high end of the interval [4,100], it is easy to see that 100, 99, and 98 obviously cannot lie in S. If x+y = 100, then x and y must both be 50, and A could effortlessly determine x and y from the product 2500. If x+y = 99, then x and y are 49 and 50. If x+y = 98, then there are only two possibilities: x=y=49 and x=48, y=50. In both cases A will be able to factor the product xy uniquely. (iv) Using (i), (ii), and (iii) we see that the only candidates for S are the odd integers between 5 and 29, inclusive. We can further restrict these candidates by observing that, as we argued in (i), S cannot contain a number of the form 2+p, where p is a prime in I. This eliminates the odd numbers 5, 7, 9, 13, 15, 19, 21, and 25. One can check that the remaining odd numbers actually satisfy the conditions for membership in S, so S = { 11, 17, 23, 27, 29 }. Part II. When B says "I knew that A did not know x and y," A is able to conclude that the sum of x+y must lie in set S. This additional information will allow him to uniquely determine x and y if, among all factorizations xy = ab, there is only one sum a+b which lies in S. For example, suppose A is given the product xy = 28. Then there are two possible factorizations (ignoring order): (x,y) = (2,14) or (4,7). The sum 2+14 is even and hence does not lie in S, so A must know from B's comment that x and y are 4 and 7, the only choice whose sum is in S. Similarly, if xy = 24, then (x,y) = (2,12), (3,8), or (4,6) and once again A can be certain that x and y are 3 and 8, since the other (even) sums 2+12 and 4+6 do not lie in S. The problem here is that if B has the sum x+y = 11, she cannot deduce from A's comment "Now I know" whether the product given to A is 28 = 4x7 or 24=3x8. Let T = {n: there exists exactly one factorization n=ab, with a,b in I, such that a+b lies in S} In general, if xy = 2^k p, where p is an odd prime in I, and k>0, then xy is in T; the only way to factor xy so that the sum is odd is x=2^k and y=p. A's assertion "Now I know" means that xy is in T. B's assertion "Now I know" means that there is only one parition of her sum n = a+b, with a,b in I, such that the product ab lies in T. B is able to rule out: n = 11 since 4x7 and 8x3 are in T n = 17 since 4x13, 6x11, and 7x10 are in T n = 23 since 4x19 and 16x7 are in T n = 27 since 4x23, 8x19, and 16x11 are in T n = 29 since 16x13 and 12x17 are in T For this last product 12x17, notice that we cannot allow the factorization 4x51 since 51 lies just outside I. For n=17, observe that 66 = 2x33 = 3x22 = 6x11, with only the sum 6+11 lying in S and 70 = 2x35 = 5x14 = 7x10, with only the sum 7+10 lying in S. For each of the five numbers in S, representing the sum x+y given to B, there are at least two different choices for the product xy given to A. Conclusion: The problem, as stated, has no solution. Remarks: 1. I wonder if the problem was posed so that 17 would be the solution, and that the set S was mistakely thought to include the odd numbers 35=2+33 and 37=2+35, arising from the above factorizations of 66 and 70. 2. What could be done to salvage the problem? For example, only one solution xy turns out to be a perfect square. You could also shrink the interval I to [2, 32], I think. How about: The Revised Problem: Two numbers x and y, 1 < x, y < 51. A was told the product xy, B was told the sum x+y, and C was told nothing. When asked what x and y are, the following conversation took place: A: I do not know. B: I knew that you would not know, but I do not know either. A: Now I know. B: I still don't know. Give me a hint. A: Three divides my number. B: Now I know. C: Now I know. What are x and y? ============================================================================== Date: Wed, 11 Sep 2002 18:11:18 -0500 (CDT) From: richard@math.niu.edu To: kwong@nwsgpa.ih.lucent.com Subject: Re: A puzzle Cc: rusin@math.niu.edu Dave and Man, I would think that you could use the interval [2,70], since the largest prime > 70/2 is 37 and so all values past 37+2 would be removed from the list. This is ok, since we do not need to have 41 and 47 in the list. Richard ============================================================================== Date: Wed, 11 Sep 2002 18:25:27 -0500 (CDT) From: richard@math.niu.edu To: rusin@math.niu.edu Subject: Re: A puzzle [2,61] won't work because then 35 will not be on the list. If A is given xy = 124, then he knows it must factor uniquely as 31x4, since 62x2 is not allowed. I suppose you could use the closed interval [2,62]. Richard ============================================================================== Date: Wed, 11 Sep 2002 18:32:41 -0500 (CDT) From: rusin@math.niu.edu To: kwong@nwsgpa.ih.lucent.com Subject: Re: A puzzle Cc: blair@math.niu.edu, jsww@chinneyhonkwok.com, kong@math.niu.edu, richard@math.niu.edu, rusin@math.niu.edu, zettl@math.niu.edu OK, I have looked again at getting Maple to do the heavy lifting for that problem about determining a pair of numbers from sums and products. I am a little surprised people are willing to do this kind of thing by hand; it seems like a lot of special cases to me. Well, chacun a son gout. Here is a somewhat more systematic Maple code to run through the possibilities. We start with all pairs of integers in the interval [2, Z]. Retain only the pairs which stymie player #1 on his first turn. Then retain only the pairs allow player #2 to make his first claim. Then retain only the pairs which allow player #1 to guess correctly on his second turn. Then retain only the pairs which allow player #2 to guess correctly on his second turn. The original problem implied that there would be only pair remaining, so that even player #3 could tell the answer at that point. Here is the result: when the numbers are bounded by Z=13 or less, then there is no way player #2 can even make the claim he made on his first turn! When 13 < Z < 61, there is no way that player #2 can know the answer on his second turn. For 61 <= Z <=120, the unique solution is {4,13}. Running the procedure below in Maple is too slow and boring for larger Z so I don't know whether this pattern continues past Z=120. I believe it would be comparatively easy to try other variants, that is, if we want to vary the responses from the players, or restrict the set of possible integers (or pairs) in some other way, we can probably adapt the Maple code here pretty easily to create a decreasing sequence of sets of pairs, and then check whether the final set contains only a single pair. dave #Two little sorting tricks: byprod:=proc(a,b) if a[1]*a[2]