Painting a 4x6 grid with 2 colours

Question

Can you paint a 4x6 grid with 2 colours such that it doesn't contain any rectangles whose corners are all the same colour? Can you do it without a computer? Rectangles must be 2x2 or greater and parallel to the grid's sides.

Good luck!

Answer 1

Absent the no-computers tag, I just wrote a quick Python script:

The formulation of the problem was pretty easy too, just

Treat each grid cell as a position in a (in this case, 24-digit) binary number. Each rectangle can be represented as a bitmask with 1s at the positions of its corners. There are 90 such masks. Now just enumerate the first $2^{24}$ numbers, and for each mask you can check whether the number totally intersects it, or totally doesn't (i.e. the AND of the number and the mask is either equal to the mask, or zero). If none of the masks match this criterion, then the number is a solution. This is the first one I found, but it is one of 720 solutions (actually 360 solutions if you don't distinguish between a coloring and its inverse).

I did some more exploring, and

It seems that there aren't too many (types of) grids that can support this. All 1xN grids are trivially solutions. For 2xN grids, you can always make one row entirely one color, and the other the other color. For 3xN, you can do up to N=6, but 3x7 fails (and therefore anything bigger also fails). As shown here, 4x6 works. But 5x5 fails, meaning that this is an exhaustive list (1xN, 2xN, and anything that fits in a 4x6 grid).

Answer 2

Here's a quick [no-computers] way of finding a solution:

Consider a set $A := \{a,b,c,d\}$ of four elements, and the set $B := \{\{a,b\},\{a,c\},\{a,d\},\{b,c\},\{b,d\},\{c,d\}\}$ of the six possible pairings of those four elements. Label the rows of a rectangle from $A$, and the columns from $B$. Now color the cells of the rectangle blue if the row label is contained in the column label, otherwise red.

Proof that this is a correct coloring: If there were a blue rectangle, then the two column labels of the rectangle corners would both contain the two row labels. This is impossible, since any two different elements of $B$ have at most one element of $A$ in common. Analogously, if there were a red rectangle, then the same argument would hold for the complements of the column labels.

Also, here's a proof that the limits in hdsdv's answer are correct:

Since hdsdv already provided examples, it remains to show that there are no valid $3\times 7$ or $5\times 5$ rectangles. A $3\times 7$ rectangle is impossible for the following reasons: Every row of 3 contains at least one double (a pair of cells with the same color). There are six possible doubles (three positions times two colors). Since there are seven rows, by the pigeonhole principle, there are two rows with the same double. Those two doubles form a rectangle together.

Excluding the 5x5 case is a tad more difficult: Each row contains at least four doubles. There are twenty possible doubles, so to prevent duplicate doubles each row must necessarily contain exactly four doubles. This is possible only if each row has three cells of one color and two of the other. Furthermore each double must occur exactly once, which means that there must be $10$ red doubles in total. But in each row there is an odd number of red doubles (1 or 3), and there are five rows, so the total number of red doubles must be a sum of five odd numbers and thus odd. This is a contradiction, since $10$ is not odd.

Answer 3

Frame Challenge

The original text of the puzzle:

Can you paint a 4x6 grid with 2 colours such that it doesn't contain any rectangles whose corners are all the same colour? Can you do it without a computer? Rectangles must be 2x2 or greater and parallel to the grid's sides.

Good luck!

Version 1:

Version 2:

I feel the challenge, as worded, does not match up to the expected puzzle and is heavily open to interpretation.

I believe what the challenge was intended to be was: "Can you fill the squares of a 4 by 6 grid with two colors, such that no square has the same color in all four adjacent squares." Any rectangle will have corners and sides the same color, otherwise it is not a rectangle (or is a multicolored rectangle on a separate surface, which doesn't fit with the color limit or grid). Also, painting is not the same as filling grid squares. And neither of my solutions contains any rectangles, but the puzzle does not state that rectangles have to be used. My answers do fit a loose interpretation that each grid square must not have all four corners (or sides) the same color. I considered doing a third one actually using rectangles made from squares the same size as the grid squares, but not overlapping with the grid squares, but I think this was enough.