A Puzzling Grid

Question

Consider the following axioms on a coloring of the Euclidean plane $\mathbb R^2$:

A1. Every point of $\mathbb R^2$ is colored $0$ or $1$.
A2. Every line contains points of both colors.

---

Definitions.

• A set of points in the plane is called monochromatic if all points have the same color.
• A square is a set of $4$ points forming the corners of a square.
• An equilateral triangle is a set of $3$ points forming the corners of an equilateral triangle.
• A unitary pair is a set of $2$ points at distance 1.

---

Question.

Does a plane satisfying Axioms A1 and A2 always contain a monochromatic square?
If the answer is yes, then please provide a (minimal) construction (not an existential proof).
If the answer is no, then please provide an impossibility proof.

Hint 1. [added 5/9/2017]

Does a plane satisfying Axioms A1 and A2 always contain a unitary pair?

Answer to Hint 1. Yes.

Pick point X1(0,0) and X2(0,1). Without loss of generality, we can assume that X1(0,0) has color 0. If both are the same color, you are done. If not, point X3(0,2) is either color, so we either have a unitary pair or a pair at distance 2 (not what we want). It seems we are stuck. Originally I could not improve on this result. I had the following insight.

If the (square) grid does not admit a unitary pair, then it must be a checkerboard pattern! However, we want to admit only finite constructions. We are not allowed to construct this checkerboard and use it in a subsequent step! Bummer. But then I realized that we do not have to know this about the grid. The unitary pair is already close at hand. Proceed as follows. If point X3(0,2) is of color 0, construct a point X' at distance 1 from X3(0,2) and at distance 2 from X1(0,0). We can do this by using a compass and intersect 2 circles. Points X1(0,0), X3(0,2) and X' form an isosceles triangle (please, check this).

If X' is of color 0, it forms a unitary pair with X3(0,2). If X' is of color 1, look at the midpoint X'' between X' and X1(0,0). If X'' is of color 0, it forms a unitary pair with X1(0,0); if it is of color 1, it forms a unitary pair with X'. Found it!

Hint 2. [Original hint (unchanged).]

Does a plane satisfying Axioms A1 and A2 always contain a monochromatic equilateral triangle?

Answer to Hint 2. Yes.

This picture shows the type of construction I am talking about. Without loss of generality, points 1 and 2 are colored as shown; if they were of opposite colors, turn the plane 180 degrees. If they were equal, it would be the same as a construction starting with 1, 3, 2, etc. (and if point 2 had been red, we would have already succeeded.) Thus, without loss of generality, we can assume that point 3 is red; if it had been green, the construction proceeds mirrored. For all the following points note that if they had the opposite color, we would have already succeeded in finding a monochromatic equilateral triangle. The picture proves that a construction needs no more than 8 points. Can you find a construction using less than 8 points?

Conjecture.

The answer to the question is yes.

I considered that for $n>1$ a square of size $(n-1)*(n-1)$ contains a grid of $n*n$ points, the corners of the unit squares in it. Using only the points of this grid, it has $O(n^{3})$ squares in it. However, I suspect that if $n$ is large enough, there is always at least one monochromatic square in it. Since we can imagine such a grid multiplied, translated or rotated anywhere in the plane, it would follow that the plane has an infinite number of monochromatic squares of (approximately) any size; in a way the plane is dense with monochromatic squares.Still, I have not been able to come up with a construction that shows the existence of at least one square. The reason is that the number of possible colourings equals $2^{n^{2}}$, ignoring symmetries. For $n=2,3,4,5$ I found colourings that do NOT admit a square. $n=6$ turns out too difficult to do by hand. Now consider $n=10$; the number of colorings is $2^{100} \approx 10^{30}$. To disprove the conjecture, it is sufficient to find just ONE colouring that does not admit a square. But to prove the conjecture, I need to find a monochromatic square in ALL colourings. I couldn't see how to simplify this search. Please, help.

If you want to disprove the conjecture, you can colour the plane in any way you want (as long as axioms A1 and A2 hold) and prove for your colouring that it does not have a monochromatic square. If you can do this, then it is clear that no construction of a monochromatic square is possible. Then it will follow that ALL finite grids can be coloured in such a way that it does NOT have a monochromatic square. It would be quite a powerful result. (And therefore not trivial.)

---

Note.

• A2 eq. no line is monochromatic.
• I remember this problem as part of an article or or a book I read during the late 80's, but I lost the reference. The original talked about red and green points. I seem to remember that it was a study or research article about the properties of such a coloured plane. I seem to remember that it contained the construction of a monochromatic square. I could be wrong. I am still intrigued after all these years! It seems to be an interesting problem in its own right.

Good luck.

Answer 1

The Hungarian mathematician Tibor Gallai proved the following theorem in the 1930s (but never published his proof):

Theorem: Let $S$ be a finite subset of $\mathbb{Z}^n$. Then any coloring of $\mathbb{Z}^n$ with finitely many colors contains a monochromatic subset that is homothetic to $S$, that is, a monochromatic subset of the form $x+yS$ with $x,y\in\mathbb{Z}^n$.

A proof was published later in 1943 by Richard Rado in the Proceedings of the London Mathematical Society 48, pp 122-160. See for instance http://arxiv.org/abs/1304.3154 for more information on this; or google for the terms "Ramsey theory", "Euclidean", "Gallai".

For $n=2$ and $S=\{(0,0),(0,1),(1,0),(1,1)\}$ and for two colors, Gallai's theorem tells us that there indeed always exists a monochromatic square.

Answer 2

This took me soooooo long. If you read it, I commend you. If you find fault in it, then I will delete this answer and never look at this problem again.

~~~~

We will prove that if a row containing 5 in a row exists, it must contain a monochromatic square. Then we will iteratively prove for 4, 3, 2, and 1. We only need the grid, not the real numbers. And we don't use $A2$.

Also, it doesn't rely on other theorems, which, while make other proofs elegant, also require a level of sophistication that not all puzzlers may have.

It is, unfortunately, just long.

Instead of colours, I use $0$ and $1$.

Five in a row

Lets assume there is a run of five in a row.

00000

There are a few options for how we create the row below. We cannot have two consecutive 0s, so our options are:

 1.     2.     3.     4.     5.     6.     7.     8.    9.
 00000  00000  00000  00000  00000  00000  00000  00000 00000
 11111  11110  11101  11011  11010  10101  10110  01110 01010

Notice that option 1 has no 0s, options 2-4 have 1 0, options 5-8 have 2 0s, and option 9 has 3 0s.

Case 1

Lets try to add a row on top. You can either start with a 0 or a 1.

Case 1.1

Start with a 0. The next must be a 1 to avoid making a 2x2 square. That means the 4th must be a 0 to avoid a 3x3 square of 1s. Since we can't have two consecutive 0s, the 3rd and 5th must also be 1s.

01101  --1-1
00000  -----
11111  --1-1

But this makes a 3x3 monochrome square.

Case 1.2

So instead, we start with a 1 on top. The 3rd must be a 0 and the 2nd and 4th must be 1s.

1101-  -1-1-
00000  -----
11111  -1-1-

Again, we've made a monochrome 3x3 square.

Case 2

If you add a 1, you will end up with the same situation as Case 1.2.

So, we must add a 0. The next must be a 1 meaning 4th must be 0, so the 3rd and 5th are 1s.

01101
00000
11110

Now add another row on the bottom.

If we add a 0, the 3rd column must be a 1, which means the 2nd and 4th must be 0s. But this makes a square, so we must instead add a 1 on the bottom. Thus, the 2nd must be a 0, and the 4th must be a 1, so the 3rd must be 0.

01101  -----     01101  ---0-
00000  -0-0- --> 00000  -0---
11110  -----     11110  ----0
0010-  -0-0-     1001-  --0--

This makes a tilted monochrome square of 0s. It doesn't look like a square because the font is not square, but it is.

Case 3

If the 2nd spot on top is a 0, then 1s are needed on either side which creates a monochrome 3x3 square. Thus, the 2nd spot on top must be a 1. Similarly for the 4th spot.

101-- 1-1--     -1-1-
00000 ----- --> 00000
11101 1-1--     11101

Case 3.1

Start with a 0 between the 2 1s in the top row.

-101-
00000
11101

If you put a 0 in the 2nd column of a new row below, you will get a tilted square. Thus it must be a 1. But then 0s are required on either side which also makes a square.

-101- --0--       -101- -----
00000 0----  -->  00000 0-0--
11101 ---0-       11101 -----
-0--- -0---       010-- 0-0--

Case 3.2

Thus, we need to start with a 1 in the 3rd column. We need 0s in the 1st and 5th to avoid squares.

01110
00000
11101

If you add another row on top and put a 0 in the 3rd column there is a tilted square. Thus, it must be a 1 with 0s on either side. But again, there is a square.

--0-- --0--      -010- -0-0-
01110 ----0  --> 01110 -----
00000 -0---      00000 -0-0-
11101 ---0-      11101 -----

Case 4

Notice a 0 in the 3rd spot on top would create a diamond. So we need a 1 there. You cannot have 1s on either side, so at least one of those must be a 0. Possibly both. The options are:

-010-     -011-     -110-
00000     00000     00000
11011     11011     11011

The last two are symmetric, so we can ignore the last. Notice that both remaining options require a 1 in the first spot. The first also requires a 1 in the last spot.

If you add a 0 in the 4th spot of a new row on top, you will create a tilted monochromatic square. So this must be a 1 for both. This means a 0 is required in the 1st position for both to avoid a 4x4 square, and 1 in the 3rd to avoid a 3x3 square.

---0- ---0-      0-11-  0-11-
101?- -0---  --> 1011-  10101
00000 ----0      00000  00000
11011 --0--      11011  11011

The first option is now trivially eliminated now leaving only the 2nd. We will try to add another row on top.

If you add a 1 on top in the 1st position, then the 3rd must be a 0. This makes a tilted square, so it must be a 0. Thus the 4th must be a 1 and the 3rd again must be a 0 making the same tilted square.

1-0--  --0--     0-01- --0--
0-11-  0----     0-11- 0----
10101  ---0- --> 10101 ---0-
00000  -0---     00000 -0---
11011  -----     11011 -----

Case 5

A 1 must occupy the 3rd position on top. We can't have 2 1s on either side, so the 3 options are 010, 011, and 110. These are shown below with any trivial additions required.

10101     1011-     -1101
00000     00000     00000
11010     11010     11010

Case 5.1

If the 2nd, 3rd, or 4th are 0s, you get tilted squares or a diamond. Thus, they must all be 1s. This means the 1st position must be a 0 to avoid a 4x4 square.

-0--- -0---     --0-- --0--    ---0- ---0-       0111-
10101 ---0-     10101 -0-0-    10101 -0---  -->  10101
00000 0----     00000 --0--    00000 ----0       00000
11010 --0--     11010 -----    11010 --0--       11010

In the row above this, if a 1 is placed in the 3rd spot, then you end up with a diamond. However, a 0 in the 3rd spot results in a titled square.

--1-- --1--      --0-- --0--
0111- -1-1-      0111- 0----
10101 --1-- -->  10101 ---0-
00000 -----      00000 -0---
11010 -----      11010 -----

Case 5.2

Again, the 4th position on top must be a 1 to avoid a tilted square. That means the 3rd must be a 0, making the 1st a 1.

---0-  ---0-     1-01-  1--1-
1011-  -0---     1011-  -----
00000  ----0 --> 00000  -----
11010  --0--     11010  1--1- 

Case 5.3

If the 2nd position on top is a 0, then there is a tilted square. So it must be a 1. Thus, the 3rd must be a 0, making the 1st and 5th 1s. The 4th then must be a 0. This means the 2nd row can be completed with a 0.

-0--- -0---     11001
-1101 ---0- --> 01101
00000 0----     00000
11010 --0--     11010

Lets add another row on the bottom. If the 4th is a 0, then there is a diamond, so it must be a 1.

11001 -----      11001 -1---
01101 -----      01101 ----1
00000 ---0- -->  00000 -----
11010 --0-0      11010 1----
---0- ---0-      01110 ---1-

Case 6

We clearly need 1s in the 2nd and 4th positions to avoid diamonds. If there is a 1 in the 3rd, then the 1st and 5th must be 0s. Otherwise, they can be anything. the options are shown below.

01110     01010     11010     01011     11011 
00000     00000     00000     00000     00000
10101     10101     10101     10101     10101

We can eliminate the 3rd, 4th, and 5th scenarios because we've already proven with case 5 and case 4 that these result in monochrome squares.

Case 6.1

If there is a 1 in the 3rd spot, then there must be 0s on either side making a square. Alternatively, if there is a 0 in the 3rd spot, you get a tilted square.

-010- -0-0-     --0-- --0--
01110 ----- --> 01110 ----0
00000 -0-0-     00000 -0---
10101 -----     10101 ---0-

Case 6.2

The middle 3 on top must be 1s to avoid squares.

-0--- -0---    --0-- --0--    ---0- ---0-      -111-
01010 0-0--    01010 0----    01010 --0-0 -->  01010
00000 -0---    00000 ---0-    00000 ---0-      00000
10101 -----    10101 -0---    10101 -----      10101

Lets add another row on top. If we start with a 0, then the 3rd and 4th positions must be a 1s which make a small square. Thus, the row on top must start with a 1, making the 5th spot a 0. Then the 3rd must be a 1, so the 2nd and 4th are 0s.

0-11- --11-     10100 -0--0
-111- --11-     -111- -----
01010 ----- --> 01010 -----
00000 -----     00000 -0--0
10101 -----     10101 -----

Case 7

Lets add a row above. If you start with a 1, then the 3rd spot must be a 0 with 1s on either side. If we complete this row with a 1 then this is Case 4. If we complete it with a 0, then it is Case 5. Both of which we've already proven.

1101-
00000
10110

So, we need to start with a 0. Thus, the 2nd spot must be a 1. If we complete the row with 011 or 111, then we will have Case 5 or Case 2. So we must use something else. Options are 010, 101, and 110.

01010    01101    01110
00000    00000    00000
10110    10110    10110

Case 7.1

First note that a 1 is required in the 6th position of the 2nd row to avoid a diamond. Thus, a 1 in the 5th position of the row below would make a tilted square, so it must be a 0. Thus, the 3rd position must be a 1 and the 4th a 0, which also is a tilted square.

01010- ---1--     01010- --0---
000001 -----1 --> 000001 ----0-
10110- --1---     10110- -0----
----1- ----1-     --100- ---0--

Case 7.2

Lets add to the row below. If we put a 0 in the 3rd position, we get a tilted square. So it needs to be a 1. Thus the 4th is a 0 and the 2nd is 1. This makes the 5th a 0.

01101 ---0-    01101 -----
00000 -0---    00000 -----
10110 ----0    10110 -----
--0-- --0--    -1100 -----

If we add another row on the bottom, we see that the 3rd spot cannot be a 0 since that makes a tilted square. Thus, it must be a 1, making the 2nd 0.

01101 -----     01101 ---0-
00000 ---0-     00000 0----
10110 -0--- --> 10110 -----
-1100 ----0     -1100 ----0
--0-- --0--     -01-- -0---

Case 7.3

If you put a 0 in the 3rd spot on top, then there is a tilted square. Thus it must be a 1, but then the 2nd and 3rd spots need to be 0s.

--0-- --0--    -010- -0-0-
01110 0----    01110 -----
00000 ---0-    00000 -0-0-
10110 -0---    10110 -----

Case 8

If the 3rd spot is a 0, then there must be 1s on either side. Therefore, it is a 1.

-101- -1-1-      --1--
00000 ----- -->  00000
01110 -1-1-      01110

If there are 0s on either side, then 1s are required on the ends, which makes this Case 6. We've already seen they can't be 1s on either side, so we need one of each. Since it is symmetric, WLOG we can put the 1 in the 2nd spot and a 0 in the 4th. That means a 1 in the 5th.

-1101
00000
01110

Completing this row with a 1 is Case 3 and with a 0 is Case 7.

Case 9

A 0 in the middle position requires 1s everywhere else. This is exactly the Case 4.

11011     --1--
00000 --> 00000
01010     01010

If you put 1s on either side, you create a square of 1s. 0s on either side means you need to finish with 1s, which is Case 6. Thus, we need one of each. Since it is symmetric, WLOG we will pick the 2nd spot to have a 1 and the 3rd a 0. Thus the 5th must be a 1.

-1101
00000
01010

Completing with a 1 is Case 3, and completing with a 0 is Case 7.

Four in a row

Now that we have proven that there is no run of 5, we know at most there is a run of 4 bookended with 1s as follows.

100001

There are a number of ways to tile the row below.

1.        2.        3.        4.        5.
100001    100001    100001    100001    100001
-1111-    -1110-    -1101-    -0101-    -0110-

Case 1

Try to add a row on top.

If we add a 1 in the 2nd position, then you need a 0 in the 4th and 1s on either side. This makes a square, so we know that we must start with a 0 in the 2nd position. Then the 3rd must be a 1 and the 5th a 0, making the 4th a 1.

-1101- --1-1-     -0110-
100001 ------ --> 100001
-1111- --1-1-     -1111-

If we add a 1 in either of the ends, we get a tilted square. But if they are 0s, then the middle two must be 1s.

-1---- -1----     -0110- --11--
-0110- ---1-- --> -0110- --11--
100001 1-----     100001 ------
-1111- --1---     -1111- ------

Case 2

Immediately we see that a 0 in the 3rd spot requires 1s on either side which makes a square. Therefore, it must be a 1.

-101-- -1-1--      --1---
100001 ------ -->  100001
-1110- -1-1--      -1110-

If we go up another row, we see that a 1 in the 5th spot makes a tilted square. Therefore, it must be a 0. Thus, there needs to be a 1 in the 3rd spot.

----1- ----1-      --1-0-
--1--- --1--- -->  --1---
100001 -----1      100001
-1110- ---1--      -1110-

Similarly, if we create a new row below, adding a 1 in the 3rd spot results in 0s on either side which makes a square. Thus, it must be a 0 and the 5th spot must be a 1.

--1-0- ------      --1-0-
--1--- ------      --1---
100001 -0-0-- -->  100001
-1110- ------      -1110-
-010-- -0-0--      --0-1-

Back in the 2nd row, if there is a 1 in the 4th spot, we get a tilted square. Therefore, it must be 0. Therefore, there must be 1s in the 5th and 6th (to avoid a diamond) spots.

--1-0- ------      --1-0- --1---
--11-- ---1--      --1011 -----1
100001 -----1 -->  100001 ------
-1110- --1---      -1110- -1----
--0-1- ----1-      --0-1- ----1-

Case 3

A 0 in the 4th spot makes a diamond, so it must be a 1.

---0-- ---0--      ---1--
100001 --0-0- -->  100001
-1101- ---0--      -1101-

If you go one more row up, then adding a 1 in the 2nd spot makes a tilted square, so it must be a 0. Thus you need a 1 in the 4th spot.

-1---- -1----      -0-1--
---1-- ---1--      ---1--
100001 1----- -->  100001
-1101- --1---      -1101-

Going to the row below, if there is a 1 in the 5th spot, we get a tilted square, so it must be a 0. Thus, a 1 is needed in the 3rd spot, and a 0 in the 2nd, and a 1 in the 4th. Also, a 1 is needed in the 4th row 6th spot to prevent a 0 diamond.

-0-1-- ------      -0-1--
---1-- ---1--      ---1--
100001 -----1 -->  100001
-1101- --1---      -11011
----1- ----1-      -0110-

If there is a 0 in the 2nd column of the 2nd row, then a 1 is needed in the 3rd column. This means a 0 in the 5th. In the row above, a 0 is needed in the 3rd column. But this makes a tilted square, so we know the 2nd column of the 2nd row must be a 1.

-001-- --0---      -0-1--
-0110- ----0-      -1-1--
100001 -0---- -->  100001
-11011 ---0--      -11011
-0110- ------      -0110-

The 3rd spot of the 2nd row cannot be a 1 because we'd need a 0 above it, and a 1 to avoid the tilted square we just saw, which means a 0 in the top row 5th column, which also makes a square. Thus, we need a 0 in the 3rd spot of the 2nd row. Then we need a 1 in the 1st spot of the 2nd row to avoid a diamond, and a 0 in the bottom left corner to avoid a square.

-0010- -0-0--      -0-1--
-1111- ------      1101--
100001 -0-0-- -->  100001
-11011 ------      -11011
-0110- ------      00110-

A 0 in the 3rd spot of the row below makes a tilted square. But so does a 1.

-0-1-- ------      -0-1-- ---1--
1101-- ------      1101-- ------
100001 -0---- -->  100001 1-----
-11011 ---0--      -11011 -----1
00110- 0-----      00110- ------
--0--- --0---      --1--- --1---

Case 4

If we start with a 1 in the 5th spot, then we need a 0 in the 3rd and 1s on either side.

-1011- -1011-
100001 100001
-0101- ------

But this is just Case 3 upside down, so we know we need to start with a 0 in the 5th spot, thus a 1 in the 4th.

---10-
100001
-0101-

A 1 in the 2nd spot on top will result in a tilted square, so this must be a 0. Thus a 1 in the 4th.

-1---- -1----      -0-1--
---10- ---1-- -->  ---10-
100001 1-----      100001
-0101- --1---      -0101-

Putting a 0 in the 3rd spot in the top row results in a tilted square, so it must be a 1 with a 0 below it, and a 1 to the left of that. A 1 is needed in the 1st spot of the 2nd row to avoid a diamond.

-001-- --0---      -011--
---10- ----0- -->  11010-  -1010-
100001 -0----      100001  100001
-0101- ---0--      -0101-  -0101-

Notice at this point that there is a similarity highlighted. Because of the symmetry and the fact that all the placement so far has been forced, we can extend the same pattern below. Also note we need 0s in the top right corners to avoid a 4x4 square of 1s. By symmetry, it is also needed in the bottom left.

-011--      -011-1 --1--1      -011-0
11010-      11010- ------      11010-
100001 -->  100001 ------ -->  100001
-0101-      -01011 --1--1      -01011
            --110- ------      0-110-

If we put a 1 in the top 5th (or bottom 2nd), we would get a tilted square. Thus, these must be 0s. Thus, we need 1s in the 2nd and 4th rows. The remaining corners need to be 1s to avoid 5x5 squares.

-01110 ----1-      001100 0---0-      101100 10----
11010- -1----      110101 ------      110101 11----
100001 ------ -->  100001 ------ -->  100001 10----
-01011 -----1      101011 ------      101011 10----
0-1101 --1---      00110- 0---0-      001101 ------

Notice the highlighted section is simply the inverse of Case 3 on its side.

Case 5

One of the 3rd or 4th must be a 1 (they can't both be 0s). WLOG we will say the 3rd is. Putting a 1 in the 5th row above this results in a tilted square, so it must be a 0. Thus, there is a 1 in the 3rd column.

----1- ----1-      --1-0-
--1--- --1--- -->  --1---
100001 -----1      100001
-0110- ---1--      -0110-

If you put a 1 in the 4th column of the 2nd row, then a 0 must go above it, and a 1 must be in the 2nd column on top. This makes a tilted square, so we know a 0 must go in the 4th column of the 2nd row. A 1 must go in the 5th. If we put a 1 in the 2nd column of the 2nd row, then we have Case 3 again, so it must be a 0. We can then also put a 1 in the 6th column of the 2nd row to prevent a diamond.

-1100- -1----      --1-0-
--11-- ---1-- -->  -01011
100001 1-----      100001
-0110- --1---      -0110-

A 0 in the 3rd column below makes a tilted square, so it must be a 1. That means a 0 in the 4th and a 1 in the 2nd.

--1-0- ------      --1-0- ------
-01011 ---0-- -->  -01011 --1---
100001 -0----      100001 1-----
-0110- ----0-      -0110- ---1--
--0--- --0---      -110-- -1----

Three in a row

We know any solution cannot have more than three in a row, so it as at most the following:

10001

The possibilities for the row below are:

1.       2.       3.       4.
10001    10001    10001    10001
-111-    -110-    -101-    -010-

Case 1

We know that there are no runs of 4, so the row of ones must have 0s on either side.

For the top row, a 0 in the 3rd position would necessitate 1s on either side making a square. Thus, it needs to be a 1. Either the 2nd or 4th must be a 0 (they can't both be 1s) so WLOG we will assume the 2nd is a 0. Similarly, in the row below, a 1 in the 3rd position makes a 0 square. So it must be a 0.

-101- -1-1-      -01-- -0---
10001 -0-0- -->  10001 ---0-
01110 -1-1-      01110 0----
-010- -0-0-      --0-- --0--

Case 2

Case 2.1

In the row above, we can try a 0 in the 2nd spot. We must avoid 4 in a row on the diagonal since we've proven 4 in a row cannot exist, so we end those in 1s. We also need a 1 in the 3rd spot.

1----
-01--
10001
-110-
----1

If you have a 1 in the 5th row 4th spot, you get a tilted square. Thus, it must be a 0 and this makes a row of 3 again, so we know it ends in 1s.

1---- -----     1---- 1----
-01-- --1--     -011- -0-1-
10001 ----1 --> 10001 --0-1
-110- -1---     -110- ---0-
---11 ---1-     ---01 ----1

Now notice the section that has been highlighted. If we put a 1 in the top middle, we will have created Case 1 on the diagonal. Thus it must be a 0.

If you put a 0 in the 5th spot of the 2nd row, we have a tilted square, so this must be a 1. This gives 3 1s in a row, so we must end it in a 0. Also, we need a 0 in the 4th row 5th spot to avoid a square of 1s.

1-0-- --0--      1-0--- ------
-0110 ----0      -01110 -01110
10001 -0--- -->  10001- --001-
-110- ---0-      -1100- --100-
---01 -----      ---01- ------

But notice the highlighted section is simply Case 2.1 in reverse.

Case 2.2

Thus, in the row above, we must have a 1 in the 2nd spot.

-1---
10001
-110-

If we put a 0 in the 4th spot, then you need a 1 in the 3rd and we have 3 0s in a row, so they must be ended in 1s. But this makes a tilted square, so a 1 is required in the 4th spot. We know the middle must be a 0 (to avoid Case 1).

-110- --1--      -101-
10001 ----1 -->  10001
-110- -1---      -110-
---1- ---1-      

The row above cannot have a 1 in the 4th spot due to a tilted square. So it must be a 0. Thus, a 1 is required in the 2nd spot.

---1- ---1-      -1-0- -1---
-101- -1---      -101- ---1-
10001 ----1 -->  10001 1----
-110- --1--      1110- --1--

Case 3

A 0 in the 3rd spot makes a diamond, so it must be a 1. If we put a 1 in the 2nd or 4th spot, then we will have Case 2. Thus, they must both be 0s.

-010-
10001
-101-

A 1 in the row below in the 2nd spot will make a tilted square. Due to symmetry, this means a 1 in the 4th spot will do the same. So both must be 0s. But this makes a square.

-010- --1--     -010- -----
10001 1---- --> 10001 -0-0-
-101- ---1-     -101- -----
-1--- -1---     -0-0- -0-0-

Case 4

We know that we can't put 111, 110, or 101 on the top since those scenarios have already been disproven. The only remaining option is 010.

-010- -0-0-
10001 -----
-010- -0-0-

Two in a row

Lets look at boards where the longest length is 2 in a row.

1001

There are two options for the row below;

1.    2.
1001  1001
-11-  -01-

Case 1

Adding a single 1 to the 2nd row makes it similar to Case 2 of the "Three in a Row". So we know we must book-end it with 0s.

1001
0110

If we add a 0 in the 2nd spot on top, then we need a 1 in the 3rd. But notice how this is again the same as Case 2 of "Three in a Row" on the diagonal. Thus, we cannot add a 0, but instead it must be a 1. By symmetry, so must the 3rd spot. Again, we must bookend the 1s with 0s.

-01- -0--     0110
1001 1-0- --> 1001
0110 -1-0     0110

To avoid a diamond of 0s, we need 1s on the ends of the 2nd row.

-0110-
110011
-0110-

You can see that the original pattern is repeating itself above and below. So it must be extended.

            -0110-
-1001-      110011     1---1-
001100      001100     ------
110011 -->  110011 --> ------
001100      001100     ------
-1001-      110011     1---1-
            -0110-

Case 2

In order to avoid 3 0s in a row, we need a 1s in the 2nd column of the rows above and below. Similarly, we need 1s on the diagonal to avoid more than 2 0s in a row on that diagonal.

-1-1
1001
-01-
11--

To avoid more than 2 1s in a row, we can add some 0s.

-1-1 ----
1001 --0-
-010 -0-0
110- --0-

One in a Row

Trivially, we can see that the pattern doesn't work.

101 1-1
010 ---
101 1-1

Conclusion

So we have shown that there are no solutions containing 5 in a row, and all solutions with 4 in a row lead to contradictions or 5 in a row. Similarly for 3 in a row and 2 in a row. Lastly, the trivial pattern with 1 in a row is obviously not a solution either.

Therefore, there are no colourings of the grid (and thus the plane) that do not permit a monochromatic square.

Answer 3

Edit: The following is incorrect. I misread the question, and thought that a square included all of the points inside the square. However, only the corners are of interest. Thanks to Mike Earnest for pointing this out.

I think that:

Not all planes have a monochromatic square

Because:

Consider the plane where, for any pair (x,y) it is coloured 0 if $\sqrt{x^2 + y^2}$ is rational. Otherwise, it is coloured 1. This creates "infinitely dense" rings of both colours centred around the origin.

In this plane:

It is clear to see that every point is coloured, so it satisfies A1. Any line of any finite length goes through different radii, because lines of constant radii are curved. If a line goes through different radii, then some radii must be irrational and some must be rational, so the line satisfies A2.

Construction of squares:

It is impossible to construct a monochromatic square in this plane. Any square must have a line segment of finite length, which means it must go through different radii. Going through different radii implies different colours (again, because some radii will be irrational and some will be rational). This means that any square (or indeed any polygon) must not be monochromatic.

Note: I have assumed that you are talking about the plane $R^2$, not only the integer grid $Z^2$.

Answer 4

The original question was to construct the monochromatic square. Thanks to the reference to Gallai's theorem I found the following article Coloring and extremal problems in combinatorics.

It contains Gallai's theorem (Theorem 3.6) and also a proof that to construct a square, we need an nxn grid with 13 <= n < min{VW(8), 5.2^(2^40)} and where VW(8) is the so-called classical Van der Waerden number for n points. The best bounds for VW(8) are 11495 <= VW(8) <= 2^(2^(2^(2^(2^17)))).

So, it seemed that nobody had found a construction of the square yet! I was going to reproduce the graph that showed we need a grid of at least size 13, since there exists a grid of size 12 that does not contain a monochromatic square. But then I noticed that their definition of square seems to only include squares that are positioned orthogonal to the grid. Bummer!

Their grid does contain monochromatic squares, such of the form {A, A+(2,2), A+(4,0), A+(2,-2)}.

I guess that my question isn't answered yet. But here's the proof--in the form of a coloring--that we need a grid of at least size 6 to be able to construct a square for all colorings. None of its 50 squares is monochromatic. For n=6 a grid of 6x6 contains 105 squares, etc.

(thanks to @Trenin)

So, to clarify my idea, if for ALL colorings of a large enough grid there is ALWAYS a monochromatic square, then we can use that pattern to find a monochromatic square in the plane by overlaying the grid ANYWHERE in the plane. That is de facto a construction of a monochromatic square. On the other hand, if we find ONE coloring of a grid that does not have ANY monochromatic square, then we can not use that size of grid to find a monochromatic square . . .

Answer 5

Not quite sure about your definition of 'Square'.

If you consider a 'square' to be a filled square or even only the outline (= lines only) of a square, then No.

Extend a chess board to infinity -- there will never be a square of same-colored elements.

Proof:

Assume your points have integer coordinates $((1,1), (1,0), (12345,6342)$, etc.). Then you get a chess board pattern with the following coloring rule: $x+y$ even => color $0$; $x+y$ odd => color $1$.This means that, no matter in which direction you move, the next point will always have the opposite color (since you are only changing $1$ coordinate, and so going from odd to even or vice versa). But to create a non-trivial square (either outline or filled) you need to have at least two neighboring points of the same color. If you don't have integer coordinates but real coordinates, Lacklub has given you the answer of constructing such a plane.

---

If you consider a square to be a set of $4$ points of which always two share either an $x$ or a $y$ coordinate (= corners of a rectangle), then YES as long as $n>4$

No for $n=4$:

$1100$
$1010$
$0101$
$0011$

EDIT: The following lemma and proof are for RECTANGLES, not for SQUARES!!!

Lemma:

if you have an $n*n$ plane, you can sort rows and columns as you like without the square-or-not-square property being affected. (obvious)

Proof for YES:

Assuming you have $n\ge4$ then you will have a row where one color appears $3$ or more times. Let this color be $0$. Since you can sort the columns, you can assume that the $0s$ are next to each other:
$000$
To prevent a square from forming, all other rows may only have one $0$ at the most (if you have $2$ or $3$ zeroes, they would form a square with the first row).
$000$
$110$
$101$
$011$
Now the next row needs to have two $1s$. However, there are only $3$ distinct possibilities of distributing two indistinguishable items in three slots. So with the next row $(n=5)$ you will inevitably repeat one of the patterns, leading to a square of $1s$.
Ergo, with $n\ge5$ you will have at least one such 'square'.

Answer 6

As an answer to the hint, a construction of an equilateral triangle can be done with no more than 7 points. The following diagrams share points 1-3 of the construction, and the construction follows Fig. 1 if point 4 is green, and follows Fig. 2 if point 4 is red. Note that the used colorings can be assumed without loss of generality. Further, if point 2 is red, consider it point 3 and rotate the diagram to proceed the construction with points 2, 4, etc. If points 1, 2 and 3 are of the same color or any point beyond 4 is of the other color, a monochromatic equilateral triangle has already been found using less than 7 points and the construction stops. The construction needs not more than 7 points. Are there any constructions of monochromatic equilateral triangles using less points?

Fig. 1.

Fig. 2.