No Isosceles Triangles For You!

A FiveThirtyEight Riddler puzzle.

By Vamshi Jandhyala in mathematics Riddler

May 21, 2021

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
        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
    if not cur_size_largest:
        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