On A Lattice: Part 4
Probability
Level
2
Every point on a lattice is colored either red or blue. Is there necessarily a square, with vertices on the lattice, such that the four vertices have the same color? If so, is there necessarily a finite number of them? If so, how many?
There is necessarily
such squares, where
.
There is not necessarily any such squares.
There is necessarily an infinite number of such squares.
There is necessarily 3 such squares.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Short proof: By the pigeon hole principle.
Medium proof: Build the square by first finding a finite n 1 × n 1 grid that, by the pigeon hole principle, guarantees there's two points in the same column with the same colour.
Then note that there are finitely many different ways ( n 2 − 1 ) to colour this n 1 × n 1 grid. So, by the pigeon hole principle, in any n 2 × n 2 grid of n 1 × n 1 grids, there are two n 1 × n 1 grids with the same colouring in the same big column.
In these identical smaller grids, there are two points the same colour in the same column. A third point that would create another corner of the square is the same colour in both small grids (a "third corner point").
Back to the grid of grids, look at the small grids with same colouring and find the small grid that would be another corner of a square of grids (a "third corner grid). Look at points within this small grid that align with the three points in the identically coloured grids.
The "third corner point" in the "third corner grid" is the third corner of a L-shape where all the points are the same colour, using either the all "third corner points" or using the first corner point of the first grid and the second corner point of the second grid.
Using the same structure of proof, we can build a bigger grid of grids of grids, rely on the pigeon hole principle to show there is an L-shape of grids of grids that are identically coloured and look at the final corner and similarly argue there has to be at least one of a few squares that have all 4 points the same colour.
This shows that every grid of this finite size has at least one monotone square. By the, um, pigeon hole principle, you can fit infinitely many grids of this size into an infinite lattice, which means there are infinitely many monotone squares.
Long proof: https://www.google.com.au/url?sa=t&source=web&rct=j&url=http://cs.umd.edu/~gasarch/COURSES/250/S15/monosq.pdf&ved=2ahUKEwjZwrLs-creAhWHTX0KHcxADBMQFjAMegQIBhAB&usg=AOvVaw0SxkH_Ds5z3FDgsy-ksJGG&cshid=1541892605933