6
$\begingroup$

Every point in the plane is colored either red or blue. Is it necessarily the case (i.e., is it true for all such colorings) that there exist some four points of the same color that are the vertices of a square?

$\endgroup$
7
  • 1
    $\begingroup$ I could be misreading, but it seems like this is missing at least one sentence on clarifying the circumstances we are meant to consider. $\endgroup$ – feelinferrety Dec 30 '20 at 22:29
  • 4
    $\begingroup$ I think all that's missing is the word "necessarily" before "exist" in the second sentence. $\endgroup$ – Gareth McCaughan Dec 30 '20 at 22:32
  • $\begingroup$ A bunch of people voted to close this as insufficiently clear. I've edited it to make (what I hope was) the meaning more explicit and reopened. Close-voters, if there are other things you felt should be explicit, you might want to say so. $\endgroup$ – Gareth McCaughan Dec 31 '20 at 2:46
  • 1
    $\begingroup$ I think you need to clarify that the square must have nonzero area (see Timothy's answer). $\endgroup$ – Bubbler Dec 31 '20 at 4:48
  • 2
    $\begingroup$ (too short for an answer) The so-called Gallai-Witt theorem (here, e.g.) immediately solves this. Since the G-W theorem is a much, much more general version, there's probably a more low-tech solution than that. $\endgroup$ – Ankoganit Dec 31 '20 at 4:58
2
$\begingroup$

I believe the answer is

Yes, given any colored plane, we can find a square of nonzero size whose four vertices have the same color.

Not a proof, but a heuristic argument:

Define a Cartesian coordinate system on the plane, and consider the set of lattice points $(x,y), 0 \le x,y < n, x,y \in \mathbb{Z}$. The number of points in the set is $n^2$, and the number of squares whose four corners are in the set is $(n^4-n^2)/12$ (proof). If we assume that coloring of each point and same-color-ness of each square are all independent, the expected number of square-free colorings of the given set is $$ 2^{n^2} \times \left( \frac78 \right)^{\frac{n^4-n^2}{12}} $$ where the second term dominates as $n$ increases, so it converges to zero. The first smallest value of $n$ where the above value drops under 1 is $n=8$, so I expect one can actually "prove" the result by running the condition on a SAT solver.

EDIT: A "proof" by computer. At least this gives the evidence for the yes/no part, so that a more serious attempt can be made in the right direction.

Python code to print out the Z3 code format. It encodes each point's color as a Boolean, and each square condition as "cannot be all true, and cannot be all false". So if the SAT solver gives "no solution", we are certain that there is at least one square with four corners of one color.

Running Z3 for n=7 gives unsat i.e. no solution.

$\endgroup$
2
$\begingroup$

There is a relevant paper which I came across recently connected to this question:

  • "Extremal binary matrices without constant 2-squares" by Roland Bacher and Shalom Eliahou

In it, the authors prove that

Given any $2$-colouring of a $15 \times 15$ square grid, there is a $2 \times 2$ subgrid whose four points are coloured the same.

which shows not only that

The conjecture in the question is true.

but also that

There necessarily exists a square whose sides are parallel to the axes and whose vertices are the same colour.

Further interesting points

Given that the authors only consider axis-parallel squares, it may be the case that the question can be solved by considering grids of smaller sizes and squares of all types (perhaps even $7\times 7$ as suggested by Rosie F).

$\endgroup$
1
$\begingroup$

Not an answer, but a suggestive result.

In "New Mathematical Diversions from Scientific American" (the third collection of his Mathematical Games columns), ch.12, p.134, Martin Gardner described the game of Hip, which is played on a 6x6 grid. On each turn the turn player places one of their stones on an unoccupied square. A player loses if they own four stones at the corners of a square. In the answer section, Gardner shows squareless arrangements of 18 black and 18 white stones on the 6x6 grid. He also reports that, in 1960, Robert Jewett proved that a draw is impossible on the 7x7 board.

That doesn't prove that a square is inevitable, because it leaves open the possibility that

there is some clever squareless arrangement of 23 blue stones on the 7x7 board where any further blue stone would complete a blue square, but which allows a squareless arrangement of 26 red stones.

$\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.