Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
@Theo: I guess you want the OP to edit the old question instead of asking a new one? –  Qiaochu Yuan Jul 22 '11 at 22:26
    
@Qiaochu: Yes, absolutely. I don't think we should encourage re-posting questions and I don't like the fact that the OP just asked this question an hour ago, and decides "can go nowhere". I guess didn't try hard enough. –  t.b. Jul 22 '11 at 22:28
    
What have you tried? For example, is it obvious that the answer is somewhere from $n^3/(3n-2)$ to $n^2$ rooks? –  Henry Jul 22 '11 at 22:32
    
My intuition and "space geometry" is bad,so i really need some hint... –  abcde Jul 22 '11 at 22:49
1  
@abcde: This is a good question, but please go edit your old question to make it clear (like this question here) instead of ignoring it and asking the question again. –  ShreevatsaR Jul 23 '11 at 5:51
add comment

2 Answers 2

up vote 3 down vote accepted

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

n = 8 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.

share|improve this answer
    
You've derived a lower bound, not an upper bound, as far as I can tell. –  joriki Jul 23 '11 at 20:19
    
I had the impression that this was the part that was giving the OP difficulty. When I get back from errands this evening I’ll edit the answer to include a proof of sufficiency. –  Brian M. Scott Jul 23 '11 at 21:43
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.