No Isosceles Triangles For You!

Riddler Classic

In an $N\times N$ grid of points, an “anti-isosceles” set is one in which no three points form an isosceles triangle, where degenerate (collinear) triangles count too. How large can such a set be on a $4\times 4$ grid? Extra credit: on a $5\times 5$, $6\times 6$, or larger grid?

Solution

A triple of points is isosceles exactly when two of its three pairwise distances are equal, so an anti-isosceles set is one in which every three chosen points have three distinct pairwise distances. There is no known formula, so the honest route is an exhaustive search that grows a set point by point, adding a new point only if it keeps every triple’s distances distinct, and pruning any branch that can no longer beat the best found. On the $4\times 4$ grid the largest such set has $$\boxed{6 \text{ points,}}$$ for example $(0,0), (0,1), (2,0), (2,3), (3,1), (3,3)$. The same search gives $7$ points on the $5\times 5$ grid and $9$ on the $6\times 6$. The maximum grows slowly and irregularly with $N$, roughly in step with the side length rather than the area, which is why these sets stay sparse: a grid offers so many equal distances that avoiding all of them is genuinely hard.

The computation

Backtrack over grid points, extending the current set only when the new point forms no isosceles triple with any pair already chosen, and prune once the remaining points cannot improve on the best.

from itertools import combinations
def d2(p, q): return (p[0] - q[0])**2 + (p[1] - q[1])**2
def distinct(a, b, c):
    x, y, z = d2(a, b), d2(b, c), d2(a, c)
    return x != y and y != z and x != z
def largest(n):
    pts = [(i, j) for i in range(n) for j in range(n)]
    best = [0, None]
    def grow(start, chosen):
        if len(chosen) > best[0]: best[:] = [len(chosen), list(chosen)]
        for i in range(start, len(pts)):
            if len(chosen) + (len(pts) - i) <= best[0]: break   # prune
            p = pts[i]
            if all(distinct(a, b, p) for a, b in combinations(chosen, 2)):
                chosen.append(p); grow(i + 1, chosen); chosen.pop()
    grow(0, [])
    return best[0]
for n in (4, 5, 6): print(n, largest(n))       # 6, 7, 9