# 3x3 grid with no isosceles triangles of the same colour

Can you paint the 16 nodes of a 3x3 grid in three colours, such that no three nodes of the same colour form the vertices of an isosceles triangle? Note that we allow isosceles triangles to have zero area.

• Identifying which nodes form equilateral triangles is the big part here. Feb 7 at 12:51
• There are no equilateral triangles on three lattice points. Please describe your intention clearly. Feb 7 at 12:57
• Oh ooops! I meant to say isosceles! Wrong word. Sorry my bad Feb 7 at 13:04
• The line A-A-B-A has three A's in a line, but it that allowed or not? I would consider the A's to form a triangle with side lengths 1, 2 and 3, so not isosceles. Feb 7 at 14:04
• Actually good point. I will allow such a line. Feb 7 at 14:10

No, I can't (computer assisted proof)

In a 4x4 grid there are 16 dots, so by Pigeonhole Principle there has to be 6 of the same color. Computer search determines that the only such scenario is:

Now consider the 5 marked spots.

By Pigeonhole Principle 3 of them has to be the same color, but any case generates an isosceles triangle.

• Yep you got it. I came up with the same 6 points in my approach. Feb 8 at 3:27

Via integer linear programming, the minimum number of monochromatic isosceles triangles is

4: $$\begin{matrix} 1 &\boxed{2} &\boxed{\boxed{2}} &1 \\ \boxed{\boxed{2}} &\boxed{1} &\boxed{3} &\boxed{2} \\ \boxed{3} &\boxed{1} &3 &\boxed{\boxed{2}} \\ 3 &\boxed{1} &\boxed{2} &\boxed{3}\end{matrix}$$

• Gareth McCaughan's solution also has that many triangles Feb 8 at 3:10

Totally wrong answer (I believe in leaving my errors visible rather than deleting them):

that there is such a colouring:

R G G R
G R R G
G B B G
B R R B

Note: this is with the clarification, given by OP in comments, that three same-colour vertices are allowed on a line if they are unequally spaced: that is, degenerate scalene triangles are allowed even though degenerate isosceles ones are not.

Further note: this is also completely incorrect, as discussed in the comments (or, in fact, fairly easily seen if one happens to have a brain).

• That does not work since the Gs form an isosceles triangle. If we let bottom right be (0,0) (as in mathematics) then (0,1), (1,3), (3,2), for instance, is isosceles. Feb 7 at 15:02
• thats what you get for sleeping at 5:30 am Feb 7 at 15:25
• Those knight's move triangles are so easy to overlook. There are some red ones too. Feb 7 at 16:11
• @GarethMcCaughan so, what was the bug in the code? Feb 8 at 2:58
• I seem to have run it in a terminal window that I have since closed, so I fear I will never know. I do remember that it claimed that the number of isosceles triangles formed by vertices is 44, which now I think about it seems clearly way too low. ... Ah, figured it out. I had a 3 instead of a 4 and was therefore only looking at triangles using (3/4)x(3/4) of the vertices. D'oh! Feb 8 at 21:23