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
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).
No comments:
Post a Comment