Can you paint a 10x10 grid with 3 colours such that it doesn't contain any rectangles whose corners are all the same colour? Rectangles must be 2x2 or greater and parallel to the grid's sides. Computers are allowed :)
Source: Rectangle Free Coloring of Grids, https://arxiv.org/abs/1005.3750 page 28
The authors of that paper found the solution by placing one color manually and letting a computer program figure out the other two colors.
By the pigeonhole principle, every row and every column contains at least four squares of the same colour.
Let us look at this particular colour for each column : this gives a list of $10$ colours. By the pigeonhole principle, at least four of these colours are the same.
In an attempt to prove that it's impossible: in a $10\times 4$ grid, can you place four yellow dots per column in such a way that no four dots are the corners of a rectangle?
It turns out you can place four yellow dots per column in up to five columns while satisfying this condition:
If a solution exists, it will have to include a $4\times 10$ subconfiguration of the above, or similar.