Dtyjlui

what is the smallest number of rooks that can dominate an n×n×n chessboard?
i've just finished the problem with nxn case, but i can go nowhere in the case of nxnxn, please give some hints and necessary steps.Is there any way to finish this problem without casework?

Since you’ve apparently already seen and had trouble with the proof in Engel’s Problem-Solving Strategies, I see no point in giving a hint; I’ve simply expanded that argument to try to make it a bit clearer.

Suppose that you have a dominating family of rooks. Choose a layer $L$ of the cube containing a minimum number, $m$, of rooks; we may assume that $L$ is horizontal. (In other words, I’m using the term layer to mean a planar cross-section parallel to any of the three coordinate planes.) Say that the $m$ rooks in $L$ lie on $m_x le m$ rows in the $x$-direction and $m_y le m$ rows in the $y$-direction; this leaves $(n-m_x)(n-m_y)$ cells in $L$ that don’t lie on any of those $m_x$ rows and $m_y$ columns and therefore aren’t dominated by any rook in $L$; these cells must therefore be dominated by the rooks in the layers above and below $L$. We may assume without loss of generality that $m_x le m_y$.

Now consider the $n$ layers parallel to the $xz$-plane; each intersects $L$ in a row in the $x$-direction. Thus, exactly $m_x$ of them contain one or more of the $m$ rooks in $L$, and $n-m_x$ contain no rook from $L$. Pick one, $L'$, say, that contains no rook from $L$. Its intersection with $L$ is a row in the $x$-direction that contains no rook, so only $m_y$ of the cells in this row are dominated by rooks in $L$. The remaining $n-m_y$ cells in this row must therefore be dominated by rooks in $L'$, and $L'$ must therefore contain at least $n-m_y$ rooks. $L'$ was arbitrary, so each of the $n-m_x$ layers parallel to $L'$ containing no rook from $L$ must contain at least $(n-m_y)$ rooks, for a total of at least $(n-m_x)(n-m_y)$ rooks altogether in these layers.

By the minimality of $m$, each of the $m_x$ layers parallel to $L'$ whose intersection with $L$ does contain at least one rook must contain at least $m$ rooks, so these layers must contain altogether at least $mm_x$ rooks. Thus, we must have altogether at least$$mm_x + (n-m_x)(n-m_y)$$rooks. And $m ge m_x ge m_y$, so
$$begin{align*}mm_x + (n-m_x)(n-m_y) &ge m_x^2 + (n-m_x)^2\ &= n^2 - 2m_xn + 2m_x^2\ &= frac{(2m_x - n)^2}{2} + frac{n^2}{2}. end{align*}$$

Clearly this is minimal when the first term is as small as possible. For even $n$ this when the first term is $0$, and the value of the expression is then $n^2/2$; for odd $n$ it’s when the first term is $1/2$, and the value of the expression is then $(n^2+1)/2$. The cases can be combined: the minimum value of the expression is $lceil (n^2/2) rceil$.

Added: To show that this number is sufficient, I’ll describe a dominating configuration with $lceil (n^2/2) rceil$ rooks. Number the layers of the cube from $0$ through $n-1$ in each direction, so that each cell is specified by a triple $langle a,b,c rangle$ with $0 le a,b,c le n-1$. If $m$ is a positive integer, and $a$ and $b$ are non-negative integers less than $m$, I’ll write $a oplus_m b$ and $a ominus_m b$ for the least non-negative integers congruent to $a+b mod m$ and $a-b mod m$, respectively.

If $n=2m$, place a first group of $m^2$ rooks in the cells $langle a,b,a oplus_m b rangle$ and a second group of $m^2$ rooks in the cells $langle a+m,b+m,(a oplus_m b)+m rangle$, where $0 le a,b < m$ for both groups.

If $n=2m-1$, place a first group of $m^2$ rooks in the cells $langle a,b,a oplus_m b rangle$ for $0 le a,b < m$, and place a second groups of $(m-1)^2$ rooks in the cells $langle a+m,b+m,(a oplus_{m-1} b)+m rangle$ for $0 le a,b < m-1$. (Since $frac{(2m-1)^2+1}{2} = 2m^2 - 2m + 1 = m^2 + (m-1)^2$, this is indeed the desired number of rooks.)

Note that the two cases can be combined if we note that in each of them the second group of rooks is placed in the cells $langle a+m,b+m,(a oplus_{n-m} b)+m rangle$ for which $0 le a,b < n-m$.

In both cases the first group of $m^2$ rooks clearly dominates all cells $langle a,b,c rangle$ such that $a$ and $b$ are both less than $m$. I claim that it also dominates all cells $langle a,b,c rangle$ such that $c < m$ and at least one of $a$ and $b$ is also less than $m$. Let $langle a,b,c rangle$ be such a cell, and suppose without loss of generality that $a<m$; then there is a rook in cell $langle a,c ominus_m a,c rangle$, and clearly it dominates $langle a,b,c rangle$.

The remaining cells are those $langle a,b,c rangle$ for which either (1) $c<m$, $a ge m$, and $b ge m$, or (2) $c ge m$ and at least one of $a$ and $b$ is also $ge m$, and these are all dominated by the second group of rooks, the ones with third coordinate $ge m$. This is clear for cells of type (1), since for each pair $langle a,b rangle$ with $m le a,b < n$ there is a cell $langle a,b,c rangle$ containing a rook from the second group. Now let $langle a,b,c rangle$ be a cell of type (2), and assume without loss of generality that $a < m le b$. Let $b' = b - m$ and $c' = c - m$, and let $a' = c' ominus_{n-m} b'$; then there is a rook in the second group at $langle a'+m,b'+m,(a' oplus_{n-m} b')+m rangle = langle a'+m,b,c rangle$, and this rook evidently dominates $langle a,b,c rangle$.

Below are images representing the cases $n=8$ and $n=7$.

Imagine the columns and rows of each grid as being numbered from $0$ through $n-1$ from left to right and from bottom to top, respectively. For example, the leftmost $3$ in the first diagram is in row $3$, column $0$, and the rightmost $1$ is in column $3$, row $2$. To identify a rook in cell $langle a,b,c rangle$ of the cube, I place a $c$ in column $a$, row $b$ of the diagram. Thus, both diagrams show rooks in cells $langle 2,0,2 rangle$, $langle 2,1,3 rangle$, $langle 2,2,0 rangle$, and $langle 2,3,1 rangle$; the first shows a rook in cell $langle 5,6,7 rangle$, the second in cell $langle 5,6,4 rangle$. The $16$ rooks indicated in the lower left comprise the first block; the $16$ (resp. $9$) in the upper right comprise the second block.

This question is equivalent to asking for the size of the smallest maximal partial Latin square.

Definitions: A partial Latin square is an $n times n$ matrix in which non-empty cells contain symbols from an $n$-set, say $N:={1,2,ldots,n}$, without duplicated symbols in any row or column. It is maximal if no symbol may be added to an empty cell without violating the partial Latin square property (i.e., without a duplicated symbol in a row or column).

The equivalence is straightforward: if symbol $s$ appears in cell $(i,j)$ then we put a rook in cell $(i,j,s)$.

Diane Donovan attributes a proof that $lceil n^2/2 rceil$ non-empty cells (or rooks) are required and sufficient (among other related results) to Horák and Rosa (which I don't have immediate access to).

D. Donovan, The completion of partial Latin squares. Australas. J. Combin. 22 (2000), 247–264.

P. Horák and A. Rosa, Maximal partial Latin squares. Graphs, matrices, and designs, 225–235, Lecture Notes in Pure and Appl. Math., 139, Dekker, New York, 1993.