9
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ No. Square is a kind of rectangle, and therefore, when a square is one by one unit, it fails. $\endgroup$ – Omega Krypton Sep 20 at 7:51
  • $\begingroup$ Good catch. I mean rectangles that are 2x2 or larger. $\endgroup$ – Dmitry Kamenetsky Sep 20 at 10:41
  • $\begingroup$ @DmitryKamenetsky you should edit that information into your post as it is pretty much important. $\endgroup$ – Zoma Sep 20 at 13:10
14
$\begingroup$

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

enter image description here

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).

$\endgroup$
  • $\begingroup$ Great work and very quick! Although I was hoping that people can do it without a computer, so I updated the description. $\endgroup$ – Dmitry Kamenetsky Sep 20 at 0:59
  • 2
    $\begingroup$ @DmitryKamenetsky For future reference, you may add no-computers tag. For now, it's better to let it be and not adding the constraint as it may invalidate this answer :) $\endgroup$ – athin Sep 20 at 1:13
  • $\begingroup$ Great exploration. You are correct that 3x7 fails. $\endgroup$ – Dmitry Kamenetsky Sep 20 at 2:29
  • $\begingroup$ Assuming that the grid is made of little squares, the top-left $3\times 3$ square in your solution does contain a rectangle. It was never said that the sides of the rectangles should be vertical or horizontal ;) $\endgroup$ – Arnaud Mortier Sep 20 at 8:40
  • $\begingroup$ @ArnaudMortier Yes, I assumed that the question meant that the rectangles were along gridlines. If not, the problem is trivially impossible because every square contains infinitely many rectangles that are all the same color at the corner. $\endgroup$ – hdsdv Sep 20 at 8:47
6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ That's just brilliant! $\endgroup$ – Dmitry Kamenetsky Sep 20 at 12:39
  • $\begingroup$ I love it! I would not be at all bothered if the check mark moved to this answer. $\endgroup$ – hdsdv Sep 20 at 12:54
  • $\begingroup$ @hdsdv you could create a bounty to reward this answer if you think that Magma deserve to be rewarded. I guess it is better if an accepted answer stay as so. $\endgroup$ – Zoma Sep 20 at 13:13
  • $\begingroup$ I see. I guess technically mine came in first since the no-computers tag wasn't applied. I just think this is more in the spirit of the intended solution, and it's terribly elegant! $\endgroup$ – hdsdv Sep 20 at 13:24
1
$\begingroup$

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:

No rectangles, only circles

Version 2:

No rectangles, only triangles

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.

$\endgroup$
  • $\begingroup$ I admire your creativity! $\endgroup$ – Dmitry Kamenetsky Sep 21 at 2:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.