4
$\begingroup$

I have an $8 \times 8$ board. On the board, I want to choose 2 unit squares in each column and row such that none of the chosen squares are touching. This means they cannot share a side or a corner. How many ways can I choose the unit squares? What if the board is $9 \times 9$?

Now, I want to choose 3 unit squares in each column and row such that none of the chosen squares are touching (touching defined similarly). What is the minimum dimensions of the square board so that this is achievable, and on that board, how many ways is it doable?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ To close voters: I don't think it is a textbook problem. There is a general fact that it is possible in exactly 2 ways to choose $4n^2$ non-touching squares on a $4n\times 4n$ board so that each row/column has exactly $n$ squares chosen. The proof is non-trivial; IIRC $n=25$ version has appeared on an olympiad (either regional or international, I can't remember which). This fact is sometimes used in Star Battle puzzles too. $\endgroup$
    – Bubbler
    Feb 23, 2021 at 0:34
  • $\begingroup$ To add to @Bubbler, the n=25 case is IMO 2010 ShortList C3. $\endgroup$
    – Ankoganit
    Feb 23, 2021 at 2:56
  • 1
    $\begingroup$ This a question from the SUMaC 2021 entrance exam, which is ongoing and ends Mar 10. They specifically asked not to share the problems with anyone, nor to consult the internet for help. $\endgroup$
    – Mike Earnest
    Feb 23, 2021 at 17:16
  • 1
    $\begingroup$ Since this contest has now ended and per our policy we will unlock such questions and undelete answers once the contest has concluded, I am doing so here. $\endgroup$
    – Rubio ♦
    Dec 2, 2021 at 7:51

1 Answer 1

Reset to default
6
$\begingroup$

8x8:

2 ways: 

     . X . X . . . .
     . . . . . X . X
     . X . X . . . .
     . . . . . X . X
     X . X . . . . .
     . . . . X . X .
     X . X . . . . .
     . . . . X . X .

and the same mirrored.

Why not more?

We can count grid points: The no-touching means every square occupies 4 of them with no sharing. This means we need to place 64 corners in a 9x9 grid. Of the 64 at most 16 can lie on the boundary, therefore 48 must lie on the 7x7 inner grid, i.e. only a single inner grid point can be left unoccupied. It cannot be fewer because then only two parities out of four (even/odd column even/odd row) could be realised. A single inner (boundary must be special cased) grid point can only be left unoccupied if the adjacent squares are arranged as in the centre of the pattern shown above and all the other squares are forced by the requirement that all other grid points must be covered. As the four emerging regular grids must all be 2x2 forces the location of the single unoccupied grid point.

9x9 (partial answer):

at least 40 ways: 

     . . X . X . . . .
     . . . . . . X . X
     X . . . X . . . .
     . . . . . . X . X
     X . X . . . . . .
     . . . . . X . X .
     . X . X . . . . .
     . . . . . X . X .
     . X . X . . . . .

Columns 1 and 3 can be swapped. Independently, column 5 or row 5 (but not both) can be swapped for column/row 7 or 9. There are four rotations of the pattern.

3 per row/column:

12x12, also 2 ways 

     . 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 the same mirrored.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Nice. Extending the pattern, for $n$ unit squares we will need a $4n \times 4n$ grid. But can we do it in a smaller grid? $\endgroup$
    – Dmitry Kamenetsky
    Feb 23, 2021 at 12:58
  • $\begingroup$ Consider a grid of side length 4n-1. For each strip of two adjacent rows, the 2n stars are locked into every other column - since this is true of every strip, no stars can be placed into the columns of the opposite parity. $\endgroup$
    – AxiomaticSystem
    Feb 23, 2021 at 13:48
  • $\begingroup$ @DmitryKamenetsky we can either count grid points (16n^2 for side length 4n-1) and square corners (16n^2) as in the answer, or make a direct argument as AxiomaticSystem did. $\endgroup$
    – Albert.Lang
    Feb 23, 2021 at 17:52

Your Answer

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

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