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$
  • 1
    $\begingroup$ The problem with 3 cells and $n>4$ is The American Mathematical Monthly problem 12137 (October 2019). $\endgroup$ – RobPratt May 19 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 at 22:28
  • 2
    $\begingroup$ @BernardoRecamánSantos math.lsu.edu/~mahlburg/teaching/handouts/2018S-3903/12008.pdf $\endgroup$ – RobPratt May 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 at 13:12
  • 1
    $\begingroup$ Sorry, I thought it was a typo like othogonally. 😉 $\endgroup$ – RobPratt May 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

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

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

enter image description here

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Looks good for all $n\ge 5$ $\endgroup$ – Daniel Mathias May 20 at 15:53
  • 1
    $\begingroup$ Truly beautiful!! $\endgroup$ – Bernardo Recamán Santos May 20 at 16:07
  • 3
    $\begingroup$ n = 4 is trivial; fill the grid. n < 4 is trivially impossible. $\endgroup$ – Joshua May 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.