5
$\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?

$\endgroup$
5
  • 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 at 0:34
  • $\begingroup$ To add to @Bubbler, the n=25 case is IMO 2010 ShortList C3. $\endgroup$ – Ankoganit Feb 23 at 2:56
  • $\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 at 17:16
  • 2
    $\begingroup$ I’m voting to close this question because it belongs to an ongoing contest. $\endgroup$ – WhatsUp Feb 25 at 14:39
  • $\begingroup$ My apologies. A friend sent this over and asked me to ask online. I wasn't aware that it was from something ongoing. Yes, please close this. $\endgroup$ – mahal Feb 25 at 19:02