8
$\begingroup$

Can you paint the cells of a 6x6 grid in three colours, such that no three cells of the same colour lie on a straight line passing through their center?

$\endgroup$

2 Answers 2

5
$\begingroup$

There are

702 ways to paint the cells so that no row, column or diagonal contains three cells of the same color.

Of these

All of them contain at least one line of knight's moves with three cells of the same color.

$\endgroup$
8
  • 2
    $\begingroup$ How? ILP? IHATE15CHAR $\endgroup$
    – Sny
    Commented Feb 7 at 15:02
  • $\begingroup$ @SnySmartie No, just recursively filling the grid without violating the row/column/diagonal constraints, then checking the knight lines once the grid was full. $\endgroup$ Commented Feb 7 at 15:33
  • 1
    $\begingroup$ @SnySmartie link to C code $\endgroup$ Commented Feb 7 at 15:37
  • 1
    $\begingroup$ I confirmed via ILP your count of $702$. $\endgroup$
    – RobPratt
    Commented Feb 7 at 19:03
  • $\begingroup$ @RobPratt There are no other slopes with three points in a 6x6 lattice. $\endgroup$ Commented Feb 7 at 19:04
4
$\begingroup$

Via integer linear programming, the minimum number of monochromatic lines is

2.

enter image description here

$\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.