Integer triangles on a grid

Probability Level 4

How many distinct integer triangles can be placed on a 40 x 40 grid if their vertices are required to be on grid intersections? A distinct integer triangle is a triangle with integer sides expressed as an unordered tuple. i.e. a (3,4,5) triangle is the same as a (4,3,5) triangle. As an example, there are only two such triangles on a 7x7 grid.

Bonus: Generalize to $n \times n$ grid.

The answer is 69.

1 solution

David Vreken
Oct 18, 2020

The following Python computer program uses brute force to find $\boxed{69}$ distinct integer triangles:

# Integer Triangles on a Grid
# Python

import math

# determine if a number is a perfect square
def issqu(x):
    return (int(math.sqrt(x))) ** 2 == x

n = 40
sideslist = []

# pick two other points on the grid (labeled
#  numbers 0 through n**2) a and b
for a in range(1, n ** 2):
    # convert grid number to coordinates
    ax = (a - a % n) / n
    ay = a % n
    for b in range(a + 1, n ** 2):
        # convert grid number to coordinates
        bx = (b - b % n) / n
        by = b % n
        # find the square of each side of a triangle
        #   formed by (0, 0), (ax, ay), and (bx, by)
        s1_2 = (ax - bx) ** 2 + (ay - by) ** 2
        s2_2 = ax ** 2 + ay ** 2
        s3_2 = bx ** 2 + by ** 2
        # if all sides are integers, sort them in order
        if issqu(s1_2) and issqu(s2_2) and issqu(s3_2):
            sides = [int(math.sqrt(s1_2)), int(
                math.sqrt(s2_2)), int(math.sqrt(s3_2))]
            sides.sort()
            # make sure the sides form a triangle (and
            #  not a straight line) and make sure the
            #  sides haven't been counted already
            if sides[2] < sides[0] + sides[1] and (
                sides not in sideslist):
                sideslist.append(sides)

# display the results            
print(len(sideslist))

When I wrote the problem, I had hoped for a combinatoric solution, but I doubt that is likely now. It's just too hard. My solution is similar to yours, but not written as cleanly. Thanks for taking the time to answer this. Nice code.

Fletcher Mattox - 7 months, 3 weeks ago

I first tried a combinatoric solution, too, but it got too complicated for me. Maybe someone else will write a solution using that method.

David Vreken - 7 months, 3 weeks ago

interesting problem. I see an issue with your answer 69. Triangle [13,40,45] is a member of the solution set that your code counts as valid. I do not believe that it is possible to place that triangle on a 40X40 grid. A maximum length 39 is possible between the 1st and the 40th grid intersections. If [13,40,45]is valid then what about [30,40,50] , [29,29,40], [9,40,41] that could also be placed on a grid with 41 intersections i.e. 40 unit spaces between the intersection points. I believe that 68 is the correct answer when the grid is 40X40 intersection points.

Darryl Dennis - 7 months, 3 weeks ago

The triangle with vertices $A(0,0),B(36,27),C(24,32)$ has sidelengths $(13,40,45)$ and fits on the grid.

Chris Lewis - 7 months, 3 weeks ago

@Chris Lewis – OK my mistake I missed that possibility. thanks

Darryl Dennis - 7 months, 3 weeks ago

@Chris Lewis is correct. Also, if you add the line "print(sides, (0, 0), (ax, ay), (bx, by))" between lines 37 and 38 and then run the program it will show one set of coordinates for each set of sides found.

David Vreken - 7 months, 3 weeks ago

I did this by code as well. There seems to be a bit of a pattern if you look at the average number of triangles as $n$ increases - that is, if it's possible to draw $T(n)$ distinct triangles with integer sides on an $(n \times n)$ grid, $\frac{1}{n} \sum_{r=1}^{n} T(n)$

looks reasonably smooth (it's almost, but not quite, quadratic in $n$ ).

I used a slightly different code so it might be useful to double-check some values; I found $T(20)=18$ , $T(30)=42$ , $T(50)=122$ and $T(100)=397$ . Do these agree with yours?

Chris Lewis - 7 months, 3 weeks ago

Nice observations! And yes, I found all of the same values as you did for T.

David Vreken - 7 months, 3 weeks ago

Great, thanks for checking. Just a few more thoughts: the way I set up my code was to start with a small grid, then gradually increase the grid size. If a particular triangle is possible in an $n \times n$ grid, but not in an $(n-1) \times (n-1)$ grid, two of its vertices would have to be on opposite edges of the grid; ie they'd have coordinates $(0,a)$ and $n,b)$ for some $a$ and $b$ (in fact we can take $a=0$ wlog). (It's still necessary to check each triangle is "new".) This meant fewer points to scan overall, as there weren't as many (say) $3,4,5$ triangles to count, and also (helpfully) built a list of $T(n)$ values along the way. So this could lead to a kind of induction argument.

There are three types of triangle to count: those with two sides parallel to the coordinate axes; those with one side parallel; and those with none. It might help to consider these separately for counting purposes, except...

...the fly in the ointment with both of these is that it's possible for the same triangle to appear in more than one orientation. For example, the triangles with vertices $(0,0),(15,0),(0,20)$ and $(0,0),(9,12),(25,0)$ have the same sidelengths, so there's a risk of double-counting.

So far I've only really looked at counting the triangles by scanning gridpoints. An alternative would be to scan all possible distinct triangles with integer sides to see which fit on gridpoints. I guess for each triangle that can fit on gridpoints, there's a smallest $n \times n$ grid that it can go on; but I'm not sure if this is a helpful approach.

Chris Lewis - 7 months, 3 weeks ago

Fine problem. Try to add T(1),T(2)....... in https://oeis.org/

Yuriy Kazakov - 7 months, 3 weeks ago

Integer triangles on a grid

The answer is 69.

1 solution

0 pending reports