No Isosceles Triangles For You!

Riddler Classic

This week’s Classic is being served up by Jordan Ellenberg, whose new book, “Shape,” goes on sale on May $25$.

One of the many geometers who appears in “Shape” is the great Paul Erdős. In $1946$, Erdős himself posed a riddle about what are called “isosceles sets”: How many points can you place in d-dimensional space such that any three of them form an isosceles triangle?

In two dimensions, the largest isosceles set has exactly six points, with five forming the vertices of a regular pentagon and the sixth point in the middle. In three dimensions, the largest isosceles set has eight points; in four dimensions, the largest set has $11$ points. And in dimensions higher than eight, no one knows what the largest isosceles sets might be!

But this week, Jordan is asking about what he calls anti-isosceles sets. Consider a $N×N$ grid of points. What is the greatest subset of these $N^2$ points such that no three of them form an isosceles triangle? (Note: Degenerate triangles, or triangles with zero area, do count as triangles here, as long as their three vertices are distinct.)

How many points are in the largest anti-isosceles set for a $4×4$ grid?

Extra credit: What about a $5×5$ grid, a $6×6$ grid, or even larger square grids? Can you find an expression (or bounds) for the size of the largest anti-isosceles set for the general $N×N$ grid? (If you figure out anything about the general case, Jordan would love to hear about it!)

Computational Solution

from itertools import product, combinations
from copy import deepcopy

def isoceles(t):
    def d(p1, p2):
        return (p1[0]-p2[0])**2 + (p1[1]-p2[1])**2
    d1, d2, d3 = d(t[0], t[1]), d(t[1], t[2]), d(t[2], t[0])
    if d1 == d2 or d2 == d3 or d3 == d1:
        return True
    else:
        return False

n = 5
grid = product(*[range(n)]*2)
max_size = 6
cur_size = max_size + 1
max_pts_set = []
while True:
    cur_size_largest = False
    pts_set = []
    for pts in combinations(grid, cur_size):
        if all([not isoceles(t) for t in combinations(pts, 3)]):
            cur_size_largest = True
            pts_set.append(pts)          
    if not cur_size_largest:
        break
    else:
        max_size = cur_size
        cur_size += 1
        max_pts_set = deepcopy(pts_set)
print(max_size, max_pts_set)

Anti-isoceles sets for $4\times4$ grid

Anti-isoceles sets for $5\times5$ grid