Let $n$ be a positive integer. David has six $n\times n$ chessboards which he arranges in an $n\times n\times n$ cube. Two cells are "aligned" if they can be connected by a path of cells $a=c_1,\ c_2,\ \dots,\ c_m=b$ such that all consecutive cells in the path share a side, and the sides that the cell $c_i$ shares with its neighbors are on opposite sides of the square for $i=2,\ 3,\ \dots\ m-1$. Two towers attack each other if the cells they occupy are aligned. What is the maximum amount of towers he can place on the board such that no two towers attack each other?
Problem
Source: 2022 Mexican Mathematics Olympiad P2
Tags: 3d, chess, combinatorics
VicKmath7
09.11.2022 18:20
Cute. The answer is $\lfloor \frac{3n}{2} \rfloor$. The construction is to take three faces of the cube sharing an vertex and put rooks in the main diagonals of three grids $\lfloor \frac{n} {2} \rfloor \times \lfloor \frac{n} {2} \rfloor$ in these faces (one from each face; basically we divide each face into four almost identical grids (exactly identical in the even case) and we take appropriate three of these). The bound is implied by a double counting argument: it is easy to see that each square without a rook is attacked at most twice, and each rook attacks $8n-2$ squares, hence if we denote by $R$ the number of rooks, we get $2(6n^2-R) \geq (8n-2)R$ and this rearranges to $R \leq \frac{3n}{2}$, done.
Justpassingby
11.11.2022 09:27
I proposed this problem : ) Unfortunately, it turned out to not be original: https://artofproblemsolving.com/community/c6h1831726p12266053?fbclid=IwAR2_yY128rvchAvwvxaDcGkR7mnaWypIBE8VM8WLFRguRedBjjoJE5yPSj8 The original solution I envisioned involved proving each "line" (be it a column or row) may only be attacked once. It's equivalent to the double counting argument above.