From: SOURCERER@delphi.com Subject: Problem Sourcerer 1.122 Prove that there are exactly three right-angled triangles whose sides are integers while the area is numerically equal to twice the perimeter. Bruce M. Bowden, aka - Sourcerer@delphi.com From: "M.H. SINGER" Subject: Help needed with a problem I have a problem I have been working on for some time which currently has me stumped as to how to proceed. I would like to enlist the aid of those in this group to see if any further progress is known, or can be made. To wit: If we accept the truth of Fermat's Last Theorem (with or without Professor Wiles) then there is a followup question that must be asked: Given that 2 nth powers cannot sum to another nth power for n>2, what is the minimum number of nth powers that CAN? 3 3 3 3 If n=3, the answer is 3. An example is: 3 + 4 + 5 = 6 and it is easy to find many other examples. If n=4, the answer is also 3, although the smallest known example is anything but easy: 4 4 4 4 95800 + 217519 + 414560 = 422481 If n=5, the best I have so far is an answer of 4, but it is uncertain if there might be a case of 3 terms that just haven't been discovered yet. The 4-term example is: 5 5 5 5 5 27 + 84 + 110 + 133 = 144 Utilizing my computer, I have found examples for n=6 and n=7 which require 15 and 17 terms respectively. I find it hard to believe that these are minimum numbers, but I am at a loss as to how to prove it. Also, has any general research ever been done on this problem? So I have several questions: 1. Is 4 the minimum when n=5? 2. How can I determine minima for larger n? 3. Is there a general algebraic approach that would define the minimum value for each n as a function of n? 4. Is the 'function' non-decreasing? (stepwise increasing) If 4 is true, then this in itself is a proof of Fermat's Last Theorem, since an increasing function can never return to a lower value, in this case 2. So there can't be another case, besides n=2, where 2 nth powers sum to an nth power. I have done other work with this, involving examination of the behavior of the function for non-integral n, and also for negative n. The behavior of the 'function' is very intriguing and I would be happy to share this additional information with anyone interested. Thank you. Mark Singer singerm@cpva.saic.com From: SOURCERER@delphi.com Subject: Problem Sourcerer 2.122 (Problem 2 for January 22, 1994 from Sourcerer to the Internet Amateur Mathematics Society.) If A, B, C, and D are four distinct points such that every circle through A and B intersects, or coincides with, every circle through C and D, prove that the four points are either collinear or concyclic (all on one circle). Bruce M. Bowden Sourcerer@delphi.com Note: solutions to these problems appear attached to new problems a few days after posting. From: "David A. Wagner" Subject: Not-so-hard Number Theory Problem Ok, here's one that shouldn't be too hard for y'all. I give you m and the equation \phi(n) = m. [Here \phi(n) counts the number of positive integers less than n and relatively prime to n.] Give a method to find all n that satisfy the equation. ------------------------------------------------------------------------------- David Wagner dawagner@princeton.edu From: SOURCERER@delphi.com Subject: Problem Sourcerer 1.123 (Problem 1 for January 23, 1994 from Sourcerer to the Internet Amateur Mathematics Society.) Let a, b and c be the lengths of the sides of a triangle, let p = (a + b + c)/2, and let r be the radius of the inscribed circle. Show that 1/(p - a)^2 + 1/(p - b)^2 + 1/(p - c)^2 G.E. 1/r^2. ("^" represents "to the power of" and "G.E." means "is greater than or equal to.") Bruce M. Bowden Sourcerer@delphi.com Note: solutions to these problems appear attached to new problems a few days after posting. From: tulled@rpi.edu (David Michael Tuller) Subject: Sequences Here are a few problems about sequences of my own devising I thought you might enjoy working on. 1) Let {a_n} be a sequence satisfying a_1=1, a_(n+1)=na_n+1. a) Show that lim a_(n+1)/n!=e. b) Determine whether or not a_(n+1)=[n!e] when n>0. ([x] is the greatest integer function.) 2) Let {u_n} be a sequence defined as follows. u_1=1, u_2=2 and u_n when n>2 is the smallest integer which is the sum of two distinct previous numbers in the sequence in a unique way. The sequence is {1,2,3,4,6,8,11,...} a) Show that u_n<=u_(n-1)+u_(n-3) if n>4. b) Show that u_n>=2n-4. c) Show that lim n/u_n<=1/3. David M. Tuller tulled@rpi.edu From: tom@wg.icl.co.uk (Tom Thomson) Subject: Spoiler: Problem Sourcerer 1.122 What a meaningles problem. Let's take a triamgle with sides 12m, 13m, 5m. The perimeter is 30m. The area is 60t, where t is the area of a square whose diagonal is 1m. I can pick any other right triangle and play the same trick. Since area and perimeter are incomensurable, numerical relations between one and the other are completely meaningless and I can claim any triangle I chooe satisfies the relation proposed (so long as it's a right triangle). Even if I have to stick to internationally recognised and well understood units of area and length I will have no problem in exhibiting more than three triangles satisfying the condition: for example, I can choose the triangle whose sides are 3 cm, 4cm , and 5 cm (area 6 cm sq, perimeter 12 cm). Then I can choose the triangle with the same ratios of sides but use m and m sq, or ft and ft sq, or .... and so on ad nauseam. If you want to ask a problem about number theory, couch it in term of number theory; translating it into terms of geometry while you neglect to ensure that you don't inject any dimensional errors is just nonsense. Tom Thomson From: SOURCERER@delphi.com Subject: Problem Sourcerer 1.124 (Problem 1 for January 24, 1994 from Sourcerer to the Internet Amateur Mathematics Society.) Prove that after deleting the perfect squares from the list of positive integers the number found in the nth position is equal to n + [SQRT(n)], where the square brackets, [], are being used to denote "the closest integer." SQRT, of course, is the "square root" function. -------------- Solution to problem 1.122: "Prove that there are exactly three right-angled triangles whose sides are integers while the area is numerically equal to twice the perimeter." All Pythagorean triples can be obtained from x = N * (p^2 - q^2), y = 2 * N * p * q, z = N * (p^2 + q^2) where 0 < q < p, p N.E. q mod 2, and N is any natural number. (N.E. means "not equivalent.") The problem requires that x * y/2 = 2 * (x + y + z), a condition which can be written N^2 * (p^2 - q^2) * (p * q) = 2 * N * (p^2 - q^2 + 2 * p * q + p^2 + q^2), or simply N * (p - q) * q = 4. Since (p - q) is odd, it follows that (p - q) = 1 and the only possibilities for q are 1, 2 and 4. If q = 1, p = 2, N = 4, x = 12, y = 16, z = 20. If q = 2, p = 3, N = 2, x = 10, y = 24, z = 26. If q = 4, p = 5, N = 1, x = 9, y = 40, z = 41. ------------ Note: as in this case, solutions to these problems appear attached to new problems a few days after posting. Bruce M. Bowden Sourcerer@delphi.com From: s.virtes@genie.geis.com Subject: Morephi(n) problems More onphi(n)... > I give you m and the equation > phi(n) = m. > [Herephi(n) counts the number of positive integers less than > n and relatively prime to n.] Give a method to find all n that > satisfy the equation. An interesting problem. phi(n) is "Euler's phi-function", (invented c.1760) which pops up in many strange corners of number theory. I won't give away any of its secrets. Instead, I thought I'd add two "warm-up" problems: 1) When is phi(n) odd? 2) When doesphi(n) divide n? Thanks to David Wagner for mentioning one of my favorites! - s.virtes@genie.geis.com From: SOURCERER@delphi.com Subject: Problem Sourcerer 1.125 (Problem 1 for January 25, 1994 from Sourcerer to the Internet Amateur Mathematics Society.) Prove that among any ten consecutive integers at least one is relatively prime to each of the others. -------------- Solution to problem 2.122: "If A, B, C, and D are four distinct points such that every circle through A and B intersects, or coincides with, every circle through C and D, prove that the four points are either collinear or concyclic (all on one circle)." Start by supposing that A, B, C and D are neither concylic nor collinear. Then p, the perpendicular bisector of segment AB, can't coincide with q, the perpendicular bisector of segment CD. If the lines p and q intersect, their common point is the center of two concentric circles, one through A and B, the other through C and D. If, instead, p and q are parallel, so are the segments AB and CD. Now consider points P and Q, on p and q respectively, midway between the parallel lines AB and CD. It should be obvious that the circles ABP and CDQ have no common point. ------------ Note: as in this case, solutions to these problems appear attached to new problems a few days after posting. ==== Congratulations to Csaba Gabor (csaba@teleport.com) for the correct solution to problem 1.122. :) ==== David G. Radcliffe (radcliff@csd4.csd.uwm.edu) supplied an alternative method to 1.122, which I quote from here: >Start with the equation 2(x+y+z) = xy/2. Rewrite it as >4z = xy - 4x - 4y. Square both sides, and replace z^2 with x^2+y^2. >Cancel, and divide both sides by xy. Some creative factoring leads >to (x-8)(y-8) = 32. The creative factoring proceeds as follows: after dividing both sides by x * y we get x * y - 8 * x - 8 * y + 32 = 0. Add 32 to both sides and factor to get Mr. Radcliffe's result, from which the three unique solutions follow. He also raises the following question: >Have you thought about what happens if you don't have a right triangle? >I found a few solutions: (13,14,15), (33,34,65), and (18,289,305). >I don't know if there is a general solution, or if the number of >solutions is finite. A good question. In the case of a general triangle, the problem becomes 2 * (x + y + z) = SQRT(s * (s - x) * (s - y) * (s - z)), where the right side is Heron's formula for triangular areas, with s = (x + y + z) / 2. Squaring and simplifying leads to 64 * (x + y + z) + (x - y - z) * (x - y + z) * (x + y - z) = 0. Can a generating formula be developed from this? ==== Tom Thomson (tom@wg.icl.co.uk) responded to 1.122 by arguing that if area is defined in a non-standard way, as in what might be called "diagonal units" (the unit square is redefined by a unit on the diagonal rather than the side), it becomes possible to produce any number of solutions. His reply raises an interesting ontological point contrasting reality and formal representations of reality. It never hurts to take a closer look at the philosophical basis of what we do, and, it seems to me, that kind of examination has a place here too. :) ==== Bruce M. Bowden Sourcerer@delphi.com From: a_rubin@dsg4.dse.beckman.com (arthur rubin) Subject: Problem Sourcerer 1.122 revisited >>:David G. Radcliffe (radcliff@csd4.csd.uwm.edu) >:Bruce M. Bowden (Sourcerer@delphi.com) >>Have you thought about what happens if you don't have a right triangle? >>I found a few solutions: (13,14,15), (33,34,65), and (18,289,305). >>I don't know if there is a general solution, or if the number of >>solutions is finite. >A good question. In the case of a general triangle, the problem becomes > 2 * (x + y + z) = SQRT(s * (s - x) * (s - y) * (s - z)), >where the right side is Heron's formula for triangular areas, with >s = (x + y + z) / 2. Squaring and simplifying leads to > 64 * (x + y + z) + (x - y - z) * (x - y + z) * (x + y - z) = 0. Writing x1 = s - x, y1 = s - y, z1 = s - z, and further simplifying, we get 16 (x1 + y1 + z1) = x1 y1 z1 By using methods similar to David's trick, we can solve this to get the complete solution: (x1,y1,z1) = (1,17,288),(1,18,152),(1,20,84),(1,24,50),(1,32,33),(2,9,88), (2,10,48),(2,12,28),(2,13,24),(2,16,18),(3,6,72),(3,7,32), (3,8,22),(3,12,12),(4,5,36),(4,6,20),(4,8,12),(6,7,8), and (x,y,z) = (9,40,41)*,(9,75,78),(10,24,26)*,(10,35,39),(11,25,30),(11,90,97), (12,16,20)*,(12,50,58),(13,14,15),(14,30,40),(15,15,24),(15,26,37), (18,20,34),(18,289,305),(19,153,170),(21,85,104),(25,51,74), (33,34,65), with * indicating a right triangle. From: csaba@teleport.com (Csaba Gabor) Subject: Integer sided triangles We know that all pythagorean triples are generated by: (k(b^2 - a^2), 2kab, k(b^2 + a^2)) I would like to know if there is some way to generate all integer sided traingles. Thanx, Csaba From: "Jonathan Wildstrom" <95JWILDSTROM@vax.mbhs.edu> Subject: Re: Integer sided triangles > We know that all pythagorean triples are generated by: > > (k(b^2 - a^2), 2kab, k(b^2 + a^2)) > > I would like to know if there is some way to >generate all integer sided traingles. Thanx, > Csaba If by "integer sided triangles" you mean triangles with all sides being integral, then there are an infinite number of "integer sided triangles." You can just pick any three numbers a, b, and c, such that a We know that all pythagorean triples are generated by: > > (k(b^2 - a^2), 2kab, k(b^2 + a^2)) > > I would like to know if there is some way to > generate all integer sided traingles. Thanx, > Csaba > From: SOURCERER@delphi.com Subject: Problem Sourcerer 1.126 (Problem 1 for January 26, 1994 from Sourcerer to the Internet Amateur Mathematics Society.) A familiar riddle states that a man walks one mile south, one mile east and one mile north to arrive back where he started. He sees a bear. The riddle then goes on to ask what color the bear is. The answer, of course, is "white," because the man must have started at the North Pole. But did he have to start at the North Pole to follow the south, east, and north path, each leg a mile in length, to reach his starting point (and encounter a white bear)? If not, give alternative solutions. ;) -------------- Solution to problem 1.123: "Let a, b and c be the lengths of the sides of a triangle, let p = (a + b + c)/2, and let r be the radius of the inscribed circle. Show that 1/(p - a)^2 + 1/(p - b)^2 + 1/(p - c)^2 G.E. 1/r^2." This problem was first solved by David G. Radcliffe (radcliff@csd4.csd.uwm.edu) on the same day it was released. I quote his solution here: >Let x,y,z be positive numbers. Then x/y + y/x >= 2, (*) so > > x(y/z + z/y) + y(x/z + z/x) + z(x/y + y/x) >= 2(x + y + z). > >Expand the left side and divide by 2xyz, giving > > 1/x^2 + 1/y^2 + 1/z^2 >= (x + y + z)/(xyz). > >Let x=p-a, y=p-b, and z=p-c. Note that x + y + z = p. We now have > > 1/(p-a)^2 + 1/(p-b)^2 + 1/(p-c)^2 >= p/(xyz). > >The proof will be complete if we can show that xyz = pr^2. >Draw line segments from the center of the inscribed circle >to each vertex, dividing the triangle into three smaller >triangles. The area of these triangles are ar/2, br/2, and cr/2, >so the area of the big triangle is pr. > >But by Heron's formula, the area of the triangle is the >square root of p(p-a)(p-b)(p-c). Consequently, > (pr)^2 = p(p-a)(p-b)(p-c) = pxyz, > >so xyz = pr^2, as required. > >--- >(*) Proof that x/y + y/x >= 2: > > (x - y)^2 >= 0 > x^2 - 2xy + y^2 >= 0 > x^2 + y^2 >= 2xy > (x^2 + y^2)/xy >= 2 > x/y + y/x >= 2 . ==== Csaba Gabor (csaba@teleport.com) used a different approach to 1.123 using the Lagrangian multiplier method: > If p1, p2, p3 denote the sides of a triangle, and r its inradius, >show that with s = p1 + p2 + p3 that: > > 1/(s-p1)^2 + 1/(s-p2)^2 + 1/(s-p3)^2 - 1/r^2 >= 0 > >Solution: > Warning. This solution is practically obscene. It is not >intuitive, nor geometric, nor elementary, nor does it shed any >light whatsoever on the intrinsic nature of the problem. >Nevertheless, it has the two redeeming features of solving the >problem and being relatively short. To work: > > Important (geometric) note: > rs = A (trivial to show by drawing the 3 relevant radii) > A^2 = s(s-p1)(s-p2)(s-p3) (Hero's formula - messier to show) > > Define (our function above): > f(p1,p2,p3,s) = Sum(i = 1 to 3 of 1/(s-pi)^2)) - (s/A)^2 > > Now we find the minimum of f subject to 2s = p1 + p2 + p3 using > (gasp) Lagrangian multipliers. We will let L be our lambda. > > So we wish to minimize: > f - L(p1 + p2 + p3 - 2s) > > Take partials with respect to pi (and set to 0): >(1) Df/Dpi = 2/(s-pi)^3 - s^2/((s-pi)A^2) - L = 0 > Now we do what we always do when we are at this stage in solving > a problem with Lagrangian multipliers: we cross multiply by some > factor to return our equation to some semblance of the original. >(2) 2/(s-pi)^2 - 1/r^2 = L(s-pi) > Now we do what we always do when we are at this stage in solving > a problem with Lagrangian multipliers: we sum over all the equations > from each pi: >(3) 2f + 2/r^2 - 3/r^2 = L(3s - p1 - p2 - p3) > or >(4) 2f = 1/r^2 + Ls > It must be emphasized that this f the is value of f(p1,p2,p3,s) at > its minimum. Since all we want to do is show that it is greater > than or equal to 0, it would be sufficient to simplify the right > hand side. > > Here we recall that we still have one variable left. Let's take > partials with respect to s: >(5) Df/Ds = Sum(i=1 to 3 of (-2/(s-pi)^3)) - 1/sr^2 > - 1/r^2 (Sum(i = 1 to 3 of 1/(s-pi))) + 2L = 0 > Now we do what we always do when we are at this stage in solving > a problem with Lagrangian multipliers: we hope. We hope that > somewhere we can notice something to simplify our ugly equation. > We are fortunate. Using (1) we see that our two summations in (5) > simplify to -3L. Hence, >(6) -1/sr^2 = L > which we plug in to (4) to yield f=0 at its minimum. > > QED ==== Note: as in this case, solutions to these problems appear attached to new problems a few days after posting. Bruce M. Bowden Sourcerer@delphi.com From: Ariel Scolnicov Subject: Re: Problem Sourcerer 1.126 > (Problem 1 for January 26, 1994 from Sourcerer to the Internet > Amateur Mathematics Society.) > > A familiar riddle states that a man walks one mile south, one mile > east and one mile north to arrive back where he started. He sees a > bear. The riddle then goes on to ask what color the bear is. The > answer, of course, is "white," because the man must have started at > the North Pole. But did he have to start at the North Pole to follow > the south, east, and north path, each leg a mile in length, to reach > his starting point (and encounter a white bear)? If not, give > alternative solutions. ;) > [...] > Note: as in this case, solutions to these problems appear attached > to new problems a few days after posting. > > Bruce M. Bowden > Sourcerer@delphi.com > There is an infinite set of latitudes satisfying the condition: pick any point 1 mile north of a line of latitude the length of which is 1/n miles, for some (integer) n. Going south one mile we reach the line; 1 mile east takes us n times around it; going one mile north we reach our original position. Literally speaking, the above isn't a solution (no bears in Antarctica). However, we could consider a certain swimming bird instead. Ariel Scolnicov From: SOURCERER@delphi.com Subject: Problem Sourcerer 2.126 (Problem 2 for January 26, 1994 from Sourcerer to the Internet Amateur Mathematics Society.) Consider polynomials of the form A * x^2 - B * x + C with integer coefficients which have two distinct zeros in the open interval 0 < x < 1. Can you give the least positive integer value of A for which such a polynomial exists, supplying a proof? -------------- Solutions to these problems appear attached to new problems a few days after posting. Bruce M. Bowden Sourcerer@delphi.com From: SOURCERER@delphi.com Subject: Problem Sourcerer 1.127 (Problem 1 for January 27, 1994 from Sourcerer to the Internet Amateur Mathematics Society.) Let (ABCDEF) be a hexagon inscribed in a circle of radius r. Show that if segment AB = segment CD = segment EF = r, then the midpoints of segments BC, DE and FA are the vertices of an equilateral triangle. -------------- Solution to problem 1.124: "Prove that after deleting the perfect squares from the list of positive integers the number found in the nth position is equal to n + [SQRT(n)], where the square brackets, [], are being used to denote 'the closest integer.' SQRT, of course, is the 'square root' function." In proving by induction, it's sufficient to show that the difference n + [SQRT(n)] - (n - 1 + [SQRT(n-1)]) = 1 or 2, with the value of 2 arising IFF the number n + [SQRT(n-1)] is a perfect square. Let's let q represent [SQRT(n-1)]. It should be clear that q - 1/2 < SQRT(n-1) < q + 1/2 or, restated, q^2 - q + 1/4 < n - 1 < q^2 + q + 1/4. This gives q^2 + 5/4 < n + [SQRT(n-1)] < (q + 1)^2 + 1/4. So n + [SQRT(n-1)] is a perfect square IFF n = (q + 1)^2 - q. However, then and only then SQRT(n) > q + 1/2 > SQRT(n-1). In other words then and only then [SQRT(n)] - [SQRT(n-1)] = 1, because this difference is never greater than 1. ==== David G. Radcliffe (radcliff@csd4.csd.uwm.edu) noted that the solution to this problem can be found in Ross Honsberger's "Ingenuity in Mathematics," p. 97, which he recommends as "a great book." :) ==== OMNI Books will soon be releasing MATHOPEDIA: THE OMNI GUIDE TO MATH FOR EVERYONE by Ed Ferrell. I've seen two chapters in "sampler" format; as the title might suggest, this is an introductory tome, popularly written. You -will- find some history of the subject in it, though, and if you're often trying to convince non-mathematical members of your circle that math can be interesting, it might be worth chacking out as a gift. ==== Note: as in this case, solutions to these problems appear attached to new problems a few days after posting. Bruce M. Bowden Sourcerer@delphi.com From: SOURCERER@delphi.com Subject: Problem Sourcerer 1.128 (Problem 1 for January 28, 1994 from Sourcerer to the Internet Amateur Mathematics Society.) Quickies: A) Find a number base other than 10 in which 121 is a perfect square. B) An anthropologist comes to fork in the road. He's been told beforehand that the fork will lead to a tribe of truth-tellers in one direction and a tribe of liars in the other direction. Both tribes were, in fact, a single tribe once, but they didn't get along. They -do-, however, share a common language and manner of dress. Unfortunately, the anthroplogist, while having seen pictures of these folk, had to prepare for his trip so hurredly that he only learned the words equivalent to "yes" and "no" from the tribes' common language and promptly forgot which was which. He only recalls that one of the words was "iams" and the other was "smai." At the fork stands a native, obviously (by dress and bearing) from one of the tribes, who might be prevailed upon to direct the anthropologist to the village of his choice. The native however, seems in a hurry to leave and will obviously (for this is a very perceptive anthropologist) answer only one question and is not given to gesticulation. "Fortunate," the anthropologist thinks to himself, "that these natives know -my- language, at least!" Now, given the conditions above, what one question might the anthropologist ask of the native, not knowing which of "iams" and "smai" mean "yes" and which means "no," to find his way to where he's going? -------------- Solution to problem 1.125: "Prove that among any ten consecutive integers at least one is relatively prime to each of the others." Any common factor of two of these numbers would have to be divisible by 2, 3, 5 or 7. It's enough to prove that among any ten consecutive integers there's at least one not divisible by 2, 3, 5 or 7. We'll arrive at such an integer by elimination: Remove those divisible by 3; there may be either 3 or 4 of them. Among these is either at least one or two which are divisible also by 2. Removing all those divisible by 2 we'll have eliminated, at most, seven of the integers. In doing this, we've also stricken off at least one number divisible by five. we're left with three integers only two of which can be divisible by 5 or 7. The remaining integer is what we seek. ==== Csaba Gabor (csaba@teleport.com) and Arthur Rubin (a_rubin@dsg4.dse.beckman.com) used essentially the same reasoning. ==== David W. Wilson (wilson@express.ctron.com) took a more involved approach. I quote from his email here: >Let S be a set of 10 consecutive integers at n. In S, there are 5 >even numbers. Of the remaining odd integers in S, at most 2 are >divisible by 3, exactly 1 is divisible by 5, and at most 1 is >divisible by 7. This makes a total of at most 9 integers in S >which are divisible by 2, 3, 5, or 7. But S contains 10 integers, >so at least one of them is indivisible by 2, 3, 5, or 7. Let a >be this integer. > >Let b be any integer in S distinct from a. Because a ~= 0, we have >(a, b) >= 1. Now, > > (a, b) = (a, b-a) = (a, |b-a|) = (a, |a-b|) > >so that 1 <= (a, b) <= |a-b|. Since a and b are both in S, we have >|a-b| <= 9, giving > > 1 <= (a, b) <= 9 > >Since none of 2, 3, 5, or 7 divide a, none of them divide (a, b). >In light of the last inequality, therefore, (a, b) = 1. > >Thus a is in S and is relatively prime to any distinct b in S, as >was to be shown. ==== Note: as in this case, solutions to these problems appear attached to new problems a few days after posting. Bruce M. Bowden Sourcerer@delphi.com From: David G Radcliffe Subject: Re: Problem Sourcerer 1.125 + survey results SOURCERER@delphi.com wrote: > Prove that among any ten consecutive integers at least one is > relatively prime to each of the others. Is it true in general that in any list of consecutive integers, at least one is relatively prime to each of the others? (I don't know the answer to this.) Some old business: A week ago, I asked the list for your favorite elementary math books and journals. Unfortunately, I had only four responses. Two people recommended a journal called Quantum (call 1-800-SPRINGER for subscriptions). The other suggestions were: Aha! Insight / Martin Gardner Applied Numerical Methods / Carnahan, Luther, Wilkes The VNR Concise Encyclopedia Of Mathematics / Kastner, Kustner, etc. Editors, Van Nostrand Reinhold Publishing Personally, I would recommend anything by Martin Gardner or Ross Honsberger. I also liked "The Shape of Space" by Jeffrey Weeks. Thanks to everbody who replied! Dave From: SOURCERER@delphi.com Subject: Problem Sourcerer 1.129 (Problem 1 for January 29, 1994 from Sourcerer to the Internet Amateur Mathematics Society.) Let f(x,y) be a polynomial with real coefficients in the real variables x and y defined over the entire x-y plane. What are the possibilities for the range of f(x,y)? -------------- Solution to problem 1.126: "A familiar riddle states that a man walks one mile south, one mile east and one mile north to arrive back where he started. He sees a bear. The riddle then goes on to ask what color the bear is. The answer, of course, is "white," because the man must have started at the North Pole. But did he have to start at the North Pole to follow the south, east, and north path, each leg a mile in length, to reach his starting point (and encounter a white bear)? If not, give alternative solutions. ;)" The simple answer is "yes, he -would- have to start at the North Pole" if you consider the white bear (hence a starting point near the North Pole). In order for the solution to be otherwise, the man would have to start a mile north of a parallel of latitude which satisfied the condition n * circumference = 1, or n * 2 * pi * r * cos(a) = 1, where 'n' is a natural number (the number of times around the pole, in fact), 'pi' is the area of a unit circle, 'r' is the radius of the earth in miles (about 3959), and 'a' is the angle of north latitude. The furthest south this circle can be is where the circumference is precisely one mile, hence n=1. Solving this, a is about equal to 1.570756 radians, or 89 degrees, 59 minutes, 51.7 seconds. An additional mile north of that would be 1/r radians or about 52 seconds of arc. That would put us nearly 44 seconds of arc over the pole. So the northern hemisphere offers only one solution. If the white bear is excluded from the problem, however, there are an infinite number of solutions in the southern hemisphere. Proceed in the same manner as above to determine a latitude satisfying the condition as given, with 'a' now southern. Again, the furthest north this circle can be is where the circumference is precisely one mile, hence n=1. The solution is about equal to 1.570756 radians south, or 89 degrees, 59 minutes, 51.7 seconds. An additional mile north of that would be 1/r radians or about 52 seconds of arc. Hence, the furthest starting point north is at about acos(1/(2 * pi * 3959)) - 1/3959 = 1.5705035 radians south, or 89 degrees, 58 minutes, 59.61 seconds southern latitude... about 1.159 miles from the pole. The set of solutions occupies the infinity of points from this latitude to 840 feet further south, each additional latitude being a solution using values for n from 2 upward. ==== Ariel Scolnicov (ariels@CS.HUJI.AC.IL) and Alexander Volokh (of the Competitive Enterprise Institute) both sent back descriptive solutions of far fewer words. :D ==== Note: as in this case, solutions to these problems appear attached to new problems a few days after posting. Bruce M. Bowden Sourcerer@delphi.com From: SOURCERER@delphi.com Subject: Problem Sourcerer 2.129 (Problem 2 for January 29, 1994 from Sourcerer to the Internet Amateur Mathematics Society.) - Triangles Again - A line segment AB, with midpoint M, has length a. A point X is randomly chosen interior to the segment. What is the probability that segments AX, BX, and AM can be the sides of a triangle? -------------- Note: solutions to these problems appear attached to new problems a few days after posting. Bruce M. Bowden Sourcerer@delphi.com From: csaba@teleport.com (Csaba Gabor) Subject: Re: Problem Sourcerer 2.129 Problem: A line segment AB, with midpoint M, has length a. A point X is randomly chosen interior to the segment. What is the probability that segments AX, BX, and AM can be the sides of a triangle? Solution: The probability is one half. If x is the smaller of AX, BX then we must have x + a/2 > a - x => x > a/4. The triangle forming region is half of AB, centered at M. Csaba From: SOURCERER@delphi.com Subject: Problem Sourcerer 1.130 (Problem 1 for January 30, 1994 from Sourcerer to the Internet Amateur Mathematics Society.) Two circles are concentric. A chord of the outer circle runs tangent to the inner circle and is two meters in length. What's the area of the region between the two circles? -------------- Solution to problem 2.126: "Consider polynomials of the form A * x^2 - B * x + C with integer coefficients which have two distinct zeros in the open interval 0 < x < 1. Can you give the least positive integer value of A for which such a polynomial exists, supplying a proof?" Let f(x) = A * x^2 - B * x + C = A * (x - r) * (x - s). Then f(0) * f(1) = A^2 * r * (r - 1) * s * (s - 1). The graph of r * (r - 1) shows that 0 < r < 1 implies 0 < r * (r - 1) is less than or equal to 1/4, with equality IFF r = 1/2. Similarly, 0 < s * (s - 1) is less than or equal to 1/4. Since r is not equal to s, r * (r - 1) * s * (s - 1) < 1/16 and 0 < f(0) * f(1) < A^2/16. The coefficients A, B and C are integers and thus 1 is less than or equal to f(0) * f(1). Consequently, A^2 > 16; that is, A is greater than or equal to 5. The discriminant B^2 - 4 * A * C shows that the minimum possible value for B is 5. Furthermore, 5 * x^2 - 5 * x + 1 has two distinct roots between 0 and 1. ==== The Polar Bear Problem Revisited In email dated January 29th, David Radcliffe (radcliff@csd4.csd.uwm.edu) writes: >This may be nitpicking, but there aren't any bears at the >North Pole either. They don't wander that far north. >After all, what would they eat? Maybe this is why some folks prefer -pure-, as opposed to -applied-, mathematics. :D ==== Note: as in this case, solutions to these problems appear attached to new problems a few days after posting. Bruce M. Bowden Sourcerer@delphi.com From: SOURCERER@delphi.com Subject: Problem Sourcerer 2.130 (Problem 2 for January 30, 1994 from Sourcerer to the Internet Amateur Mathematics Society.) Let Dn be the determinant of order n of which the element in the ith row and the jth column is the absolute value of the difference of i and j. Show that Dn is equal to (-1)^(n-1) * (n-1) * 2^(n-2). -------------- Note: solutions to these problems appear attached to new problems a few days after posting. Bruce M. Bowden Sourcerer@delphi.com From: TKIDD@CLEMSON.CLEMSON.EDU Subject: Sum of squares... Suppose x and y are coprime and of opposite parity. It looks to me (having used small values of x and y) like x^2 + y^2 is either 1) divisible by 5, or 2) prime. Furthermore, after dividing x^2 + y^2 by 5 as many times as possible, the result may be expressed as the sum of two squares. Also, 5(x^2 + y^2) may be expressed as the sum of two squares. Is there any proof of this (true or false)?? -Travis From: tulled@rpi.edu (David Michael Tuller) Subject: Re: Sum of squares... On Jan 30, 12:30pm, TKIDD@CLEMSON.CLEMSON.EDU wrote: > Subject: Sum of squares... > Suppose x and y are coprime and of opposite parity. > It looks to me (having used small values of x and y) like > x^2 + y^2 is either 1) divisible by 5, or 2) prime. > > Furthermore, after dividing x^2 + y^2 by 5 as many times as > possible, the result may be expressed as the sum of two squares. > > Also, 5(x^2 + y^2) may be expressed as the sum of two squares. > > Is there any proof of this (true or false)?? >-- End of excerpt from TKIDD@CLEMSON.CLEMSON.EDU (a^2+b^2)(c^2+d^2)=(ac)^2+(ad)^2+(bc)^2+(bd)^2=(ac)^2+(bd)^2+2abcd-2abcd+ (ad)^2+(bc)^2=(ac+bd)^2+(ad-bc)^2. 13=2^2+3^2, 17=1^2+4^2 so 13*17=14^2+5^2 which is a counterexample to your conjecture. There are (I believe) infinitely many counterexamples because every prime of the form 4k+1 is the sum of two squares. David M. Tuller tulled@rpi.edu From: SOURCERER@delphi.com Subject: Problem Sourcerer 1.131 (Problem 1 for January 31, 1994 from Sourcerer to the Internet Amateur Mathematics Society.) CBers Two Citizen Band radio operators, Tiger Lil and Huge Huey, work for Carl's Trucking. The range of their CB radios is 25 km. Tiger Lil is traveling toward the base from the east and at 3:00 PM is somewhere within 30 km of the base. Huge Huey is traveling toward the base from the north and at 3:00 PM is somewhere within 40 km of the base. What's the probability that they can communicate with each other at 3:00 PM? -------------- Solution to problem 1.127: "Let (ABCDEF) be a hexagon inscribed in a circle of radius r. Show that if segment AB = segment CD = segment EF = r, then the midpoints of segments BC, DE and FA are the vertices of an equilateral triangle." Place the figure in the complex plane with the center of the circle at the origin. We can take A, B, C, D, E and F as complex numbers of absolute value r. Furthermore, B = A * z, D = C * z, and F = E * z, where z = cos(pi/3) + i * sin(pi/3). Since z^3 = -1 and z N.E. 1, z^2 - z + 1 = 0. The midpoints of segments BC, DE and FA are P = (A * z + C)/2, Q = (C * z + E)/2, and R = (E * z + A)/2. If the segment from Q to R is rotated through pi/3 about Q, then R is carried into Q + z * (R - Q), which equals P. Thus, P, Q and R are vertices of an equilateral triangle. (Here, pi is the area of the unit circle, i is the imaginary root, and N.E. means "not equal to.") ==== Note: as in this case, solutions to these problems appear attached to new problems a few days after posting. Bruce M. Bowden Sourcerer@delphi.com From: Kermit Rose Subject: Roman numeral arithmetick How to find square root in Roman Numerals: We will use the following table of three columns. column i column ii column iii row i i ii iii row ii iiii viii xii row iii xvi xxxii xxxxviii row iiii lxiiii cxxviii clxxxxii row v cclvi dxii dcclxviii row vi mxxiiii mmxxxxviii mmmlxxii row vii mmmmlxxxxvi etc. As preliminary, establish four columns for accumulator, dividend,answer and row. Put the number whose square root is to be found in the accumulator column. Find the row number of the largest entry in the table shich is less than or equal to this accumulator value. Enter this row number in the row column. Step1. If the accumulator is not null, find the largest number in the table less than or equal to the accumulator value. If its row number is the same as the number in the row column, subtract the table entry from the accumulator value, and put the difference in the accumulator column. Step ii. If the row column is null, then answer column now contains square root. Otherwise, subtract one from row column and put difference back in row column. Step iii. If there is a number in the dividend column, multiply it by four and put the product in the dividend column. Step iiii. If, in step i, the row numbers matched, add to the dividend value the column number corresponding to the table entry of step i. (If the dividend value is null, just place the number to be added in the dividend column.) step v. If the answer column value is not null, double it. Step vi. Calculate twice the answer column. Do not change the answer column entry. If the calculated number is greater than or equal to the number in the dividend column, skip the next two steps. Otherwise, do the next two steps. (If the answer column is null, do the next two steps.) Step vii. Add one to the answer column. Put the new value in the answer column. (If the answer column is null, put 1 in the answer column.) Step viii. Subtract answer column from dividend column. Put difference in dividend column. Step viiii. repeat step i through step viii until final answer is found. (see step ii.) Example: Find the square root of mmmmc Accumulator dividend answer row mmmmc vii iiii i i vi null ii v iiii iiii viii iii null ii i xvi i iiii xxxii null lxiiii answer is lxiiii. From: Kermit Rose Subject: physics length expansion formula. The formula is given in elementary physics text that the new length of a bar, L1 when heated from temperature t0 to temperature t1 is given by L1 = L0 + b L0 (t1 - t0) where L0 is the length at temperature t0, and b is the constant coefficient of expansion. Prove that this formula is false. Ie. It is logically self-contradictory. Answer: Consider a bar being heated from temperature to to t1, then further heated from temperature t1 to t2. This is equivalent to the bar being heated from temperature t0 to t2. Thus (L1 - L0) + (L2 - L1) = L2 - L0 b L0(t1 - t0) + b L1(t2 - t1) = b L0(t2 - t0) L0 (t1 - t0) + L1 (t2 - t1) = L0 (t2 - t0) L1 = L0 + b L0 (t1 - t0) L0 (t1 - t0) + [ L0 + b L0 (t1 -t0) ] (t2 - t1) = L0 (t2 - t0) (t1 - t0) + [1 + b (t1 - t0) ] (t2 - t1) = (t2 - t0) [ 1 + b(t1-t0) ] (t2 - t1) = (t2 - t0) - (t1 - t0) [1 + b(t1-t0) ] (t2 - t1) = t2 - t1 1 + b(t1-t0) = 1 b(t1-t0) = 0 This is impossible since b is not zero and t1 > t0. The consistent formula would be L1 - L0 = L0 (t1 - t0)/(1+bt) where t is measured on the kelvin scale. From: Kermit Rose Subject: sum neg powers infinity infinity Prove that sum sum n^(-m) = 1. n=2 m=2 sum sum n^(-m) = sum sum [ n^(-2)]/[n^(m-2)] = sum n^(-2) sum n^(2-m) = sum n(-2) /(1 - 1/n) = sum 1/(n^2 - n) = sum 1/[n(n-1) ] = sum [n - (n-1)]/[n(n-1)] = sum [ 1/(n-1) - 1/n] = 1/(2 - 1) = 1 From: Kermit Rose Subject: harmonic sum to unity If P>0 and q>0 then the following are equivalent. 1/p + 1/q = 1 p + q = pq (p-1)(q-1) = 1 p = q/(q-1) q = p/(p-1) p/q = p - 1 q/p = q - 1 (p-1)/(q-1) = p^2 /q^2 p/q - q/p = p - q = 1/(q-1) - 1/(p-1) 1/(p-1) + 1/(q-1) = (p-1) + (q-1) From: "David A. Wagner" Subject: Re: Sum of squares... > > Suppose x and y are coprime and of opposite parity. > It looks to me (having used small values of x and y) like > x^2 + y^2 is either 1) divisible by 5, or 2) prime. > How about 5^2 + 12^2 = 169 = 13^2 as a counterexample? > > Furthermore, after dividing x^2 + y^2 by 5 as many times as > possible, the result may be expressed as the sum of two squares. > > Also, 5(x^2 + y^2) may be expressed as the sum of two squares. > Yes, this is true, and it follows from a theorem of Fermat. He proved that a prime p can be written as a sum of two squares iff p=1(mod 4). Thus 5=1^2+2^2, 13=2^2+3^2, 17=1^+4^2, 29=2^+5^2, ... Next there is a lemma that if you take any two numbers that can be written as the sum of two squares and multiply them together, the result can be written as a sum of two squares. The lemma takes the form of (a^2+b^2)(c^2+d^2) = (ac-bd)^2 + (ab+cd)^2. So factoring x^2+y^2 can only yield primes of the form 4k+1, and vice versa - multiplying any number of primes of the form 4k+1 yields a number which can be written as the sum of two squares. If I remember correctly, this was in my algebra book by Herstein, and also is in several introductory number theory books. Nifty question! Interested in a followup? Let me define a function f as follows: if you give me a positive integer m, I'll first find the m-th prime that is congruent to 1 (mod 4). [This sequence of primes starts off as 5, 13, 17, 29, ...] Call the prime p_m. Next I'll decompose into a sum of two squares, writing p_m=a_m^2 + b_m^2. Now define f(m)=a_m + b_m. Experimentally, it looks like the sequence f(1), f(2), ... begins 3, 5, 5, 7, 7, 9, 9, 11, 11, 13, ... Does the pattern continue; and if so, can you tell me why? ------------------------------------------------------------------------------- David Wagner dawagner@princeton.edu From: Ariel Scolnicov Subject: 1/p + 1/q = 1 [Re: harmonic sum to unity] When 1/p+1/q = 1, we have the following generalisation of the Cauchy-Schwarz (sp?) inequality, termed Ho"lder's inequality: sum (a_i * b_i) <= (sum a_i^p)^(1/p) * (sum b_i^q)^(1/q) where a_i, b_i are nonnegative reals (as are p, q). Substituting p=q=2 yields Cauchy-Schwarz; unfortunately this generally gives a large RHS, so it doesn't help when proving. It is possible to prove this fairly directly by normalising the a's and the b's, then differentiating with respect to a_n and looking for extrema; this is not recommended. If anybody's interested I could find a rather neat proof (mainly based on the concavity of the log function). Ariel Scolnicov. From: Kermit Rose Subject: 24th roots of unity. List the eight primitive 24th roots of unity. Answer. (sqrt(6) + sqrt(2) )/4 + i (sqrt(6) - sqrt(2) )/4 (sqrt(6) - sqrt(2) )/4 + i (sqrt(6) + sqrt(2) )/4 -(sqrt(6) - sqrt(2) )/4 + i (sqrt(6) + sqrt(2) )/4 -(sqrt(6) + sqrt(2) )/4 + i (sqrt(6) - sqrt(2) )/4 -(sqrt(6) + sqrt(2) )/4 - i (sqrt(6) - sqrt(2) )/4 -(sqrt(6) - sqrt(2) )/4 - i (sqrt(6) + sqrt(2) )/4 (sqrt(6) - sqrt(2) )/4 - i (sqrt(6) + sqrt(2) )/4 (sqrt(6) + sqrt(2) )/4 - i (sqrt(6) - sqrt(2) )/4 From: Kermit Rose Subject: tenth roots of unity. List the eight primitive 10th roots of unity. Answer. ( 1+sqrt(5))/4 + i sqrt(10-2 sqrt(5))/4 (-1+sqrt(5))/4 + i sqrt(10+2 sqrt(5))/4 -(-1+sqrt(5))/4 + i sqrt(10+2 sqrt(5))/4 -( 1+sqrt(5))/4 + i sqrt(10-2 sqrt(5))/4 -( 1+sqrt(5))/4 - i sqrt(10-2 sqrt(5))/4 -(-1+sqrt(5))/4 - i sqrt(10+2 sqrt(5))/4 (-1+sqrt(5))/4 - i sqrt(10+2 sqrt(5))/4 ( 1+sqrt(5))/4 - i sqrt(10-2 sqrt(5))/4 From: TKIDD@CLEMSON.CLEMSON.EDU Subject: 1/p + 1/q = 1??? Isn't that just the same thing as saying p + q = pq ???? If so, then we have p = pq - q or p = q(p-1). Therefore, p/(p-1) = q. So 1 + 1/(p-1) = q, so 1/(p-1) = q-1. So all you gotta do is take any two numbers which are reciprocals of each other, add 1 to each of them, and you have two numbers whose reciprocals add to 1. -Travis From: Kermit Rose Subject: spoof of mathematics On the nature of mathematical proofs. By Joel Cohen Department of Mathematics Harvard University Cambridge 38, Massachusetts (Long ago and in a previous generation.) Bertrand Russell has defined mathematics as the science in which we never know what we are talking about or whether what we are saying is true. Mathematics has been shown to apply widely in many other scientific fields. Hence most other scientists do not know what they are talking about or whether what they are saying is true. Thus providing a rigorous basis for philosophical insights is one of the main functions of mathematical proofs. Aristotle was among the first philosophers to study mathematical proofs. He invented the sillygism, a device which, because of its absolute uselessness, has interested countless philosophers and logicians. Briefly, by means of a sillygism, one infers a conclusion from a major and minor premise. In fact, logicians are always coming to conclusions. The miracle of it is that they haven't got around to stopping yet. The major premise makes a statement about a class of things; for instance, "Not all major premises are true." The minor premise says that the thing with which we are concerned is a member of the class; for instance, "The last six words of the first sentence of this paragraph are a major premise." From this we conclude, "It is not always true that not all major premises are true." Such is the overwhelming capacity of logic to inform us of the realities of daily life. We note, however, that premises are essential for sillygisms. A baleful influence on Aristotelian habits among logicians has been exercised by the recent plethora of signs warning "Keep off the premises." Another function of the mathematical proof is to draw probable inferences from mathematical models of physical systems. For instance, given a sufficient number of physical data, the most desirable mathematical model is probably 36-24-36. De gustibus non es disputandum. With mathematical proof, scientists have succeeded in relating the hitherto disparate fields of thermodynamics and communication engineering in the discipline of information theory. "Information", as technically defined, is proportionate to surprise; the more surprising a message is, the more information it contains. If someone listening over the telephone heard "Hello" at the beginning of a conversation, he would not be very surprised; but his gain of information would be quite large if he were suddenly electrocuted. Great new possibilities in mathematical proof were made available with the development of set theory around the end of the last century and the beginning of this one. A set is any well-defined collection; examples are: the country club set, the table please set, permanent hair-set upset. A theorem in set theory recently discovered by this author is eminently worthy of mention here; the proof will be sketched. Theorem: A set whose only element is a set may be isomorphic to a set whose only element is a set whose only elements are a subgroup of the group of elements in the set which is the only element of the set with which it is isomorphic. [sick]. This intuitively obvious theorem follows rather deviously from the first isomorphism theorem of group theory. The duty of the logicians however, is to find the shortest logical line between hypothesis and conclusion. In this interest we give the following proof by a familiar method. Step 1: Hypothesis: We assume the entire existing body of mathematics. By inspection, the theorem follows. The aesthetically appealing simplicity of this method of proof has made many students revere the power of logic. The beauty of the method is exceeded by that of only one other, practiced by Immanuel Kant and first explicated by this author as proof by assumption. By assuming the desired conclusion in the hypothesis, the proof is somewhat simplified. Besides proof by inspection and proof by assumption, we have to consider proof by induction. Induction is so widespread that even the army does not hesitate to use it. So mechanical is its application that there exist an electronic device cleverly called induction coil. While inductive technique is simple, its results can be both deep and profound. The inductive principle is based on a set of five axioms stated around the end of the last century by an Italian musician named piano. Piano was trying to teach his bambino some arithmetic. The first axiom was that zero is a number. Any idiot knows this, which is why piano was a musician and not a mathematician. Axioms two, three and four were on a similar level of sophistication. For the fifth axiom, we must introduce the idea of a property. The numbers 1,4,9, and 16 all have the property of being the square of some natural number. If we call the property F, then we can say "1 is F, 4 is F," and so on. Now let F be an arbitrary property, for instance, "Monotonous", "incomprehensible". Piano's fifth axiom was: Every number is F if the property F satisfies the two conditions: (1)zero is F; and (2) if any individual is F, then so is its successor. At this point, Piano's bambino wet his diaper. This brings logical systems to mind. A logical system is distinct from a collection of theorems much as a mansion differs from a brickyard. In a logical system, each theorem is based upon what has come before. G. Polya has observed that Euclid's contributions was not in collecting geometrical facts, but in arranging them logically. Had he thrown the together randomly, he might have been just an ordinary author of high school texts. To illustrate the various methods of proof discussed above, we give an extended example of a logical system. (For the first theorem and lemmas of this system, which I propose to call "the pejorative calculus", I am indebted to professor Lee M. Sonneborn, Topologist, of the University of Kansas. Dr. Sonneborn is initially known among his students as "L.M.S.F.T.". The rest of the system is presented for the first time in this paper.) The Pejorative Calculus. Lemma I All horses are the same color. (by induction) Proof: It is obvious that one horse is the same color. Let us assume the proposition p(k) that k horses are the same color. Given the set of (k+1) horses, we remove one horse; then the remaining k horses are the same color, by hypothesis. We remove another horse and replace the first; the k horses, by hypothesis, are again the same color. We repeat this until by exhaustion, the (k+1) sets of k horses each have been shown to be the same color. It follows then that since every horse is of the same color as every other horse, p(k) entails p(k+1). But since we have shown p(1) to be true, p is true for all succeeding values of k. i.e.. all horses are the same color. Theorem I. Every horse has an infinite number of legs. (Proof by intimidation.) Proof: Horses have an even number of legs. Behind they have two legs, and in front they have fore legs. This makes six legs, which is certainly an odd number of legs for a horse. But the only number that is both odd and even is infinity. Therefore horses have an infinite number of legs. Now to show that this is general, suppose that somewhere there is a horse with a finite number of legs. But that is a horse of another color, and by the lemma that does not exist. Corollary I. Everything is the same color. Proof: The proof of lemma I does not depend at all on the nature of the object under consideration. The predicate of the antecedent of the universally quantified conditional "for all x, if x is a horse, then x is the same color," namely, " is a horse," may be generalized to "is anything" without affecting the validity of the proof; hence, "for all x, if x is anything, x is the same color." (Incidentally, x is the same color even if x isn't anything, but we do not prove that here.) Corollary II. Everything is white. Proof: If a sentential formula in x is logically true, then any particular substitution instance of it is a true sentence. In particular then, "for all x, if x is an elephant, then x is the same color," is true. Now it is manifestly axiomatic that white elephants exist . For proof by blatant assertion, consult mark twain, "The Stolen White Elephant"). Therefore all elephants are white. By corollary I everything is white. Theorem II. Alexander the Great did not exist and he had an infinite number of limbs. Proof: First we note the obvious fact that historians always tell the truth (for historians always take a stand, and therefore they cannot lie). Hence we have the historically true sentence, "If Alexander the Great existed, then he rode a black horse Bucephalus." But we know by corollary II everything is white; hence Alexander could not have ridden a black horse. Since the consequent of the conditional is false, in order for the whole statement to be true the antecedent must be false. Hence Alexander the Great did not exist. We also have the historically true statement that Alexander was warned by an oracle that he would meet death if he crossed a certain river. He had two legs; and "fore-warned is four-armed." This gives him six limbs, and even number, which is certainly an odd number of limbs for a man. Now the only number that is both even and odd is infinity; hence Alexander had an infinite number of limbs. But suppose he had a finite number of limbs. Then it would be possible to put his limbs in a one-to-one corespondance with the natural numbers, an operation which we shall call limbing. There would exist a last limb, and we should be able to limb it. But only an infinite series approaches a limbit. Hence he had an infinite number of limbs. We have proved: Alexander the Great did not exist and he had an infinite number of limbs. It is not to be imagined from this merely compendious account of the nature of mathematical proofs that everything has been proved. Witness the celebrated paradox of Euler's little liver lemma concerning the four cooler problem. Specifically we cite two unproved examples. The first is the famous Goldbrick conjecture from the theory of numbers, which states that every prime number is expressible as the sum of two even numbers. No counter-example has ever been found to this seemingly artless assertion, and the search for its proof has occupied mathematicians for centuries. The second example is a generalization well known, even if only intuitively, to practically the whole uncivilized world. It is Finagle's famous first law. "If something can go wrong, it will." Nor is it to be thought that there are not other types of proofs, which in print shops are recorded on proof sheets. There is the bullet proof and the proof of the pudding. Finally, there is the 200 proof, a most potent spirit among mathematicians and people alike. From: SOURCERER@delphi.com Subject: Problem Sourcerer 1.201 (Problem 1 for February 1, 1994 from Sourcerer to the Internet Amateur Mathematics Society.) A cylindrical tunnel is drilled completely through a sphere. The length of the tunnel is 10 meters. What is the volume of the remainder of the sphere? (I think that most of us have favorite mathematical riddles. They combine elegance, insight and just plain fun. The above is one of my all-time favorites. I ran across it many years ago after just having learned enough calculus to prove the solution rigorously. Calculus is NOT required for the solution, though. If you have a puzzle in your background which similarly charms you, please share it.) -------------- Solutions to problems 1.128: "Quickies: A) Find a number base other than 10 in which 121 is a perfect square. B) An anthropologist comes to fork in the road. He's been told beforehand that the fork will lead to a tribe of truth-tellers in one direction and a tribe of liars in the other direction. Both tribes were, in fact, a single tribe once, but they didn't get along. They -do-, however, share a common language and manner of dress. Unfortunately, the anthroplogist, while having seen pictures of these folk, had to prepare for his trip so hurredly that he only learned the words equivalent to 'yes' and 'no' from the tribes' common language and promptly forgot which was which. He only recalls that one of the words was 'iams' and the other was 'smai.' At the fork stands a native, obviously (by dress and bearing) from one of the tribes, who might be prevailed upon to direct the anthropologist to the village of his choice. The native however, seems in a hurry to leave and will obviously (for this is a very perceptive anthropologist) answer only one question and is not given to gesticulation. 'Fortunate,' the anthropologist thinks to himself, 'that these natives know -my- language, at least!' Now, given the conditions above, what one question might the anthropologist ask of the native, not knowing which of 'iams' and 'smai' mean 'yes' and which means 'no,' to find his way to where he's going?" Alexander "Sasha" Volokh was the first to answer the riddles correctly. His solutions follow. A) >In base a, "121" represents a^2 + 2a + 1 = (a+1)^2, which is always a >perfect square. Of course, the base must be greater than 2, or else >the digits "1" and "2" wouldn't exist. For example: >(121)_3 = 9 + 6 + 1 = 16 >(121)_4 = 16 + 8 + 1 = 25 >(121)_5 = 25 + 10 + 1 = 36 >... >(121)_a = a^2 + 2a + 1 = (a+1)^2 B) >"If I were to ask you if this road [pointing] led to the >truth-tellers' village, would you tell me 'smai'?" > >Both the truth-teller and the liar will give the same answer, because >the liar must invert the correct answer to the nested question twice. >Therefore, the answer given must be the correct one. > >If the answer is "smai," then either "smai" means yes and the road >does indeed lead to the truth-tellers' village, or "smai" means no >and so the road does NOT NOT leaed to the truth-tellers' village. >Either way, that road leads to the truth-tellers' village. > >If the answer is "iams," then that road leads to the liars' village. ==== Thanks to David Wagner (dawagner@princeton.edu) and Kermit Rose (rose@garnet.acns.fsu.edu) for their email solutions to part A. :) ==== Note: as in this case, solutions to these problems appear attached to new problems a few days after posting. Bruce M. Bowden Sourcerer@delphi.com From mike_griffin@il.us.swissbank.com Tue Feb 1 03:20:22 1994 (4.1/BK-1.9) id AA04456; Tue, 1 Feb 94 09:21:22 CST From: mike_griffin@il.us.swissbank.com (Mike Griffin) Subject: Re: Sum of squares... Requests.to.iams-request@quack.kfu.com > So factoring x^2+y^2 can only yield primes of the form 4k+1, >and vice versa - multiplying any number of primes of the form 4k+1 >yields a number which can be written as the sum of two squares. This is true if x^2 + y^2 is square-free. In general the intergers representable as the sum of two squares are of the form p_1^n_1 * ... *p_k^n_k where p_i == 1 (mod 4) or n_i is even. Mike Griffin From tulled@rpi.edu Tue Feb 1 08:36:36 1994 From: tulled@rpi.edu (David Michael Tuller) "Re: Sum of squares..." (Jan 31, 12:23pm) Subject: Re: Sum of squares... > Interested in a followup? Let me define a function f as > follows: if you give me a positive integer m, I'll first find the > m-th prime that is congruent to 1 (mod 4). [This sequence of primes > starts off as 5, 13, 17, 29, ...] Call the prime p_m. Next I'll > decompose into a sum of two squares, writing > > p_m=a_m^2 + b_m^2. > > Now define f(m)=a_m + b_m. > > Experimentally, it looks like the sequence f(1), f(2), ... > begins 3, 5, 5, 7, 7, 9, 9, 11, 11, 13, ... Does the pattern continue; > and if so, can you tell me why? Here are the values that I calculated. The pattern continues for a while but breaks down at 101. p_m a,b f(m) 5 1,2 3 13 2,3 5 17 1,4 5 29 2,5 7 37 1,6 7 41 4,5 9 53 2,7 9 61 5,6 11 73 3,8 11 89 5,8 13 97 4,9 13 101 1,10 11 Looks like it was just a coincidence. David M. Tuller tulled@rpi.edu From: "David A. Wagner" Subject: Re: Sum of squares... > > > So factoring x^2+y^2 can only yield primes of the form 4k+1, > >and vice versa - multiplying any number of primes of the form 4k+1 > >yields a number which can be written as the sum of two squares. > > This is true if x^2 + y^2 is square-free. In general the intergers > representable as the sum of two squares are of the form > > p_1^n_1 * ... *p_k^n_k > > where p_i == 1 (mod 4) or n_i is even. > Ahh yes good point, I should have been more explicit: I meant expressible in the form x^2+y^2 for positive integers x and y. Then the original statement is correct... Sorry! :-) Here's another followup, if you find this interesting: how many "different" ways are there to write p_1^a_1 p_2^a_2 \cdots p_k^a_k as a sum of two positive squares? [Assume p_i = 1 (mod 4) and p_i prime for all i.] For instance, when k=1, the expression as a sum of two squares is unique. [Disregard order, so that 5 = 1^2 + 2^2 = 2^2 + 1^2 counts as just one expression of 5 as a sum of two squares.] ------------------------------------------------------------------------------- David Wagner dawagner@princeton.edu From mike_griffin@il.us.swissbank.com Tue Feb 1 07:00:16 1994 (4.1/BK-1.9) id AA09443; Tue, 1 Feb 94 13:01:16 CST From: mike_griffin@il.us.swissbank.com (Mike Griffin) Subject: Sum of squares... Here's what I was trying to say, in plaintext. Apologies if you received a uuencoded version.... > Ahh yes good point, I should have been more explicit: I meant >expressible in the form x^2+y^2 for positive integers x and y. Then >the original statement is correct... Sorry! :-) No, still not quite right: 45 = 9*5 = 3^2(2^2 + 1^2) = 6^2 + 3^2 is a sum of two non-zero squares which has a prime factor not congruent to 1 (mod 4). From: Kermit Rose Subject: sum of pentagon points. The regular pentagon is drawn in the complex plane so that its center is at the origin. Three of the vertices are to the right of the y-axis and two of the vertices are to the left of the y-axis. Prove that the sum of the two distances from the y-axis to the two vertices to the left is equal to the sum of the three distances from the y-axis to the three vertices to the right. distance(v1) + distance(v2) = distance(v3) + distance(v4) + distance(v5) Kermit. From: csaba@teleport.com (Csaba Gabor) Subject: Re: sum of pentagon points. - SPOILER Problem: Show that the sum of the x coordinates of a regular pentagon centered at the origin is 0. Solution: We borrow from the interesting solution to the hexagon problem a few days back. define z^5 = 1, z # 1, and let p be one vertex of the pentagon. Then the remaining vertices in the complex plane are pz, pz^2, pz^3, pz^4. We would like to find Re(p + pz + pz^2 + pz^3 + pz^4) = Re(p(z^4 + z^3 + z^2 + z + 1)) = Re(p(z^5-1)/(z-1)) = Re(0) = 0 From: Kermit Rose Subject: sum of 4th powers. Prove the following: If x,y,z are any positive integers, then ( x^4 + y^4) ^7 + 1 is never divisible by 29. (x^4 + y^4) ^4 - 4 is never divisible by 17. (x^4 + y^4) ^3 - 5 is never divisible by 13. x^4 + y^4 + z^4 is divisible by 29 only if each of x, y, and z is divisible by 29. Kermit. From: Competitive Enterprise Institute Subject: Re: spoof of mathematics On a similar note, here's something I wrote about 4 years ago: A BRIEF HISTORY OF GREEK PHILOSOPHY It all started with Socrates, the famous Greek philosopher of the 5th century B.C., who used to say, "I only know one thing, and that is that I know nothing." Nowadays, in the 20th century, we take pride in sneering at this Greek luminary, and wondering how he could possibly have thought that something was nothing. But it would probably be best for us to keep quiet -- those ancient Greeks weren't as dumb as we think they were. In fact, as early as the 4th century B.C., a whole school of Greek philosophers (all Greek philosophers were peripatetic and traveled in schools), little known today because of its aloofness from the mainstream philosophy of Plato, had as its credo, "I only know one thing, and that is that I know one thing," but they found that that only confused the already perplexed. They tried to add spice to their maxim by changing it to "I only know one thing, and that is that I know one thing, that one thing being that I know one thing," but here, it was a classic case of "Out of the frying pan and into the fire." This school of philosophy died a quick and painless death, easily succumbing to the greater popularity of the comedies of Aristophanes. But their memory lived on in Athenian schools such as the Academy; future thinkers tried to reconcile the Socratic view with common sense and suggested such words to live by as "I only know one thing -- how to eat," or "One thing is all you need to know -- Love is all you need," but the immortal words of Socrates survived these fads, because Socrates had all his thoughts recorded by Plato, who wrote them up in clay tablets, whereas the other philosophers preferred the new-fangled invention, paper, which easily decomposed and was better for the environment. Some frustrated philosophers tried to discredit the name of Socrates altogether, wondering why people chose to follow a philosopher who only knew a wrong thing. Still another school was fond of asking why people assumed that Socrates made his mistake in the second part of his sentence. As we know, they reasoned, Socrates made a great many mistakes, and some of them may have been at the beginnings of sentences. It is this school that suggested the ageless adage, "I know two things: one wrong thing, which is that I know nothing, and a correct thing, which I forgot" -- but the rulers of Athens, fearing a popular revolt against the revilers of the memory of their beloved teacher, sent the entire school to Asia Minor to fight the Persians. They were all hanged by the Gordian Knot. Henceforth, no philosopher seriously attempted to discredit the ideals of Socrates and of his school; and thus, Socrates, Plato, and Aristotle were widely studied throughout the Middle Ages. The only Greek philosophers of any consequence, after Aristotle, were almost exclusively logicians, who attempted to make sense of the laws of syllogisms. A syllogism, as we well know, is a series of three statements -- two premises and a conclusion drawn from the premises, such as "All men are mortal, Socrates is a man, therefore Socrates is mortal." Syllogisms, however, are not as simple as they appear -- take, for instance, the perplexing example of "All cats are mortal, Socrates is mortal, therefore Socrates is a cat," or "An inexpensive car is rare, all rare things are expensive, therefore an inexpensive car is expensive." The "syllogism issue," as it was called until well into the 2nd century B.C., confounded many a young, promising mind. The movement made no startling discoveries, but did succeed in explaining the Egyptian belief in the sacredness of cats: "All cats are mortal, Socrates is mortal, therefore Socrates is a cat; but Socrates is not a cat, as we can plainly see, and yet Socrates is mortal, since he's dead, therefore cats must be immortal." So you see, you have to give the Greeks some credit. They were really no dummies. From: Android Subject: Plans for IAMS As some of you know already, IAMS is moving to a new domain, namely hh.sbay.org (Do not send emails to there yet). I have talked to the sysop at that place, and he is suggesting that we pit out a newsgroup alt.iams for people who would be able to use the newsgroup. If not, you could use the list. People on the newsgroup will get messagese sent to the list people on the mailing list will get messages sent to the newsgroup. The new arrangement will take loads away from his machine, so he prefers it that way. I do not really care because I would try to keep the mailing list as clean as possible anyway (later it would be moderated). Personally, I think the newsgroup arrangement would work better. What do you guys think? I do not plan to start the sci.math.iams kind of newsgroup soon because it takes too much time. I think alt.iams would work if we all keep in mind that it is still math oriented. Does anyone know if I could moderate an alt. group? I am open for suggestions. Benjie From: tulled@rpi.edu (David Michael Tuller) Subject: Diophantine Equation Find all solutions (in integers) to a+b+c=ac/b. Enjoy! David M. Tuller tulled@rpi.edu From: "Travis Kidd" Subject: x^5 mod 41 Let x be an integer. Find all possible congruences of x^5 (mod 41). The answer is surprising (at least to me)! -Travis From: Kermit Rose Subject: Another Diophantine Equation. Find all solutions to a - b + c = ac/b Kermit. From: Kermit Rose Subject: more about 5th powers mod 41 prove that for any positive integers x, y (x^5 + y^5) ^8 + 4 is never divisible by 41. kermit From: SOURCERER@delphi.com Subject: Problem Sourcerer 1.203 (Problem 1 for February 3, 1994 from Sourcerer to the Internet Amateur Mathematics Society.) Encounter Problem A married couple on a shopping expedition (the wife's idea, actually) agree to meet at a specified street corner between 4:00 and 5:00 PM. The one who arrives first agrees to wait 15 minutes for the other, after which that person will leave to continue shopping. What is the probability that the couple will meet, assuming that their arrival times are random within the hour? -------------- Solution to problem 2.129: "A line segment AB, with midpoint M, has length a. A point X is randomly chosen interior to the segment. What is the probability that segments AX, BX, and AM can be the sides of a triangle?" The sum of the lengths of any two sides must be greater than the length of the third side. Since the length of segment AX is x, the length of segment BX is a - x, and the length of segment AM is a/2, x + a/2 > a - x, (a - x) + a/2 > x. These are equivalent to x > a/4, x < 3 * a/4. Rewriting this, a success occurs if the point selected has coordinate x, where a/4 < X < 3 * a/4. The probability, therefore, is ((3 * a/4) - a/4)/a = 1/2. ==== Correct solutions to 2.129 from Alexander Volokh, Csaba Gabor and Kermit Rose. ==== Response to 2.129 from David Wagner: >``Interior to''? What's that mean? I guess I never was too good at >geometry :-) ==== Note: as in this case, solutions to these problems appear attached to new problems a few days after posting. Bruce M. Bowden Sourcerer@delphi.com From: ua532@freenet.victoria.bc.ca (David Snook) Subject: Spoiler This is my first posting so if it's going to the wrong destination my apologies, in advance. RE: a+b+c = (a*c)/b Set b = any prime number n = any integer a = 2*b c = 3*b Then n*(2*b + b + 3*b) =n*(((2*b)*(3*b))/b) eg 4,006 + 2,003 + 6,009 = 12,018 (4,006*6,009)/2,003 = 12,018 There are an infinite number of these. There are also other ways achieving equality between the sum and product/division. Thanx. Dave. -- David J. Snook.................................ua532@freenet.victoria.bc.ca From: Kermit Rose Subject: re: Diophantine Equation - Spoiler Find all integer a,b,c such that a + b + c = ac/b answer below a + b + c = ac/b ab + b^2 + cb = ac b^2 + cb = ac - ab b^2 + cb = a(c-b) b^2 + b^2 - b^2 + cb = a(c-b) 2b^2 -b^2 + cb = a(c-b) 2b^2 +cb - b^2 = a(c-b) 2b^2 +(c-b)b = a(c-b) 2b^2 = a(c-b) - (c-b)b 2b^2 = a(c-b) - b(c-b) 2b^2 =(a-b)(c-b) Let b = pr. Then 2(pr)^2 = (a-pr)(c-pr) Let a-pr = p^2 and c-pr =2 r^2 Then a = pr + p^2 = p(p+r) and c = r(p+2r) Verification. a + b + c = p(p+r) + pr + r(p+2r) = p^2 + pr + pr + pr + 2 r^2 = p^2 + 3pr + 2 r^2 = (p+r)(p+2r) = pr(p+r)(p+2r)/pr = p(p+r) r(p+2r)/pr = a c /b Kermit. From: SOURCERER@delphi.com Subject: Problem Sourcerer 1.204 (Problem 1 for February 4, 1994 from Sourcerer to the Internet Amateur Mathematics Society.) Show that a finite group can't be the union of two of its proper subgroups. Does the statement remain true if "two" is replaced by "three"? -------------- Solution to problem 1.130: "Two circles are concentric. A chord of the outer circle runs tangent to the inner circle and is two meters in length. What's the area of the region between the two circles?" It may seem that there's not enough information here for solving the problem but, of course, you have all the facts you need. Assuming such to be the case, it can be deduced that the actual sizes of the circles are unimportant to the solution, provided that a chord of the given length is possible. Therefore, allow the inner circle to go to zero so that the chord is the diameter of the larger circle. Obviously, the area between the two regions is pi times the square of half the chord length, or pi square meters. To prove the legitimacy of this answer, make a diagram. If R is the radius if the large circle, connected from one end of the chord to the center, and r is the radius of the smaller circle, connected from the point of tangency to the center, then the right triangle so-formed shows R^2 - r^2 = (l/2)^2. Since the definition of the area we seek is pi * (R^2 - r^2), the area is pi * (l/2)^2. ==== Correct solutions from Alexander Volokh, Benjie Chen, Csaba Gabor, and Kermit Rose in private correspondence. ==== Note: as in this case, solutions to these problems appear attached to new problems a few days after posting. Bruce M. Bowden Sourcerer@delphi.com From: Steve Wildstrom Subject: Re: x^5 mod 41 (Spoiler) On Wed, 2 Feb 1994, Travis Kidd wrote: > Let x be an integer. > Find all possible congruences of x^5 (mod 41). > The answer is surprising (at least to me)! > > -Travis > Spoiler--although this isn't really a problem Well, I finally had a chance tosit down with the modular arithmetic calculator I designed as a Visual Basic problem and compute the results. For x from 1 to 41, there are only eight numbers congruent to (x^5) mod 41-- 1,3,9,14,27,32,38 and 40. Each occurs exactly five times. But I don't see any patter that would explain why these five values or how they are distributed. Any number theoreticians have thoughts? From: ua532@freenet.victoria.bc.ca (David Snook) Subject: SPOILER (X^5 mod 41) RE: X^5 mod 41 Each congruency is repeated exactly five(5) times. In other words equally distributed. 1 x 5 27 x 5 3 x 5 32 x 5 9 x 5 38 x 5 14 x 5 40 x 5 Also of some general interest are the following: 40^5 mod 41 = 40 32^5 mod 41 = 32 9^5 mod 41 = 9 1^5 mod 41 = 1 I'm not sure if this was the desired solution. Thanx, Dave. -- David J. Snook.................................ua532@freenet.victoria.bc.ca From: Kermit Rose Subject: Re: x^5 mod 41 (Spoiler) (fwd) Forwarded message: > > > On Wed, 2 Feb 1994, Travis Kidd wrote: > > > Let x be an integer. > > Find all possible congruences of x^5 (mod 41). > > The answer is surprising (at least to me)! > > > > -Travis > > > > Spoiler--although this isn't really a problem > > > > > > > > > > > > > > > > > > > > > > > > > > > Well, I finally had a chance tosit down with the modular arithmetic > calculator I designed as a Visual Basic problem and compute the results. > For x from 1 to 41, there are only eight numbers congruent to (x^5) mod 41-- > 1,3,9,14,27,32,38 and 40. Each occurs exactly five times. But I don't see > any patter that would explain why these five values or how they are > distributed. Any number theoreticians have thoughts? > Note that the numbers are 1,3,9,27, 40,38,32,14. That is, 1,3,9,27, -1,-3,-9,and -27. THe 5th powers mod 41 are + or - the powers of three. Kermit. From: Kermit Rose Subject: Another Diophantine Equation. (spoiler) > > Find all solutions to > > a - b + c = ac/b > > > Kermit. > > a - b + c = ac/b ab - b^2 + cb = ac - b^2 + cb = ac - ab cb - b^2 = ac - ab (c-b) b = a(c-b) b(c-b) = a(c-b) 0 = a(c-b) - b(c-b) 0 = (a-b) (c-b) Thus a-b = 0 or c-b = 0. b=a or b=c. From: Kermit Rose Subject: square puzzle. (spoiler) > > This is a puzzle I copied out of a book. > > The solicitor was reading the eccentric's will. > > "To my faithful gardener, Jack", he read. "I bequeath the sum of $1000, > with the request that part of the money be spent in planting a rose garden > with 50 rosebushes within each of five circles, and 50 rosebushes in each > of ten rows, no two beds containing the same number of bushes." > > "At $1 a bush," said Jack, "I reckon I will only have $250 left of that > legacy." > > "At $1 a bush," said Jack's wife, "I reckon you can hang on to $800." > > "How?" said Jack. > > "Easy," said his wife. She drew the sketch below and began filling in the > number of rosebushes to be planted in each bed. > > "I get it," said Jack. "Don't fill in any more. I can work the rest out > myself". > > > ( I have drawn 5 squares instead of 5 circles because of text constraints.) > > l---------------l---------------- > l * 7 l 6 * l > l l l > l ----------------- l > l l l l l > l 9 l * l 15 l * l > l l l l l > --------l---------------l-------- > l l l l l > l * l * l 11 l 16 l > l l l l l > l l----------------- l > l l l > l * * l * * l > ----------------------------------- > > > l---------------l---------------- > l 20 7 l 6 17 l > l l l > l ----------------- l > l l l l l > l 9 l 14 l 15 l 12 l > l l l l l > --------l---------------l-------- > l l l l l > l 13 l 10 l 11 l 16 l > l l l l l > l l----------------- l > l l l > l 8 19 l 18 5 l > ----------------------------------- > From: David G Radcliffe Subject: Shortest path in cube Here's a quickie: Let P be a point in the interior of a unit cube. Find the length of the shortest path beginning and ending at P which meets every face. == Dave (radcliff@csd4.csd.uwm.edu) From: SOURCERER@delphi.com Subject: Problem Sourcerer 1.205 (Problem 1 for February 5, 1994 from Sourcerer to the Internet Amateur Mathematics Society.) Show that any curve of unit length can be covered by a closed rectangle of area 1/4. -------------- Solution to problem 2.130: "Let Dn be the determinant of order n of which the element in the ith row and the jth column is the absolute value of the difference of i and j. Show that Dn is equal to (-1)^(n-1) * (n-1) * 2^(n-2)." Subtract the first column from every other column. Then add the first row to every other row. The last row now has all zeros except for (n-1) in the first column. Dn is (-1)^(n-1) * (n-1) times the minor formed by deleting the first column and last row from the transformed determinant. This minor has only zeros below the main diagonal and thus is equal to the product of its diagonal elements. Hence the minor has value 2^(n-2) and Dn = (-1)^(n-1) * (n-1) * 2^(n-2). ==== Note: as in this case, solutions to these problems appear attached to new problems a few days after posting. Bruce M. Bowden Sourcerer@delphi.com From: Ariel Scolnicov Subject: Trick question #1 Quite a lot can be learnt from trick questions, i.e. (in this context) questions which implicitly depend on a fallacy. I've been collecting a few of these lately, so I might as well post them... I'll be glad to hear of any other questions people might have. #1 -1/(x*x) Define a real function by f(x) = e . (That's exp(-1/(x*x)) for programming types) for x not equal to 0, f(0) = 0. Find f's McLaurin series expansion (a McLaurin expansion is a Taylor series about x=0). Enjoy! Ariel Scolnicov From: Sylvan Jacques Subject: SPOILER (?) RE exp(-1/x^2) RE: The function exp(-1/(x*x)). ======= SPOILER ? ======= The function exp(-1/(x*x)) is infinitely differentialble (is C-oo), but not analytic. All its derivatives are 0 at x = 0, though it is nonzero in the neighborhood of 0, so it is not an analytic function. =========== This function and variations on it are important for distributions. In the theory of integration, one often wants to consider the space of C-oo functions of compact support, and no analytic function has compact support. One can construct C-oo functions of compact support, using exp(-1/(x*x)), e.g., f(x) = exp[-a^2/(a^2 - |x|^2)] for |x| < a, and = 0 for |x| > or = a . Using this, one can construct "regularizing" and "truncating" sequences of functions. From: rsmotz@aol.com Subject: Triangle Area I was wondering if anyone out there knows of the name of this formula K=(1/2)*abs{(x1 y1 1), (x2 y2 1), (x3 y3 1)} <==sqr. matrix, where K is the area of the triange whose vertices are (x1,y1), (x2,y2), and (x3,y3). If you do not know of the name of this formula, do you know of the creator? Any help would be appreciated, thank you. RSmotz From: Competitive Enterprise Institute Subject: Re: Triangle Area On Sat, 5 Feb 1994 rsmotz@aol.com wrote: > I was wondering if anyone out there knows of the name of this formula > K=(1/2)*abs{(x1 y1 1), (x2 y2 1), (x3 y3 1)} <==sqr. matrix, where K is the > area of the triange whose vertices are (x1,y1), (x2,y2), and (x3,y3). If you > do not know of the name of this formula, do you know of the creator? Any > help would be appreciated, thank you. This is the cross product, I believe. - Alexander "Sasha" Volokh From: SOURCERER@delphi.com Subject: Problem Sourcerer 1.206 (Problem 1 for February 6, 1994 from Sourcerer to the Internet Amateur Mathematics Society.) Find the length of the longest sequence of equal nonzero digits in which an integral square can terminate (in base 10) and find the smallest square which terminates in such a sequence. -------------- Solution to problem 1.201: "A cylindrical tunnel is drilled completely through a sphere. The length of the tunnel is 10 meters. What is the volume of the remainder of the sphere? (I think that most of us have favorite mathematical riddles. They combine elegance, insight and just plain fun. The above is one of my all-time favorites. I ran across it many years ago after just having learned enough calculus to prove the solution rigorously. Calculus is NOT required for the solution, though. If you have a puzzle in your background which similarly charms you, please share it.)" The reasoning to be applied here is similar to the concentric circles problem (1.130). You have all the information you need to solve the problem, and calculus isn't required. If the length of the tunnel is all that matters, then the tunnel width is unimportant. For a huge sphere, the tunnel width will be correspondingly huge in order for it to have the original length. The opposite case is to make the width zero. In this case, the diameter of the sphere would be 10 meters. Hence, the volume is pi * r^3 * 4/3, or 500 * pi/3 - regardless of the actual, original sphere size. ;) To prove this by calculus, take a cross-section of the sphere, intersecting the axis of the tunnel. Place this cross-section on the x-y plane with the y-axis on the axis of the tunnel and the x-axis passing through the point corresponding to the center of the sphere. We're only concerned with the portion of the cross-section in the first quadrant. Let L represent half the length of the tunnel and let R be the radius of the sphere. The volume is found by integrating by the shell method (integral of 2 * pi * x * f(x), with respect to x) and multiplying by two. f(x) is SQRT(R^2-x^2), and the limits of integration are from SQRT(R^2 - L^2) to R. ==== Correct solution to 1.201 in private correspondence from Benjie Chen. ==== Note: as in this case, solutions to these problems appear attached to new problems a few days after posting. Bruce M. Bowden Sourcerer@delphi.com From: Ariel Scolnicov Subject: Trick Q #2 A more than complete answer to #1 was given by Sylvan Jacques . Apart from showing that not all that is infinitely differentiable is analytic (in the reals), this example shows that the method of analysing an extremum by looking at the first nonzero derivative isn't always useful. .......................................................................... Question #2 is from probability: You are presented with two envelopes, one of which contains twice as much money as the other. One of the envelopes is randomly selected and opened, revealing $1000. You may take the money in either this envelope or the other. A quick calculation shows that the expectation for opening the other is $1250 - hence you should switch. Generalise this answer to $N in the opened envelope. Ariel Scolnicov From: SOURCERER@delphi.com Subject: Problem Sourcerer 2.206 (Problem 2 for February 6, 1994 from Sourcerer to the Internet Amateur Mathematics Society.) A quadrilateral which can be inscribed in a circle is said to be inscribable or cyclic. A quadrilateral which can be circumscribed to a circle is said to be circumscribable. Show that if a circumscribable quadrilateral of sides a, b, c, d has area A = SQRT(a * b * c * d), then it is also inscribable. -------------- Solution to problem 1.202: "P is a non-self-intersecting closed polygon with n sides. Its vertices are P1, P2, ... ,Pn. Now let m other points, Q1, Q2, ... Qm interior to P be given. Let the interior of P be triangulated. This means that certain pairs of the (n + m) points P1, ... , Qm are connected by line segments such that (i) the resulting figure consists exclusively of a set T of triangles, (ii) if two different triangles in T have more than a vertex in common then they have exactly a side in common, and (iii) the set of vertices of the triangles in T is precisely the set of (n + m) points P1, ... , Qm. How many triangles in T?" Call t the number of triangles. In Euler's formula V - E + F = 2, F = t + 1, and V = n + m. Since every edge is on two faces, 2 * E = 3 * t + n. Substitution leads directly to the answer t = 2 * m + n - 2. ==== Note: as in this case, solutions to these problems appear attached to new problems a few days after posting. Bruce M. Bowden Sourcerer@delphi.com From: SOURCERER@delphi.com Subject: Problem Sourcerer 1.207 (Problem 1 for February 7, 1994 from Sourcerer to the Internet Amateur Mathematics Society.) The three vertices of a triangle of sides a, b and c are lattice points and lie on a circle of radius R. Show that a * b * c G.E. 2 * R. (Lattice points are points in the Euclidean plane with integral coordinates. "G.E." means "greater than or equal to.") -------------- Solution to problem 1.203: "A married couple on a shopping expedition (the wife's idea, actually) agree to meet at a specified street corner between 4:00 and 5:00 PM. The one who arrives first agrees to wait 15 minutes for the other, after which that person will leave to continue shopping. What is the probability that the couple will meet, assuming that their arrival times are random within the hour?" Let x and y be the number of minutes after 4:00 PM that the husband and wife arrive, respectively. All the possible pairs of arrival times can be represented by the set of ordered pairs (x, y) where 0 < x < 60, and 0 < y < 60. The members of the sample space are the points inside a square of side 60. In order for the couple to meet, their arrival times must be within 15 minutes of each other. This observation is symbolized by the absolute value inequality |x - y| < 15. The success region, within the square, is between the lines x - y > -15 and x - y < 15. The probability is 1575/3600, or 43.75%. ==== Correct solutions to 1.203 from Alexander "Sasha" Volokh, Ben Davenport, and David Wagner. ==== Note: as in this case, solutions to these problems appear attached to new problems a few days after posting. Bruce M. Bowden Sourcerer@delphi.com From: Sergio Martino Subject: Did you know how ... Dear Netters, while examining the Italian lotto system I faced the following problem for which I am asking your help. Assumption: (1) I can arrange m numbers to form C(m,2) different pairs. Problem statement: Is it possible to partition these m numbers in k sets each of n numbers (obviously m = k * n) so that the k * C(n,2) resulting pairs are the same found in (1)? m and n are given. From simple consideration on factoring I can prove this is not possible (except when k = 1 :)), so I reformulate the problem in this way: Is it possible to partition these m numbers (taken each r times) in k sets each of n numbers (obviously m * r = k * n) so that the k * C(n,2) resulting pairs contains each of those found in (1) with the same multiplicity? Thanks, Sergio From: Kermit Rose Subject: Problem Sourcerer 1.206 (spoiler) > > Find the length of the longest sequence of equal nonzero digits in > which an integral square can terminate (in base 10) and find the > smallest square which terminates in such a sequence. > 20 15 10 5 0 The repeated digit is 4. The longest string is 444. The smallest square ending in 444 is 38^2 = 1444. This was confirmed by the following computer program written in fortran. MOD = 1 2 CONTINUE KOUNT = 0 MOD = 10* MOD MTEST = (MOD -1) /9 DO 1 J = 1,MOD K = J*J L = K - MOD* (K/MOD) IF( L.EQ.0)GO TO 1 IF(L.NE.(MTEST* (L/MTEST)) )GO TO 1 KOUNT = KOUNT + 1 PRINT *,' KOUNT = ',KOUNT,' MOD = ',MOD,' X = ',J,' K = ',K 1 CONTINUE IF(KOUNT.NE.0)GO TO 2 STOP END From: SOURCERER@delphi.com Subject: Problem Sourcerer 1.208 (Problem 1 for February 8, 1994 from Sourcerer to the Internet Amateur Mathematics Society.) F(x) is a real-valued function defined for all real x except for x = 0 and x = 1 and satisfying the functional equation F(x) + F{(x - 1)/x} = 1 + x. Find all functions F(x) satisfying these conditions. ;) -------------- Solution to problem 1.204: "Show that a finite group can't be the union of two of its proper subgroups. Does the statement remain true if 'two' is replaced by 'three'?" The number of elements in a subgroup is a divisor of the order of the group. Thus a proper subgroup can have no more than half of all the elements. Two subgroups always have the identity in common and hence their union cannot be the entire group. An example for the second part of the problem is the Klein group, which has an identity and three elements x, y, z of order two. The product of any two distinct elements from {x, y, z} is the third. This group is the union of three proper subgroups. ==== Solutions on the same day for 1.204 from Csaba Gabor, David Wagner and Scott Pallack. ==== Note: as in this case, solutions to these problems appear attached to new problems a few days after posting. Bruce M. Bowden Sourcerer@delphi.com From: Kermit Rose Subject: Problem Sourcerer 1.208 (spoiler) > > F(x) is a real-valued function defined for all real x except for > x = 0 and x = 1 and satisfying the functional equation > F(x) + F{(x - 1)/x} = 1 + x. > Find all functions F(x) satisfying these conditions. ;) > 20 15 10 5 0 F(x) + F( [x-1]/x ) = 1 + x x = (y-1)/y = 1 - 1/y (x-1)/x = 1 - 1/x = 1 - 1/([y-1]/y) = 1 - y/(y-1) = [ (y-1) - y]/(y-1) = -1/(y-1) F([y-1]/y) + F(-1/[y-1]) = 1 + 1 - 1/y = 2 - 1/y F([x-1]/x) + F(-1/[x-1]) = 2 - 1/x x = 1 - 1/y -1/(x-1) = -1/(-1/y) = y F(-1/[y-1]) + F(y) = 1 - 1/[y-1] F(-1/[x-1]) + F(x) = 1 - 1/[x-1] Summary: F(x) + F( [x-1]/x ) = 1 + x F([x-1]/x) + F(-1/[x-1]) = 2 - 1/x F(-1/[x-1]) + F(x) = 1 - 1/[x-1] (F(x) + F( [x-1]/x) ) - ( F([x-1]/x) + F(-1/[x-1]) ) +( F(-1/[x-1]) + F(x) ) = (1+x) - (2-1/x) + (1-1/[x-1]) 2 F(x) = 1+x -2 + 1/x +1 - 1/[x-1] 2 F(x) = x + 1/x - 1/[x-1] F(x) = (x + 1/x - 1/[x-1] )/2 From: SOURCERER@delphi.com Subject: Problem Sourcerer 1.209 (Problem 1 for February 9, 1994 from Sourcerer to the Internet Amateur Mathematics Society.) Two cars travel around a track at equal and constant speeds, each completing a lap every hour. From a common starting point, the first starts at time t = 0 and the second at an arbitrary later time t = T > 0. Prove that there is a total period of exactly one hour during the motion in which the first has completed twice as many laps as the second. -------------- Solution to problem 1.205: "Show that any curve of unit length can be covered by a closed rectangle of area 1/4." Place the curve so that its endpoints lie on the x-axis. Then take the smallest rectangle with sides parallel to the axes which covers the curve. Let this rectangle's horizontal and vertical dimensions be a and b, respectively. Let P0 and P5 be the endpoints of the curve, and let P1, P2, P3, and P4 be the points on the curve, in the order named, which lie one on each of the four sides of the rectangle. Draw the broken line P0-P1-P2-P3-P4-P5. This line has a length of, at most, one. The horizontal components of the segments of this broken line add up at least to a, since one of the vertices of the broken line lies on the left end of the rectangle and one on the right end. The vertical segments add to at least 2 * b since we start and finish on the x-axis and go to both the top and bottom sides. This implies that the total length of the broken line is at least SQRT(a^2 + 4 * b^2). We now have that a and b both lie between 0 and 1 and that a^2 + 4 * b^2 L.E. 1. Under these conditions, the product a * b is a maximum for a = SQRT(2)/2, b = SQRT(2)/4 and so the maximum of a * b is 1/4. The area of the constructed rectangle, then, is at most 1/4. ("SQRT" means "square root of" and "L.E." means "less than or equal to.") ==== ==== Note: as in this case, solutions to these problems appear attached to new problems a few days after posting. Bruce M. Bowden Sourcerer@delphi.com From: SOURCERER@delphi.com Subject: Problem Sourcerer 1.211 (Problem 1 for February 11, 1994 from Sourcerer to the Internet Amateur Mathematics Society.) How many zeros does the function f(x) = 2^x - 1 - x^2 have on the real line? -------------- Solution to problem 1.206: "Find the length of the longest sequence of equal nonzero digits in which an integral square can terminate (in base 10) and find the smallest square which terminates in such a sequence." If x is an integer, then x^2 is congruent with 0, 1, 4, 6 or 9 (mod 10). The case x^2 congruent to 0 (mod 10) is eliminated by the statement of the problem. If x^2 congruent to 11, 55 or 99 (mod 100), then x^2 congruent to 3 (mod 4) which is impossible. Similarly, x^2 congruent to 66 (mod 100) implies x^2 congruent to 2 (mod 4) which is also impossible. Therefore x^2 congruent to 44 (mod 100). If x^2 congruent to 4444 (mod 10,000), then x^2 congruent to 12 (mod 16), but a simple check shows that this is impossible. Finally, note that 38^2 = 1444. ==== Note: as in this case, solutions to these problems appear attached to new problems a few days after posting. Bruce M. Bowden Sourcerer@delphi.com From: Sylvan Jacques Subject: SPOILER ZEROS OF 2^x - 1 - x^2 SPOILER =================== The function f(x) = 2^x - 1 - x^2 has derivatives df/dx = f'(x) = ln(2)*2^x - 2x and d/dx[df/dx] = f"(x) = .693^2*2^x - 2 df/dx has 2 zeros, which means there is a max of 3 zeros of f(x). The zeros of df/dx are between x = 0 and 1, and between x = 4 and 5. f"(x) is < 0 for x < a and > 0 for x > a, where a is very near 2. Its easy to verify that f(0) = f(1) = 0, leaving only the solution between 4 and 5. There are several way of finding an approximate solution, and x = 4.258 is very close to the 3rd zero of f(x). Finally, we have x = 0, 1, 4.258 as the zeros. Van van@quack.kfu.com From: mike_griffin@il.us.swissbank.com (Mike Griffin) Subject: Re: IAMS' new domain/site Benjie, I have to say I'm uncomfortable with your plan to moderate the IAMS mailing list. I'm not sure what the motivation for this is, but I'd guess it is to cut down on what you (and others) consider irrelevant discussions. My own view is that the discussions that have taken place have been interesting and quite relevant. One very nice thing about this mailing list is the ability to carry on extended exchanges in a semi-public forum. If that generates too much mail for some people's tolerance level, they can delete it, before or after reading it. If it's still a problem, then why are they subscribing to IAMS anyway? I hope you will invite discussion of this plan, and poll the list to make sure this what most members want. (I have never been asked.) Of course, if you OWN the IAMS, then I will certainly defer to you and shut up. Mike Griffin From: SOURCERER@delphi.com Subject: Problem Sourcerer 1.212 (Problem 1 for February 12, 1994 from Sourcerer to the Internet Amateur Mathematics Society.) A MYSTERY This is a problem which seems to be without an easy solution, and it has a story behind it. A few days ago, David Snook (ua532@freenet.victoria.bc.ca) sent the following problem, which he had seen elsewhere and which was causing him a lot of annoyance: Of two numbers a and b is known that 1 < a < b <= 100 Mr. P knows the product of a and b Mr. S knows the sum of a and b [Aside from Bruce: assume that both know about the inequality above, but that Mr. P doesn't know the sum and Mr. S doesn't know the product.] Mr P and Mr S now have the following conversation. P: I dont know a or b. S: I already knew that. P: But then I know them. S: Now I also know what a and b are. David also sent me the solution in a and b, and that it's purported to be unique. What bothered David about the puzzle - and me as well, now that I've played with it - stems from the reasonable supposition that there's a trick or insight that yields the answer without very many steps. Well, David and I have wrestled with this, even trying to work backwards from the "unique" solution - but apart from a brute force search by computer (which both of us are loath to resort to) there seems no elegant answer. David writes: > My understanding is that the author did not have any knowledge of the solution when he originally posted the problem. He was relying on the rec.puzzles group to provide the solution. > When I queried him as to how the solution was derived. He replied that all of the other possible {P,S,a,b}'s had been removed by reduction. (He had not done it). That Three(3) other people had arrived at the same answer ..........ERGO it was correct. Besides, he noted the answer works. So, with David's blessing, I put the case before the membership. The question of the day, then, is: (a) give the values for a and b, and (b) show that this solution is unique. Tomorrow I'll supply the values of the sum and product, which were not given in the original statement of the problem, but may assist someone in discovering the secret of this perplexing mystery. If that isn't helpful, I'll conclude Monday with the values of a and b and a quick discussion. -------------- Solution to problem 2.206: "A quadrilateral which can be inscribed in a circle is said to be inscribable or cyclic. A quadrilateral which can be circumscribed to a circle is said to be circumscribable. Show that if a circumscribable quadrilateral of sides a, b, c, d has area A = SQRT(a * b * c * d), then it is also inscribable." Since the quadrilateral is circumscribable, a + c = b + d. Let k be the length of a diagonal and angles U and V selected so that k^2 = a^2 + b^2 - 2 * a * b * COS U = c^2 + d^2 - 2 * c * d * COS V. If we subtract (a - b)^2 = (c - d)^2, we obtain (i) 2 * a * b * (1 - COS U) = 2 * c * d * (1 - COS V). From A = 1/2 * a * b * SIN U + 1/2 * c * d * SIN V = SQRT(a * b * c * d), 4 * A^2 = 4 * a * b * c * d = a^2 * b^2 * (1 - COS^2 U) + c^2 * d^2 * (1 - COS^2 V) + 2 * a * b * c * d * SIN U * SIN V. Using (i) twice on the right hand side, 4 * a * b * c * d = a * b * (1 + COS U) * c * d * (1 - COS V) + c * d * (1 + COS V) * a * b * (1 - COS U) + 2 * a * b * c * d * SIN U * SIN V. On simplifying, 4 = 2 - 2 * COS( U + V), which implies that U + V = pi and so the quadrilateral is cyclic. ("SQRT" means "square root of," "COS" and "SIN" are the trigonometric functions, and "pi" is the area of the unit circle.) ==== Note: as in this case, solutions to these problems appear attached to new problems a few days after posting. Bruce M. Bowden Sourcerer@delphi.com From: ua532@freenet.victoria.bc.ca (David Snook) Subject: Problem Sourcerer 1.212 {iams@quack.kfu.com (The Internet Amateur Mathematics Society)} (Problem 1 for February 12, 1994 from Sourcerer to the Internet Amateur Mathematics Society.) A MYSTERY This is a problem which seems to be without an easy solution, and it has a story behind it. A few days ago, David Snook (ua532@freenet.victoria.bc.ca) sent the following problem, which he had seen elsewhere and which was causing him a lot of annoyance: Of two numbers a and b is known that 1 < a < b <= 100 Mr. P knows the product of a and b Mr. S knows the sum of a and b [Aside from Bruce: assume that both know about the inequality above, but that Mr. P doesn't know the sum and Mr. S doesn't know the product.] Mr P and Mr S now have the following conversation. P: I dont know a or b. S: I already knew that. P: But then I know them. S: Now I also know what a and b are. David also sent me the solution in a and b, and that it's purported to be unique. What bothered David about the puzzle - and me as well, now that I've played with it - stems from the reasonable supposition that there's a trick or insight that yields the answer without very many steps. Well, David and I have wrestled with this, even trying to work backwards from the "unique" solution - but apart from a brute force search by computer (which both of us are loath to resort to) there seems no elegant answer. David writes: > My understanding is that the author did not have any knowledge of the solution when he originally posted the problem. He was relying on the rec.puzzles group to provide the solution. > When I queried him as to how the solution was derived. He replied that all of the other possible {P,S,a,b}'s had been removed by reduction. (He had not done it). That Three(3) other people had arrived at the same answer ..........ERGO it was correct. Besides, he noted the answer works. So, with David's blessing, I put the case before the membership. The question of the day, then, is: (a) give the values for a and b, and (b) show that this solution is unique. Tomorrow I'll supply the values of the sum and product, which were not given in the original statement of the problem, but may assist someone in discovering the secret of this perplexing mystery. If that isn't helpful, I'll conclude Monday with the values of a and b and a quick discussion. -------------- David, would also like to add: There is another perplexing problem with this puzzle. This deals with the notion of a "Single Unique Solution". IF from all of the possible (a,b) pairs, there exists one and only one that will meet the puzzle criteria, and that specific (a,b) pair is obtainable by reduction algorithms or formulae. (determinable) THEN Mr P or Mr S, or both, would simply apply the necessary procedures and obtain the required solution. (without dialogue). This strongly suggests that if there is a solution to the "Puzzle", there must exist a number (n>1) of (a,b) pairs, to permit the dialogue portion of the puzzle to have effect. Thanx, Dave -- David J. Snook.................................ua532@freenet.victoria.bc.ca From: "Jonathan Wildstrom" <95JWILDSTROM@vax.mbhs.edu> Subject: Re: IAMS' new domain/site Mike- I think that the basic idea of the moderation is to avoid the messages that don't belong there. Basically, I think Benjie's planning to delete the "unsubscribe" messages. The spoilers that don't point out that they're spoilers or don't leave blank lines. I think it's also planned to cut out messages that don't belong on the list (i.e. tangent subjects that don't deal with math or IAMS. I could be completely wrong, in which case, hopefully, Benjie will pop in to correct us both. ------------------------------------------------------------------ --Jon Wildstrom 95JWILDSTROM@vax.mbhs.edu OR Jon.Wildstrom@launchpad.unc.edu 'Provided enough men are penicillin-resistant' --Dr. Elwood Ralson, Asimov's short story 'Breeds There a Man...?' ------------------------------------------------------------------ From: SOURCERER@delphi.com Subject: Problem Sourcerer 2.212 (Problem 2 for February 12, 1994 from Sourcerer to the Internet Amateur Mathematics Society.) Let z = x + i * y be a complex number with x and y rational and with |z| = 1. Show that the number |z^(2 * n) - 1| is rational for every integer n. -------------- Solution to problem 1.207: "The three vertices of a triangle of sides a, b and c are lattice points and lie on a circle of radius R. Show that a * b * c G.E. 2 * R. (Lattice points are points in the Euclidean plane with integral coordinates. "G.E." means "greater than or equal to.")" For a triangle with sides a, b, c, area = A and circumradius = R we have a * b * c = 4 * R * A. But if the vertices are lattice points the determinant formula (or Pick's Theorem or direct calculation) for the area shows that 2 * A is an integer. Hence 2 * A G.E. 1, so that a * b * c G.E. 2 * R. To obtain the formula a * b * c = 4 * R * A note that if U is the angle opposite side a, then side a subtends an angle 2 * U at the center and a = 2 * R * SIN U, A = 1/2 * b * c * SIN U. ==== Solution for 1.207 in private correspondence on the same day from Csaba Gabor. ==== Note: as in this case, solutions to these problems appear attached to new problems a few days after posting. Bruce M. Bowden Sourcerer@delphi.com From: SOURCERER@delphi.com Subject: Problem Sourcerer 1.213 (1.212 revisit) (Problem 1 for February 13, 1994 from Sourcerer to the Internet Amateur Mathematics Society.) A MYSTERY - CONTINUED... In our last episode (yesterday): +++++++++ This is a problem which seems to be without an easy solution, and it has a story behind it. A few days ago, David Snook (ua532@freenet.victoria.bc.ca) sent the following problem, which he had seen elsewhere and which was causing him a lot of annoyance: Of two numbers a and b is known that 1 < a < b <= 100 Mr. P knows the product of a and b Mr. S knows the sum of a and b [Aside from Bruce: assume that both know about the inequality above, but that Mr. P doesn't know the sum and Mr. S doesn't know the product.] Mr P and Mr S now have the following conversation. P: I dont know a or b. S: I already knew that. P: But then I know them. S: Now I also know what a and b are. David also sent me the solution in a and b, and that it's purported to be unique. What bothered David about the puzzle - and me as well, now that I've played with it - stems from the reasonable supposition that there's a trick or insight that yields the answer without very many steps. Well, David and I have wrestled with this, even trying to work backwards from the "unique" solution - but apart from a brute force search by computer (which both of us are loath to resort to) there seems no elegant answer. David writes: > My understanding is that the author did not have any knowledge of the solution when he originally posted the problem. He was relying on the rec.puzzles group to provide the solution. > When I queried him as to how the solution was derived. He replied that all of the other possible {P,S,a,b}'s had been removed by reduction. (He had not done it). That Three(3) other people had arrived at the same answer ..........ERGO it was correct. Besides, he noted the answer works. So, with David's blessing, I put the case before the membership. The question of the day, then, is: (a) give the values for a and b, and (b) show that this solution is unique. +++++++++ Today, here are the values for the sum and product. S=17, P=52. -------------- Solution to problem 1.208: "F(x) is a real-valued function defined for all real x except for x = 0 and x = 1 and satisfying the functional equation F(x) + F{(x - 1)/x} = 1 + x. Find all functions F(x) satisfying these conditions. ;)" In the given equation (i) F(x) + F{(x - 1)/x} = 1 + x, substitute (x - 1)/x for x, obtaining (ii) F{(x - 1)/x} + F{-1/(x - 1)} = (2 * x - 1)/x. Also, in (i), substitute -1/(x - 1) for x and obtain (iii) F{-1/(x - 1)} + F(x) = (x - 2)/(x - 1). Adding (i) and (iii) and subtracting (ii) gives (iv) 2 * F(x) = 1 + x + (x - 2)/(x - 1) - (2 * x - 1)/x = (x^3 - x^2 - 1)/{x * (x - 1)}. F(x) = (x^3 - x^2 -1)/{2 * x * (x - 1)}. That F(x), defined in (iv), satisfies the given functional equation is easily verified. So (iv) is the only solution of the problem. ==== Solutions to 1.208, on the same day, received in private correspondence from Csaba Gabor, Arthur Rubin and David W. Wilson. Arthur Rubin and David W. Wilson used composite functions in their solutions. Here's how Arthur Rubin did it: >If f(x)=(x-1)/x, then f(f(f(x)))=x. So, >F(x) + F(f(x)) = 1 + x >F(f(x))+F(f(f(x))) = 1 + f(x) >F(f(f(x))) + F(x) = 1 + f(f(x)) > >Hence F(x) = (1 + x -f(x) + f(f(x)))/2 = (x^3-x^2-1)/(2x(x-1)). ==== Note: as in this case, solutions to these problems appear attached to new problems a few days after posting. Bruce M. Bowden Sourcerer@delphi.com From: vhansen@ipf.bau-verm.uni-karlsruhe.de (Wolfgang von Hansen) Subject: probability question (dices) Hi! I have the following question: You roll a k-sided dice n times. What is the mean value of the lowest score? Wolfgang From: SOURCERER@delphi.com Subject: Problem Sourcerer 2.213 (Problem 2 for February 13, 1994 from Sourcerer to the Internet Amateur Mathematics Society.) Consider an integer p > 1 with the property that the polynomial x^2 - x + p takes prime values for all integers x in the range 0 L.E. x < p. (Examples: p = 5 and p = 41 have the property.) Show that there is exactly one triple of integers a, b, c satisfying the conditions: b^2 - 4 * a * c = 1 - 4 * p, 0 < a L.E. c, -a L.E. b < a. ("L.E." means "less than or equal to.") -------------- Solution to problem 1.209: "Two cars travel around a track at equal and constant speeds, each completing a lap every hour. From a common starting point, the first starts at time t = 0 and the second at an arbitrary later time t = T > 0. Prove that there is a total period of exactly one hour during the motion in which the first has completed twice as many laps as the second." At time t, car 1 has completed [t] laps and car 2 has completed [t - T] laps. The problem is to find values of t G.E. T for which [t] = 2 * [t - T]. Let T = k + d, where 0 L.E. d < 1, k an integer. Consider any integral interval [m, m + 1] and let m L.E. t < m + 1. Then t = m + h, where 0 L.E. h < 1. The equation to be solved becomes [t] = m = 2 * [t - T] = 2 * [m + h - (k + d)] = 2 * [m - k + h - d]. Thus m = 2 * (m - k), if h G.E. d and m = 2 * (m - k - 1) if h < d. If 1 > h G.E. d, then m = 2 * k and the equation is satisfied during [2 * k + d, 2 * k + 1], which has length 1 - d. If 0 L.E. h < d, then m = 2 * k + 2 and the equation is satisfied during [2 * k + 2, 2 * k + 2 + d], which has length d. Therefore the total length is 1 - d + d = 1. ("L.E." means "less than or equal to" and "G.E." is "greater than or equal to.") ==== Note: as in this case, solutions to these problems appear attached to new problems a few days after posting. Bruce M. Bowden Sourcerer@delphi.com From: SOURCERER@delphi.com Subject: Mystery Puzzle Reply 2 The Mystery Problem - Second Reply The following analysis concerning 1.212 in private correspondence from Kermit Rose (rose@garnet.acns.fsu.edu): ==== > > (Problem 1 for February 12, 1994 from Sourcerer to the Internet > Amateur Mathematics Society.) > > A MYSTERY > > This is a problem which seems to be without an easy solution, and it > has a story behind it. A few days ago, David Snook > (ua532@freenet.victoria.bc.ca) sent the following problem, which he > had seen elsewhere and which was causing him a lot of annoyance: > > Of two numbers a and b is known that 1 < a < b <= 100 > Mr. P knows the product of a and b > Mr. S knows the sum of a and b > > [Aside from Bruce: assume that both know about the inequality above, > but that Mr. P doesn't know the sum and Mr. S doesn't know the > product.] > > Mr P and Mr S now have the following conversation. > P: I dont know a or b. Now We know that p is not a number that can not be factored uniquely into two factors. That is, P has at least 3 prime factors. At least one of a and b must be not prime. > S: I already knew that. Knowing the sum of a and b tells S that P cannot determine from the product what a and b are. That is a+b is not the sum of two primes, or one more than a prime. Thus a+b is one of 11,17,23,27,29,35,37,41,47,51,53,57,59,65,67,71,77,79,83, 87,89,93,97 101,107,113,117,119,121,123,125,127,131,135,137,143,145,147,153, 155, 57,161,163,167,171,173,177,179,185,187,189,191,197 > P: But then I know them. Now P discovers that Knowing the sum of a and b proves that the product is not enough information to figure out a and b. This information with the knowledge of the product tells P what a and b are. That is, P knows that only one of the above numbers have summands a+b such that ab is P. a+b is one of 11,17,23,27,29,35,37,41,47,51,53,57,59,65,67,71,77,79,83, 87,89,93,97 101,107,113,117,119,121,123,125,127,131,135,137,143,145,147,153, 155, 57,161,163,167,171,173,177,179,185,187,189,191,197 For example P cannot be 30 because both 6+5 and 2+15 are in the list. Only a small number of products satisfy this criterion. I do not at this time see a simple systematic way to list them. > S: Now I also know what a and b are. All except one product will correspond to mutiple sums. S looks at the possible products and chooses the only one in the product list that yields his sum. The fact that he can do this tell us what the sum is. ==== In my own correspondence with Dave Snook on this problem last week, I said: I think that I can safely assume from the wording that although P and S knew the relationship 1 < a < b <= 100, the only other information they had to start with was the sum, known only by Mr. S, and the product, known only by Mr. P. Well, after thinking about the problem so far, it's clear how Mr. S was able to determine the values of a and b given that Mr. P couldn't. Mr. S knew what the possible values of a and b for his sum were, and that these values, when multiplied together, gave no pair of prime factors. Working from the product, Mr. P knew that a and b could either be (4, 13) or (2, 26), but he didn't know which. Mr. S's observation, however, told Mr. P that there was no pair of prime factors and Mr. P also knew that the sum of 2 and 26, if that had been Mr. S's number, could be split into 5 and 23. Since Mr. S said that he already knew that Mr. P couldn't determine a and b, Mr. S must have not have had to worry about 5 * 23, hence his sum was NOT 28. That just left 17, or 4 and 13. When P figured that out, and said he knew what a and b were, S applied the same reasoning as I have and knew as well. :) To actually arrive at the original combination of 17 and 52 (and the other three), requires a little more thought... :D ==== Bruce M. Bowden Sourcerer@delphi.com From: SOURCERER@delphi.com Subject: Mystery Puzzle Reply 1 The Mystery Problem - First Reply The following interesting private correspondence concerning 1.212 from Sylvan Jacques (van@quack.kfu.com), with a program for a brute-force search by Jeff Kenton (jkenton@world.std.com): ====== The sum/product problem from the rec.puzzle FAQ. (I also have some posts made by someone else who is good with kind of puzzle, but they don't agree with the first solution, but the 2nd, SUM PRODUCT X Y 29 208 13 16 the same as below when numbers less than 3 are excluded. ==> 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); } ==== Passed along by Bruce M. Bowden Sourcerer@delphi.com From: SOURCERER@delphi.com Subject: Problem Sourcerer 1.215 (Problem 1 for February 15, 1994 from Sourcerer to the Internet Amateur Mathematics Society.) Call a set of positive integers "conspiratorial" if no three of them are pairwise relatively prime. (A set of integers is "pairwise relatively prime" if no pair of them has a common divisor greater than 1.) What is the largest number of elements in any conspiratorial subset of the integers 1 through 16? -------------- Insights to the "P & S" problem in private correspondence from Kermit Rose, who steps through the problem as given and makes the following comments: ab is not prime or the product of two primes. (a+b) is not the sum of two primes. Exactly one of the pairs of proper factors x,y whose product xy = ab sum to a number (x+y) which is not a sum of two primes. Consider all products of zw where z+w = a+b. Exactly one of these products zw have the property above. Namely, that exactly one of the pairs of proper factors x,y whose product xy = zw sum to a number (x+y) which is not the sum of two primes. It seems likely that the original puzzle had the restriction that the product was >1 and < 100. A later version made the range restriction for a and b instead of for the product. -------------- Solution to problem 1.210: "Let n be a fixed positive integer and let b(n) be the minimum value of k + n/k as k is allowed to range through all positive integers. Prove that b(n) and SQRT(4 * n + 1) have the same integer part." Let c(n) = SQRT(4 * n + 1) and let [x] denote the greatest integer in x; then we wish to show that [b(n)] = [c(n)]. Let k(n) be a value of k that minimizes k + (n/k). Then b(n - 1) L.E. k(n) + {(n - 1)/k(n)} < k(n) + {n/k(n)} = b(n), i.e., b(n - 1) < b(n). Let m be a positive integer. Then (I) b(m^2) = 2 * m, b(m^2 + m) = 2 * m + 1. It follows from formulas (I) and the strictly increasing nature of b(n) that (II) [b(n)] = 2 * m for m^2 L.E. n < m^2 + m, [b(n)] = 2 * m + 1 for m^2 + m L.E. n < (m + 1)^2. On the other hand, c(n) is also an increasing function and c(m^2 - 1) = SQRT(4 * m^2 - 3) < 2 * m, c(m^2) = SQRT(4 * m^2 + 1) > 2 * m, c(m^2 + m) = SQRT(4 * m^2 + 4 * m + 1) = 2 * m + 1. These facts show that (II) remains true when [c(n)] is substituted for [b(n)]. ==== Note: as in this case, solutions to these problems appear attached to new problems a few days after posting. Bruce M. Bowden Sourcerer@delphi.com From: Sylvan Jacques Subject: Sum--product Problem 1.212 I sent a letter to SOURCERER@delphi.com about the sum/product problem with the interval being [3,97] or [3,100] instead of [2,100], which changes things. Its a long letter with a soln. by a mathematician on Genie. Anyone who wants it please let me know. The post of Kermit Rose (rose@garnet.acns.fsu.edu) cleared things up a lot for me. Thanks :) Van van@quack.kfu.com From: csaba@teleport.com (Csaba Gabor) Subject: Re: Probability Problem Could you please be a little more explicit about what it means to choose an integer at random. You can not have a uniform distribution over all the integers. Csaba Hello everyone! It's my opinion that the people able to solve this problem and understand its solution, hav