6
$\begingroup$

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.

enter image description here

$\endgroup$
5
  • 1
    $\begingroup$ Identifying which nodes form equilateral triangles is the big part here. $\endgroup$
    – justhalf
    Feb 7 at 12:51
  • 3
    $\begingroup$ There are no equilateral triangles on three lattice points. Please describe your intention clearly. $\endgroup$ Feb 7 at 12:57
  • 3
    $\begingroup$ Oh ooops! I meant to say isosceles! Wrong word. Sorry my bad $\endgroup$ Feb 7 at 13:04
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 7 at 14:04
  • $\begingroup$ Actually good point. I will allow such a line. $\endgroup$ Feb 7 at 14:10

3 Answers 3

17
$\begingroup$

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:

enter image description here

Now consider the 5 marked spots. enter image description here

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

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

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}

$\endgroup$
1
  • $\begingroup$ Gareth McCaughan's solution also has that many triangles $\endgroup$
    – Sunny Lu
    Feb 8 at 3:10
-1
$\begingroup$

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

The answer is

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).

$\endgroup$
6
  • 9
    $\begingroup$ 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. $\endgroup$
    – Sunny Lu
    Feb 7 at 15:02
  • 1
    $\begingroup$ thats what you get for sleeping at 5:30 am $\endgroup$
    – Sunny Lu
    Feb 7 at 15:25
  • 2
    $\begingroup$ Those knight's move triangles are so easy to overlook. There are some red ones too. $\endgroup$ Feb 7 at 16:11
  • 1
    $\begingroup$ @GarethMcCaughan so, what was the bug in the code? $\endgroup$
    – justhalf
    Feb 8 at 2:58
  • 1
    $\begingroup$ 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! $\endgroup$
    – Gareth McCaughan
    Feb 8 at 21:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.