From: [Permission pending] Newsgroups: sci.math Subject: easy (?) triangle problem Date: 10 Apr 1995 20:33:07 GMT [Post contents erroneously put in Keyword: field -- djr] I hope someone can help me with this. . Let T be a triangle with integral sides a,b,c. Let n be a natural number such that the enlarged triangle n*T can be placed on the lattice grid, i.e. all its vertices then have integral coordinates.: Can we conclude that T itself can be placed on the lattice: grid? Prove it or find a counterexample. Please send all answers to my email address [Permission pending], since I do not have access to the newsboard all the time. Thanks. [sig deleted -- djr] ============================================================================== Date: Fri, 21 Apr 1995 15:57:15 +1200 From: [Permission pending] Subject: Re: easy (?) triangle problem To: Dave Rusin Thank you very much for your comments. If you like triangle problems, here are three of which the first one I have solved. You might be able to find proofs for the other two cases. Take a triangle T=ABC with integral sides a=BC, b=AC, c=AB. Let h be the height from C onto c. Assume A is isosceles : a=b. Now assume that additionally we have one of the following three cases: (All symbols except h denote integers > 0). a) A=(x,0), B=(-u,v), C=(0,0) b) A=(-x,y), B=(u,v), C=(0,0), y<>v. c) A=(x,y), B=(u,v), C=(0,0), x1 or provide a counterexample. Have fun! Cheers, Karl ============================================================================== Date: Fri, 21 Apr 95 10:58:19 CDT From: rusin (Dave Rusin) To: [Permission pending] Subject: Re: easy (?) triangle problem >If you like triangle problems, here are three of which the first one I have >solved. You might be able to find proofs for the other two cases. > >Take a triangle T=ABC with integral sides a=BC, b=AC, c=AB. >Let h be the height from C onto c. >Assume A is isosceles : a=b. You then assume A, B, and C are integral points, (and C=(0,0) ) and ask whether h is integral. The answer is always yes, independent of any other conditions you set. I can answer this question pretty completely using the Gaussian integers Z[i]. It turns out that the isoceles condition makes some things a square Gaussian integer, which will allow the extraction of square roots. This is the extra kind of information which was not available in the previous problem you posted. If A=(x,y), we consider the Gaussian integer z=x+iy. Every Gaussian integer may be uniquely decomposed into a product z = u Prod(p_i^e_i) where u is a unit (+-1 or +-i) and each p_i is a first-quadrant prime (p_i = a+bi with a>0 and b>=0.) Note that the length b of the line segment AC is the magnitude of the complex number z, which is the square root of z*zbar, which is in turn the product Prod(p_i*p_i-bar)^e_i. Now, each p_i*p_i-bar is an ordinary prime unless p_i itself is real (e.g. p_i=3+0i is a prime Gaussian integer; 5+0i = (2+i)(2-i) is not). We conclude that the length b is integral iff each of the non-real primes occuring in z occurs to an even exponent. In particular, b is integral iff z = u s^2 n for some Gaussian integer s, some ordinary integer n, and u = a unit; then b is the integer (s*sbar)*|n|. The decomposition is unique if we assume n > 0, n has no complex divisors, and s has no real prime divisors. Now you assume an isoceles triangle, so that B=(u,v) where w=u+iv is another Gaussian integer which is again of the form w = u' t^2 m, but with the same length a = b, that is, (s*sbar)*|n| = (t*tbar)*|m|. With s and n chosen to make the representation unique, and likewise t and m, we find the m=n and s*sbar=t*tbar. It follows that there exist complex integers q and r so that s = q*r and t = q*rbar (q is the gcd of s and t). This then is the recipe for creating integral triangles with two equal integral sides: the vertices must be of the form z = u q^2 r^2 m and w = u' q^2 rbar^2 m for some Gaussian integers q and r and a real integer m > 0; u and u' are +-1 or +-i. Note that the midpoint of the side joining these vertices is then q^2 m (u r^2 + u' rbar^2)/2 The length of this side involves the factors (q*qbar) |m| so that in general there is a gcd with the length b, if the lengths are integral. Likewise the length c of the third side is the magnitude of the complex number q^2 m (u r^2 - u' rbar^2). We can factor out the u and let u'' = u'/u (also a unit); we find we need to investigate r^2 +- rbar^2 and r^2 +-i rbar^2. Writing r = a + bi we have rbar = a - bi, and the squares are (a^2-b^2) +- 2ab i. We distinguish the four cases: u''=1: r^2-rbar^2 = 4abi while (r^2+rbar^2)= 2(a^2-b^2). One is real, the other pure imaginary, but both imply the length will be integral. u''=-1: This just reverses the roles in the previous case. Likewise u''=-i will be the reverse of the following case: u''=i: (r^2-i rbar^2) = (a^2-b^2+2ab) + (-a^2+b^2+2ab) i and (r^2+i rbar^2) = (a^2-b^2-2ab) + (a^2-b^2+2ab)i. The lengths of these numbers are, respectively, the square roots of 2(a^2+2ab-b^2)^2 and 2(a^2-2ab-b^2)^2, which are never integral. Thus the length of the side c is rational iff the length h of the bisector is rational iff u'' is real. We're almost done: the only issue left is passing from rationality to integrality -- there is a "2" in the formula for h which we need to address -- but the formulas listed above for u''=1 or -1 include a 2 as well, so h will indeed be integral. dave ============================================================================== Date: Mon, 24 Apr 1995 11:09:17 +1200 From: [Permission pending] Subject: Re: easy (?) triangle problem To: Dave Rusin Thank you for your letter. You wrote: "You then assume A,B,C are integral points, and ask whether h is integral. The answer is always yes, independent on the conditions you set." Well, this is definitely wrong. Look at the two examples I sent you. They both have A,B,C on integral points, but no height is an integer. Hence the general case is more complicated. Did I or you miss something here? ============================================================================== Date: Mon, 24 Apr 1995 13:31:18 +1200 From: [Permission pending] Subject: Re: easy (?) triangle problem To: Dave Rusin Dear Dave, I have now read through your proof. I am not extremely familiar with Gaussian number theory (my field was mostly sheaves and bundles), so could you please help me clarify a point. At first glance your writing seems to prove that there is ALWAYS a gcd(h,c,a), namely q*qbar*m. Well, the sides of the triangle do not always have a common divisor. This is why I sent you the special conditions which will enforce it. Now if there is no common divisor, we should be able to prove (using your notation) that one side of the triangle is then parallel to a coordinate axis (which is the only position not covered by my setup). Can you tell me exactly how your argument works in this case? It might be simple for you, but please do me the favour and explain. Thanks again for the excellent proof. I will not make use of it in my book, because the problem of the isosceles triangles is only mentioned at the side, but I will send the problem to JORM (Journal of recreational mathematics) and I will cite your name and your solution. Looking forward to your reply.. Karl ============================================================================== Date: Wed, 26 Apr 1995 16:37:27 +1200 From: [Permission pending] Subject: Re: easy (?) triangle problem To: Dave Rusin Meanwhile I have tried to solve my last question myself and have found the answer. If z and w do not have a common factor, then z=r^2 and w=u"rbar^2. Now according to your analysis, u" can only be 1 and -1 (that's what I had overlooked, and we need it here again!). Hence with r=a+bi we get A=(a^2-b^2,2ab) and B=+-(a^2-b^2,-2ab), showing that c is parallel to a coordinate axis. Hence, if we call a triangle with gcd(a,b,c)=1 prime, we may say: If T is a prime isosceles triangle on the lattice, then its hypotenuse is parallel to a coordinate axis, and its height on c is an integer. I am still working on the original, more diffficult problem (If a multiple of an integral triangle is on the lattice, then so is the triangle itself.) Did you make any progress on this one? I find this conjecture quite intrigueing. I would love to have some sort of result on this, because this is the last stumbling block in my book. Thank you so much for your help!! If you are interested, both my books are for sale (US$30.- incl postage, both together for US$50.-) as private copies. Martin Gardner has read my first book (A Puzzling Journey to the Reptiles and Related Animals) and he highly recommends it. It is written as a fiction story and contains more than 300 drawings, containing more than 100 new and unpublished problems connected with repetitive tilings. All sorts of theoretical and practical problem in connection with irregular self- tiling shapes are covered. Very educational, but also containing some very deep and difficult questions. 150 pages, A4 format, bound. My second book contains mare than 300 pages. If you are interested, send me a cheque to 2-63 Rangatira Road, Auckland 10, New Zealand. I invent and sell silverplated wire Puzzle Pendants as well. (have you heard of the International Puzzle Party; last time in Seattle, sold quite a lot there.) Bye for now... Karl ============================================================================== Date: Thu, 27 Apr 1995 15:56:22 +1200 From: [Permission pending] Subject: Re: easy (?) triangle problem To: Dave Rusin Hi Dave, first a little note: I think that two of the formulas you gave in your proof are wrong. On the last page, for case u"=i, I find r^2-i rbar^2 = (a^2-b^2-2ab) + ...instead of (a^2-b^2+2ab)+... and r^2+i rbar^2 = (a^2-b^2+2ab) + ... instead of (a^2-b^2-2ab)+... This makes the lengths equal to (a^2-b^2-+2xy)*sqrt(2), where "-" used for u"=i, "+" for u"=-i. Please correct me if I am wrong. The same of argument still holds, of course. But I hit another, more serious problem. I agree with you that c is rational iff c is an integer iff h is an integer iff h is rational iff u" is real. But I could not prove yet that gcd(a,c)>1 implies gcd(a,h,c)>1, and that gcd(a,c)=1 implies that c is parallel to a coordinate axis. _ If m(qq) would be equal to gcd(a,c), there is nothing to show. But common factors might be hidden in the r-part of both numbers. _ _ 2 _2 _2 2 Even if m(qq)=1, a = rr and c=sqr( r -u"r )(r -u"r ) might have common factors without h having the same factor (I believe the opposite, but can we prove it???) Would you mind elaborating on this? Thank you very much. Karl ============================================================================== Date: Fri, 28 Apr 1995 02:19:33 +1200 From: [Permission pending] Subject: Re: easy (?) triangle problem To: Dave Rusin Hi Dave, thanks for your message. Please don't bother answering my questions to the isosceles triangles problem, I have sorted them out myself meanwhile. The trick is that Pythagoras leads to immediate answers concerning the gcd parts. I was looking for proofs with Gaussian integers, which makes that+ bit unnecessarily complicated. The short proofs go as follows: If gcd(a,c)>1, then (since c is even) either gcd(a,c/2)>1 or gcd(a,c)=2 . In the first case, for a prime p whcih divides gcd(a,c/2), 2 2 2 p divides h = a -(c/2) , hence p divides h and gcd(a,c,h)>1. In the second case we find that a is even. 2 2 2 But then a = h +(c/2) is divisible by 4, which is only possible if h and c/2 are even, hence again gcd(a,c,h)>1. Now assume gcd(a,c)=1. Then n=1, q=1. Hence 2 2 a = x +y and either 2 2 z-w = 4uxyi or z-w = 2u(x -y ) In both cases c is parallel to a coordinate axis. Besides, gcd(a,c)=1 also implies gcd(a,c/2)=1, so that from equation 2 2 2 a = h + (c/2) we conclude gcd(a,h)=1=gcd(h,c/2). Note that gcd(h,c)=1 is not generally true, since both c and h can be even, even if gcd(a,c)=1 ! Thanks again for your help. I will now send the problem to the Journal of Recreational Mathematics. If you find some more interesting facts on Integral Geometry, let me know. Bye, Karl ==============================================================================