15
$\begingroup$

Shade 32 cells, four on each row and column, of an 8 x 8 blank chessboard (all its cells originally white) so that a rook sitting on any shaded cell can reach any other shaded cell, moving just along other shaded cells.

If not possible, what is the size of the largest square board on which this can be done, i.e. shading four cells of each row and column creating a connected territory for a rook lying on any of its cells.

Problem based on a similar one communicated by Stan Wagon (http://stanwagon.com/pow/), who asks whether 3 cells of each row and column can be so shaded in a n x n (n > 4) board.

$\endgroup$
9
  • 1
    $\begingroup$ The problem with 3 cells and $n>4$ is The American Mathematical Monthly problem 12137 (October 2019). $\endgroup$
    – RobPratt
    May 19 '20 at 22:08
  • 3
    $\begingroup$ I had trouble understanding the problem because I imagine the rook jumping from the start to the destination cell. You should make clear that all the cells between the start and the end of each move must be shaded. The shaded region must be orthogonally connex. $\endgroup$
    – Florian F
    May 19 '20 at 22:28
  • 2
    $\begingroup$ @BernardoRecamánSantos math.lsu.edu/~mahlburg/teaching/handouts/2018S-3903/12008.pdf $\endgroup$
    – RobPratt
    May 20 '20 at 3:30
  • 1
    $\begingroup$ Connex doesn't seem to be the right term, according to Wikipedia's definition. "Orthogonally connected" probably gets the point across well enough. $\endgroup$
    – Nathaniel
    May 20 '20 at 13:12
  • 1
    $\begingroup$ Sorry, I thought it was a typo like othogonally. 😉 $\endgroup$
    – RobPratt
    May 20 '20 at 13:24
20
$\begingroup$

I started with this:

 - - X X X X - -
 - - X X X X - -
 X X - - - - X X
 X X - - - - X X
 X X - - - - X X
 X X - - - - X X
 - - X X X X - -
 - - X X X X - -

Pushed things this way and that, ended up with this:

 - - - X X X - X
 X - X X - - - X
 X X X - - - - X
 X - X - - - X X
 X X - - X - X -
 - X - - X X X -
 - X X X - X - -
 - - - X X X X -

Similarly, on 9x9:

 - - - X X X - - X
 - - X X X - - - X
 X X X - - - - - X
 X X - - - - - X X
 X - - - - X X X -
 X X - - - X - X -
 - X X - - - X X -
 - - X X X - X - -
 - - - X X X X - -

And on 10x10:

 - - X X X X - - - -
 - - - X X X X - - -
 - - - - X - X X - X
 X - - - - - - X X X
 X X - - - - - - X X
 X X - - - - - - X X
 X X - - - - - X X -
 - X X - - - X X - -
 - - X X - X X - - -
 - - X X X X - - - -

It took me a while to get there, but that one suggests an emerging pattern.

And here is an expandable solution for any $2n\times 2n$ grid.

enter image description here

$\endgroup$
4
  • $\begingroup$ Great! Is this the largest square board on which this can be done? $\endgroup$ May 19 '20 at 19:07
  • 1
    $\begingroup$ @Bernardo 9x9 and 10x10 Is there a limit? $\endgroup$ May 19 '20 at 22:12
  • $\begingroup$ @Daniel Matias Don´t know! $\endgroup$ May 19 '20 at 22:17
  • 3
    $\begingroup$ @Bernardo $2n\times 2n$, unlimited. Probably something similar for $2n+1$, but I'm done for now. $\endgroup$ May 20 '20 at 0:47
19
$\begingroup$

Here's an expandable solution for $n\ge 5$ (even or odd):

enter image description here

$\endgroup$
3
  • 2
    $\begingroup$ Looks good for all $n\ge 5$ $\endgroup$ May 20 '20 at 15:53
  • 1
    $\begingroup$ Truly beautiful!! $\endgroup$ May 20 '20 at 16:07
  • 3
    $\begingroup$ n = 4 is trivial; fill the grid. n < 4 is trivially impossible. $\endgroup$
    – Joshua
    May 20 '20 at 19:30

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.