Date: Wed, 19 Apr 1995 20:23:43 +1200 From: Karl Scherer Subject: Re: easy (?) triangle problem To: Dave Rusin Hi Dave, thanks for your reply. The origin of the problem is my book "Nutts and other Crackers" which I am writing at the moment and which is to become my second book on puzzle and geometrical problems. I found the problem (and related ones) myself and have not seen anything related published anywhere. My first book is on irregular rep-tiles and is called "A Puzzling Journey to the Reptiles and Related Animals", due to be published by MathPro Press, Westford, MA end of this year. No, not all integral triangles on the grid can be positioned with one side parallel to the coordinate axis. The exceptions, which I call the "truly tilted" cases, are of two different types. Here just one example: A(0,0), B(3,-4), C(21,20) with side lengths 5, 29 and 30. Or take A(0,0), B(15,8) C(48,64) with sides 17,65,80. The existence of these "truly tilted" cases make the problem worth stating! Otherwise (if you always could place an integral lattice trianlge with one side on the coord. axis) shrinking would obviously keep the triangle on the grid. Keep on trying... Cheers, Karl ============================================================================== Date: Wed, 19 Apr 1995 20:36:48 +1200 From: Karl Scherer Subject: Re: easy (?) triangle problem To: Dave Rusin Correction to my previous letter: I take back the sentence containing the word "obviously". Fact is, that there are triangles of type n*T on the grid with one side parallel to the coord axis, but T can only be positioned on the lattice in a tilted way. (Can you find an example?). Bye, Karl ============================================================================== Date: Wed, 19 Apr 95 09:24:22 CDT From: rusin (Dave Rusin) To: karl@kiwi.gen.nz Subject: Re: easy (?) triangle problem >No, not all integral triangles on the grid can be positioned with >one side parallel to the coordinate axis. >The exceptions, which I call the "truly tilted" cases, are of two >different types. >Here just one example: A(0,0), B(3,-4), C(21,20) >with side lengths 5, 29 and 30. >Or take A(0,0), B(15,8) C(48,64) with sides 17,65,80. I realize this -- you can't tilt them _integrally_, but you can always tilt them _rationally_. Your first example may be rotated with the matrix ( 3 -4 ) (1/5)( ) ( 4 3 ) so that the edge AB is on the x-axis. Of course this gives C rational coordinates. This is what I had in mind: your initial premise was really nothing more nor less than that the triangle had integral edges, one from the origin along the positive x-axis, the other two meeting at a point (x,y) whose rational coordinates meet some number-theoretic conditions; then the question is whether another rotation gives the triangle integral coordinates. Did you know there's algebraic number theory lurking in here? A rational rotation is multiplication by a complex number z/zbar where z = a+ib with a and b integers (and zbar=a-ib). Since the ring Z[i] of Gaussian integers admits unique factorization into primes, the only rotations which will swing (a,0) to an integral point will be multiplication by z/zbar where zbar is a divisor of a+0i in this ring. Your first example, for instance, has AB of length 5, so if you begin with it on the horizontal axis, the only rotations which will move it to other integral points involve the divisors of 5, which factors into primes as (3+4i)*(3-4i) (decomposition is unique up to order and multiplication by units +-1 and +-i). So here's the way I see the problem. You're given a triangle in the complex plane with vertices at 0, a, and x+iy (x, y rational, a integral). The length of the side from 0 to x+iy is also an integer, b. You need to find a rotation z/zbar carrying these to integral points A and B respectively. Well, A and B will have to be divisors in this ring of a^2 and b^2 respectively, in fact, you need a^2=A*Abar, b^2=B*Bbar. Since we are also asking that A = a*z/zbar, this amounts to showing that we can pair off the complex divisors of a and b in such a way as to produce the number x+iy. The reason I didn't post this, or even pursue it, is that you definitely need the condition that the third side have rational length, and I don't see an easy way to incorporate that into this analysis. Anyway, if you have a proof that there always is an integral embedding of the triangle, I'd like to see it.. dave