7
$\begingroup$

It is known that a $4\times6$ grid can be colored with two colors such that no four cells of the same color form an axis-aligned rectangle. The only valid coloring, up to permutation of its columns, is

valid coloring of 4 by 6

The question is: is there a $4\times6$ grid, colored with two colors, such that no four cells of the same color form any rectangle, axis-aligned or otherwise?

Clearly, rectangles must be non-degenerate.

$\endgroup$
1
  • 2
    $\begingroup$ What do you mean by "the diagonal"? $\endgroup$
    – Sny
    Mar 19 at 14:42

1 Answer 1

7
$\begingroup$

I think the following works

This arrangement is symmetric - mirroring top-to-bottom is equivalent to swapping the colours. Therefore you need only check a single colour for the existence of a rectangle.

O X O X
O X X O
O O X X
X X O O
X O O X
X O X O

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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