Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

To preface I am not entirely sure lattice is the correct word for this but my "research" on the question makes it seem like that is a good way to phrase the question. Just to highlight my experience I am currently taking "calculus 2" and a discrete/foundations of math course but I don't mind going outside of that zone of knowledge to figure out the problem. I am not looking for a program that iterates through points finding which triangles are right and which are not.

For simplicity I will only be talking about the square lattice. The triangles in question can only have their vertices on lattice points.

What I have done so far:

  • Found the number of ways to place points. If there are $n$ points its $n \choose 3$.
  • The amount of right triangles where the right angle is aligned with rows and columns. $n (p-1)^2$. $n$ is the amount of points that could be the vertices of the right angle and each $(p-1)$ is the amount of points left to choose from.

I am not really sure what to do from here. I have had a few thoughts though. I looked to see if finding the amount of rectangles and somehow connecting it to the amount of triangles would be easier, but to get all the triangles there would be some rectangles that were partially outside the lattice. I have also thought that maybe there is someway to find all the right triangles that could not be made by other ones(in the lattice) and maybe that could lead to a way to say how many there are. There is of course "how many are not right?" question but I do not know how I would find that. I have also tried using perpendicular lines but not really sure how to apply that idea to get the amount of right triangles.

share|improve this question
    
I do not know if it helps, but a triangle is right if and only if its hypotenuse is a diameter of the circumcircle. –  dtldarek Apr 14 '12 at 22:51
    
The number of triangles is not right. Your $3$ points could be on the same slanty line. Counting right triangles whose right angle is not in the "obvious" places is a difficult number-theoretic problem, best one can hope for is a good estimate. –  André Nicolas Apr 14 '12 at 22:55
    
You've got $p$, and you've got $n$. In fact, $n=p^2$, right? –  Gerry Myerson Apr 14 '12 at 22:56
    
The distinct points $(a,b),(c,d),(e,f)$ form a right triangle with a right angle at $(c,d)$ if and only if $(a-c)(e-c)+(b-d)(f-d)=0$, so you're looking for the number of solutions to this diophantine equation with all variables between 1 and $n$. I don't know how hard the analysis would be. Another approach is to calculate the answer for, say, $n=2,3,4$ and then look up the result in the Online Encyclopedia of Integer Sequences. –  Gerry Myerson Apr 14 '12 at 23:02
1  
@Gerry: OEIS also has text search :-) This is OEIS sequence A077435. For a rectangular grid, OEIS sequence A189814. –  joriki Apr 15 '12 at 6:01
show 2 more comments

1 Answer

up vote 3 down vote accepted

I think it was a mistake to look at the square case "for simplicity". The rectangular case is more approachable, because one can get a meaningul result by fixing the height $k$ and considering the dependence on width $n$. The simplest case is $n\times 2$, which yields $$4\binom{n}{2} +2(n-2) $$ right triangles. R. H. Hardin observed empirically that for every $k$ there exists $n_0$ such that the number of right triangles is a quadratic function of $n$ when $n>n_0$. (The links to relevant OEIS data: A077435 for square grid and A189814 for rectangular, were found by joriki).

This suggests some lines of investigation (I think these three are in increasing order of difficulty):

  1. Prove the existence of $n_0$ and give an estimate for it.
  2. Find a formula for the $n^2$ coefficient (as a function of $k$) and prove it.
  3. Same for the $n^1$ and $n^0$ coefficients.

In general, the problem is very hard. The $50\times 50$ case, greatly simplified by fixing one vertex of a triangle, was Euler project problem 91.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.