I was recently given the following math puzzle, which I’d never heard before: prove that if you have an infinite plane with each point colored one of 4 colors, there must be a rectangle whose 4 corner points are the same color.
I thought about it for a while, and came up with the following perhaps nonintuitive result:
Not only is this true for 4 colors, it’s true for ANY finite number of colors. And you don’t need an infinite plane, you just need a finite k-by-k grid, where k is some number that depends on the number of colors (obviously larger and larger as the number of colors increases). And you don’t need to consider arbitrarily rotated rectangles, just grid-aligned ones.
I’m not sure if this is already a well-known problem. If not, and if people are curious, I’ll post details of the proof I came up with, which is (I think) quite elegant.
Maybe I am misunderstanding the problem but I think you’d have to be able to draw the rectangle. You don’t even need an infinite plane.
Grab a sheet of 8.5x11 paper, take a green, black, blue and red pen and try to make columns and rows of dots where you could not achieve your result. You cannot do it.
I guess if you want to get hyper particular and say you cannot draw a truly straight line (space itself is curved) or the dots are infinitely small and just a smidge out of alignment to draw a perfect rectangle you might have a case but that is pushing it. On an infinite plane with an infinite number of dots you’d really have to get staggeringly precise to say this could not be done.
The rectangle can be any size, right? And the “points” that you’re colouring are equally-spaced vertices on a rectangular grid (like colouring all the corners on a piece of graph paper)
'Cos my original thought was WTF you’re on drugs that theory was totally wrong … but I was thinking the points had to be next to each other.
Lemme think about this - I think you may be right, but I’m not sure on the proof yet
One of my friends came up with a simpler solution mine (although I think mine is cooler and more recursive), so here’s his, for the 3-color-case (to keep the numbers small).
Assume you have a rectangular grid that is 4x82 (4 being n+1 and 28 being n^(n+1) + 1), with each point being one of 3 (n) colors.
Look at all the points in the bottom row (assuming there are 4 rows of 82 points, not the other way around), and count how many points in that row are of each color. Because there are 82 points and 3 colors, at least one color must have at least 28 points (27 * 3 being 81). So pick 28 points on the bottom row with the same color. Now look at the 28 points directly above those 28 points. Because there are 28 points and 3 colors, there must be at least 10 points among those points that are the same color. Now look at the 10 points directly above those 10 points. There must be 4 of those that are the same color. Now look at the 4 points directly above those 4 points. There must be at least 2 that are the same color. So those 2 points are the same color. Directly beneath them are 2 points that are the same color. Directly beneath those are 2 points that are the same color. And directly beneath those are 2 points that are the same color. Of those 4 rows-of-the-same-color, 2 must have the same color, as we have only 3 colors. Those 2 rows must form a rectangle.
My solution involves assuming that the proof is true for number-of-colors-n, and then, with number-of-colors-n+1, constructing a situation where a subgrid must either have a point of color n+1 in it, which forms a rectangle, or doesn’t, which means that by recursion, it must already have a rectangle. I can go into more details if someone is curious but it’s going to be a bit tricky without a whiteboard.