Newsgroups: sci.math
From: hoey@AIC.NRL.Navy.Mil (Dan Hoey)
Date: 1 May 92 19:16:54 GMT
Subject: Re: rooks in d dimensions

pr...@godel.mit.edu (Jim Propp) asked:

> Given a d-dimensional chess board of size n, what is the smallest
> number of rooks that can be placed on the board so that each of
> the n^d cells is either covered or attacked?

Someone wrote:

>It is not clear to me what happens when n>=3 (what about just 3^3?).

alope...@neumann.waterloo.edu (Alex Lopez-Ortiz), correcting for
finger dyslexia (not dislexia), wrote:

> This case is easy. Each rook covers at most 7 non-covered squares
> since there are 27 squares the minimum number is ceil(27/7)=4.

But that's not tight.  Consider the least-populated of three parallel
planes.  All points not covered or attacked by a resident rook must be
attacked by different nonresident rooks.

Case 1: If there are no rooks resident, there must be 9 nonresident,
        so at least 9 over all.
Case 2: If there is just one rook resident there must be four rooks
        nonresident, so at least five rooks on the cube.
Case 3: If there are two or more rooks resident on the *least*
        populated plane, there must be six or more rooks on the cube.

So there must be at least five rooks, and this is achievable using a
straightforward floor(n/2)^2+ceiling(n/2)^2 upper bound construction.

For general n^3, this says there must be at least max((n-k)^2+k,nk)
rooks, for k the minimum plane population.  This is tight for n<=4 and
n=6 using the same upper bound, but in other cases there is a gap
between the bounds.

   n   lb   ub
   5   11   13
   6   18   18
   7   21   23
   8   28   32
   9   36   41
  10   40   50
  11   53   61

The lower bound is (3-sqrt(5))n^2/2+o(n^2) ~ .382n^2, while the upper
bound is n^2/2+o(n^2).

The technique can be generalized to yield a lower bound of

  max[0<=a<=d] min[0<=k<=n] max((n-k)^(d-a)+k,(n^a)k).

Here k is the minimum rook population of n^a parallel hyperplanes of
dimension d-a.

Dan Hoey
Hoey@AIC.NRL.Navy.Mil