Skip to main content
Commonmark migration
Source Link

[![equilateral triangle][1]][1]equilateral triangle

[![equilateral triangle in grid][4]][4]equilateral triangle in grid

In order to show the claim, we reformulate this as an integer program. We have $61$ binary variables $x_0,\dots x_60$. Since three points are already colored red (which is, let's say, color "1"), we immediately get the equations $x_{21}=x_{31}=x_{38}=1$. In addition for each quadruple $(a,b,c,d)\in S$, we obtain the inequalities $$1\leq x_a+x_b+x_c+x_d\leq 3.$$ Thus we obtain an integer program with $3+ 2\cdot224 = 451$ constraints. The feasibility of this program is equivalent to out claim. It turns out that this program (which can be found here in [lp-format][2]lp-format and in [pip-format][3]pip-format) is infeasible.

[![configuration of 59 points][5]][5]configuration of 59 points

[![configuration of 59 points][6]][6]configuration of 59 points

I feel like there should be a more simple argument for this fact, but at least you know in what direction to look.
[1]: https://page.mi.fu-berlin.de/moritz/mo/273653/equi.svg [2]: https://page.mi.fu-berlin.de/moritz/mo/273653/prog.lp [3]: https://page.mi.fu-berlin.de/moritz/mo/273653/prog.pip [4]: https://page.mi.fu-berlin.de/moritz/mo/273653/numbergrid.svg [5]: https://page.mi.fu-berlin.de/moritz/mo/273653/59.svg [6]: https://page.mi.fu-berlin.de/moritz/mo/273653/59a.svg

[![equilateral triangle][1]][1]

[![equilateral triangle in grid][4]][4]

In order to show the claim, we reformulate this as an integer program. We have $61$ binary variables $x_0,\dots x_60$. Since three points are already colored red (which is, let's say, color "1"), we immediately get the equations $x_{21}=x_{31}=x_{38}=1$. In addition for each quadruple $(a,b,c,d)\in S$, we obtain the inequalities $$1\leq x_a+x_b+x_c+x_d\leq 3.$$ Thus we obtain an integer program with $3+ 2\cdot224 = 451$ constraints. The feasibility of this program is equivalent to out claim. It turns out that this program (which can be found here in [lp-format][2] and in [pip-format][3]) is infeasible.

[![configuration of 59 points][5]][5]

[![configuration of 59 points][6]][6]

I feel like there should be a more simple argument for this fact, but at least you know in what direction to look.
[1]: https://page.mi.fu-berlin.de/moritz/mo/273653/equi.svg [2]: https://page.mi.fu-berlin.de/moritz/mo/273653/prog.lp [3]: https://page.mi.fu-berlin.de/moritz/mo/273653/prog.pip [4]: https://page.mi.fu-berlin.de/moritz/mo/273653/numbergrid.svg [5]: https://page.mi.fu-berlin.de/moritz/mo/273653/59.svg [6]: https://page.mi.fu-berlin.de/moritz/mo/273653/59a.svg

equilateral triangle

equilateral triangle in grid

In order to show the claim, we reformulate this as an integer program. We have $61$ binary variables $x_0,\dots x_60$. Since three points are already colored red (which is, let's say, color "1"), we immediately get the equations $x_{21}=x_{31}=x_{38}=1$. In addition for each quadruple $(a,b,c,d)\in S$, we obtain the inequalities $$1\leq x_a+x_b+x_c+x_d\leq 3.$$ Thus we obtain an integer program with $3+ 2\cdot224 = 451$ constraints. The feasibility of this program is equivalent to out claim. It turns out that this program (which can be found here in lp-format and in pip-format) is infeasible.

configuration of 59 points

configuration of 59 points

I feel like there should be a more simple argument for this fact, but at least you know in what direction to look.

explain that ppl also ran..
Source Link
Moritz Firsching
  • 10.7k
  • 3
  • 63
  • 88

[EDIT: By now, the exact solver PPL, also reports infeasibility! It took a few minutes to run (but less time than writing this answer..)]

[EDIT: By now, the exact solver PPL, also reports infeasibility! It took a few minutes to run (but less time than writing this answer..)]

Source Link
Moritz Firsching
  • 10.7k
  • 3
  • 63
  • 88

The answer is "yes". Let me give the outline of a proof of a stronger statement, that implies all of the cases you consider.

Proposition: In all colorings of the plane with two colors there is an equilateral triangle, such that all of its vertices and its center have the same color.

First, as you mentioned, we can assume that we have found an monochrome equilateral triangle in the plane:

[![equilateral triangle][1]][1]

Let's not only look at those three points, but also at the following 58 points, arranged in a triangular grid in shape of a hexagon with 5 points on each edge. (Its 61 points in total and our original triangle is on of the two smallest equilateral triangles around the center).

[![equilateral triangle in grid][4]][4]

For convenience I have labelled the vertices, for example the original equilateral triangle is (21,31,38).

This configuration of points contains many quadruples $(a,b,c,d)$, such that $(a,b,c)$ is an equilateral triange and $d$ is its center. For example the point $8$ is contained is the center of the triangles (1, 4, 22), (2, 9, 14) and (3, 7, 15). Let $S$ be the set of all such quadruples. In fact $S$ is a set with 224 elements: $$S=\{(0, 3, 21, 7), (0, 7, 12, 6), (0, 10, 38, 14), (0, 15, 28, 13), (0, 18, 21, 12), (0, 24, 44, 21), (0, 31, 35, 20), (0, 34, 56, 30), (1, 4, 22, 8), (1, 5, 13, 6), (1, 8, 13, 7), (1, 16, 29, 14), (1, 19, 22, 13), (1, 25, 45, 22), (1, 26, 39, 20), (1, 32, 36, 21), (1, 42, 50, 30), (2, 6, 14, 7), (2, 9, 14, 8), (2, 11, 30, 13), (2, 17, 30, 15), (2, 20, 23, 14), (2, 27, 40, 21), (2, 33, 37, 22), (2, 43, 49, 30), (3, 7, 15, 8), (3, 10, 15, 9), (3, 12, 31, 14), (3, 18, 47, 21), (3, 21, 24, 15), (3, 28, 41, 22), (3, 34, 38, 23), (3, 35, 55, 30), (4, 5, 39, 14), (4, 8, 16, 9), (4, 13, 32, 15), (4, 19, 48, 22), (4, 22, 25, 16), (4, 26, 60, 30), (4, 29, 42, 23), (5, 8, 29, 13), (5, 13, 19, 12), (5, 16, 45, 21), (5, 22, 36, 20), (5, 25, 57, 30), (5, 26, 29, 19), (5, 32, 50, 29), (6, 9, 30, 14), (6, 11, 20, 12), (6, 14, 20, 13), (6, 17, 46, 22), (6, 23, 37, 21), (6, 27, 30, 20), (6, 33, 51, 30), (6, 40, 43, 29), (7, 10, 31, 15), (7, 12, 21, 13), (7, 15, 21, 14), (7, 18, 38, 20), (7, 24, 38, 22), (7, 28, 31, 21), (7, 34, 52, 31), (7, 35, 47, 29), (7, 41, 44, 30), (8, 13, 22, 14), (8, 16, 22, 15), (8, 19, 39, 21), (8, 25, 39, 23), (8, 26, 53, 29), (8, 29, 32, 22), (8, 36, 48, 30), (8, 42, 45, 31), (9, 11, 46, 21), (9, 14, 23, 15), (9, 17, 23, 16), (9, 20, 40, 22), (9, 27, 54, 30), (9, 30, 33, 23), (9, 37, 49, 31), (10, 12, 47, 22), (10, 15, 24, 16), (10, 18, 59, 30), (10, 21, 41, 23), (10, 28, 55, 31), (10, 31, 34, 24), (11, 14, 37, 20), (11, 17, 58, 30), (11, 20, 27, 19), (11, 23, 51, 29), (11, 30, 43, 28), (12, 15, 38, 21), (12, 18, 28, 19), (12, 21, 28, 20), (12, 24, 52, 30), (12, 31, 44, 29), (12, 35, 38, 28), (12, 41, 56, 38), (13, 16, 39, 22), (13, 19, 29, 20), (13, 22, 29, 21), (13, 25, 53, 31), (13, 26, 45, 28), (13, 32, 45, 30), (13, 36, 39, 29), (13, 42, 57, 39), (13, 48, 50, 38), (14, 17, 40, 23), (14, 20, 30, 21), (14, 23, 30, 22), (14, 27, 46, 29), (14, 33, 46, 31), (14, 37, 40, 30), (14, 43, 54, 38), (14, 49, 51, 39), (15, 18, 52, 29), (15, 21, 31, 22), (15, 24, 31, 23), (15, 28, 47, 30), (15, 34, 47, 32), (15, 35, 59, 38), (15, 38, 41, 31), (15, 44, 55, 39), (16, 19, 53, 30), (16, 22, 32, 23), (16, 25, 32, 24), (16, 29, 48, 31), (16, 36, 60, 39), (16, 39, 42, 32), (17, 20, 54, 31), (17, 23, 33, 24), (17, 30, 49, 32), (18, 21, 44, 28), (18, 28, 35, 27), (18, 31, 56, 37), (19, 22, 45, 29), (19, 26, 36, 27), (19, 29, 36, 28), (19, 32, 57, 38), (19, 39, 50, 37), (20, 23, 46, 30), (20, 27, 37, 28), (20, 30, 37, 29), (20, 33, 58, 39), (20, 40, 51, 38), (20, 43, 46, 37), (21, 24, 47, 31), (21, 28, 38, 29), (21, 31, 38, 30), (21, 34, 59, 40), (21, 35, 52, 37), (21, 41, 52, 39), (21, 44, 47, 38), (21, 55, 56, 46), (22, 25, 48, 32), (22, 26, 57, 37), (22, 29, 39, 30), (22, 32, 39, 31), (22, 36, 53, 38), (22, 42, 53, 40), (22, 45, 48, 39), (22, 50, 60, 46), (23, 27, 58, 38), (23, 30, 40, 31), (23, 33, 40, 32), (23, 37, 54, 39), (23, 46, 49, 40), (24, 28, 59, 39), (24, 31, 41, 32), (24, 34, 41, 33), (24, 38, 55, 40), (25, 29, 60, 40), (25, 32, 42, 33), (26, 29, 50, 36), (27, 30, 51, 37), (27, 37, 43, 36), (28, 31, 52, 38), (28, 35, 44, 36), (28, 38, 44, 37), (28, 47, 56, 45), (29, 32, 53, 39), (29, 36, 45, 37), (29, 39, 45, 38), (29, 48, 57, 46), (29, 50, 53, 45), (30, 33, 54, 40), (30, 37, 46, 38), (30, 40, 46, 39), (30, 43, 58, 45), (30, 49, 58, 47), (30, 51, 54, 46), (31, 34, 55, 41), (31, 38, 47, 39), (31, 41, 47, 40), (31, 44, 59, 46), (31, 52, 55, 47), (32, 39, 48, 40), (32, 42, 48, 41), (32, 45, 60, 47), (33, 40, 49, 41), (35, 38, 56, 44), (36, 39, 57, 45), (36, 45, 50, 44), (37, 40, 58, 46), (37, 43, 51, 44), (37, 46, 51, 45), (38, 41, 59, 47), (38, 44, 52, 45), (38, 47, 52, 46), (38, 56, 59, 52), (39, 42, 60, 48), (39, 45, 53, 46), (39, 48, 53, 47), (39, 57, 60, 53), (40, 46, 54, 47), (40, 49, 54, 48), (41, 47, 55, 48), (44, 52, 56, 51), (45, 50, 57, 51), (45, 53, 57, 52), (46, 51, 58, 52), (46, 54, 58, 53), (47, 52, 59, 53), (47, 55, 59, 54), (48, 53, 60, 54)\}.$$

Claim All colorings of the configuration of 61 points with two colors, there is a monochromatic quadruple $(a,b,c,d)$ such that $(a,b,c,d)\in S$, i.e. $(a,b,c)$ is an equilateral triangle with center $d$.

In order to show the claim, we reformulate this as an integer program. We have $61$ binary variables $x_0,\dots x_60$. Since three points are already colored red (which is, let's say, color "1"), we immediately get the equations $x_{21}=x_{31}=x_{38}=1$. In addition for each quadruple $(a,b,c,d)\in S$, we obtain the inequalities $$1\leq x_a+x_b+x_c+x_d\leq 3.$$ Thus we obtain an integer program with $3+ 2\cdot224 = 451$ constraints. The feasibility of this program is equivalent to out claim. It turns out that this program (which can be found here in [lp-format][2] and in [pip-format][3]) is infeasible.

Note: So far I have checked infeasibility of the program with GLPK and SCIP, both of which say that it is infeasible after less then a second. I have not (yet) used an exact solver, so you should take my answer here with a grain of salt.


If have tried a bit with smaller versions of the same idea, and I would expect a smaller configuration of points to work as well. For example, the same arguments goes through if we take out the last point (number $60$). If we take out, the two points $59$ and $60$, however there is a valid coloring:

[![configuration of 59 points][5]][5]

We can also take out the first and the last point:

[![configuration of 59 points][6]][6]

I feel like there should be a more simple argument for this fact, but at least you know in what direction to look.
[1]: https://page.mi.fu-berlin.de/moritz/mo/273653/equi.svg [2]: https://page.mi.fu-berlin.de/moritz/mo/273653/prog.lp [3]: https://page.mi.fu-berlin.de/moritz/mo/273653/prog.pip [4]: https://page.mi.fu-berlin.de/moritz/mo/273653/numbergrid.svg [5]: https://page.mi.fu-berlin.de/moritz/mo/273653/59.svg [6]: https://page.mi.fu-berlin.de/moritz/mo/273653/59a.svg