6
$\begingroup$

A plane is colored with two colors. It's an easy exercise to prove that it's always possible to find an equilateral triangle whose vertices have all the same color.

Does anyone know any proof or reference for the following problem?

A plane is colored with two colors. Is it always possible to find a triangle whose vertices and center C have all the same color? Consider four different cases:

i) C is the incenter
ii) C is the circumcenter
iii) C is the orthocenter
iv) C is the barycenter.

Any help would be appreciated.

$\endgroup$
6
$\begingroup$

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

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

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 and in pip-format) 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.

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


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

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

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.

$\endgroup$
3
$\begingroup$

Actually, for any finite subset $P$ of the plane, there are $2^{\aleph_0}$ monochromatic scaled copies of $P$:

https://arxiv.org/abs/1304.3154

(see also the question Monochromatic point sets in two-colored plane)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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