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

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

2 Answers 2

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

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

enter image description here

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ Looks good for all $n\ge 5$ $\endgroup$
    – Daniel Mathias
    Commented May 20, 2020 at 15:53
  • 1
    $\begingroup$ Truly beautiful!! $\endgroup$
    – Bernardo Recamán Santos
    Commented May 20, 2020 at 16:07
  • 4
    $\begingroup$ n = 4 is trivial; fill the grid. n < 4 is trivially impossible. $\endgroup$
    – Joshua
    Commented May 20, 2020 at 19:30

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