[Math Puzzle] Day12

e.g. take the color C at (0,0), arbitrarily move along the positive x-axis until you reach the same color C at some coordinate (X,0). move in the positive y direction for both aforementioned coords until (0,Y) and (X,Y) share the same color? if you take all of R2, this is bound to happen --> infinity.

what if the color at (0,0) is green, and there's only 1 green on our entire coordinate system?

since there is a finite number of colors, you are bound to end up with a rectangle somewhere (and the origin choice was arbitrary).

Consider the X-axis, (X,0). Since there is a finite number of colours, and an infinite number of points, at least 1 of the colours is repeated infinitely many times. Call this colour ONE. Remove the columns where the colours are not ONE.

Now repeat for (X,1), at least one of the colours is infinite, call this colour TWO. Remove all columns not colour TWO in the (X,1) row.

So now we have a map with all ONE in the (X,0) and all TWO in the (X,1).

Keep going for (X,2) ... (X,6). We have 7 rows, and 6 colours. One of the colours is repeated. So there are infinitely many rectangles of the repeated colour.

Edit: Actually, you can keep going along the Y direction, one of the colours will appear infinitely many times. So you can have the existence of a infinite two-d rectangular grid of 1 colour.

If it's too hard to understand I will draw some pictures later.
First choose a horizontal line that contains 6 points of the same colour (this must be possible). Through these 6 points we draw 6 vertical lines, and consider each 6-tuple of points that are on the 6 vertical lines that are on a horizontal line. Although there are infinitely many of these 6-tuples we will only consider 7*6^6 + 1 many of them (7*6^6 + 1 is a very conservative estimate, but it works). Note that each 6-tuple has 6^6 different ways of colouring, so for 7*6^6 + 1 many of 6-tuples, at least 7 6-tuples have the same colours. Furthermore, for each of these 3 6-tuples, each of the 6 points must have difference colours (otherwise we have a rectangle of the same colour). Now out of these 7 6-tuples, draw horizontal lines across them, and consider the intersection of these 7 horizontal lines with another vertical line (there are 7 intersections). Thus out of these 7 points at least two have the same colour, which will form a rectangle with two other points on some of the 7 6-tuples.

I didn't read anything in spoilers, so here's my reasoning. Take a column centered on the x-axis with length 2y. Since you have 6 colors to use on those 2y+1 points, there are P(2y+1,6) ways to set up this column. This is a finite number, so if you take exactly that number of columns (all centered on the x-axis but with different x-values), you'll either have two identical ones or every single possible coloring scheme. If you take one more, you have two identical ones for sure. This will necessarily produce a rectangle as the colors line up (say, 2 blues in both columns, which have respective common y-values) as long as 2y+1 > 6, so as long as y>=3.

Let a row contain an infinite sequence of elements belonging to {1,2,3,4,5,6}. A row is guaranteed to contain at least 2 of some element (since there are greater than 6 elements in the sequence). Let N be the width that separates these two identical elements in a row.

Define the column to be an infinite sequence of rows. No two rows in a column can be identical, nor can any two adjacent sub-sequences (both) containing identical elements be identical, lest there exist a rectangle.

An N-wide sub-sequence containing identical elements must exist and has only 6^N permutations. There are infinite unique rows in the column, but not infinite permutations of this sub-sequence.