Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose you have a triangular chessboard of size $n$, whose "squares" are ordered triples $(x,y,z)$ of nonnegative integers that add up to $n$. A rook can move to any other point that agrees with it in one coordinate -- for example, if you are on $(3,1,4)$ then you can move to $(2,2,4)$ or to $(6,1,1)$, but not to $(4,3,1)$.

What is the maximum number of mutually non-attacking rooks that can be placed on this chessboard?

More generally, is anything known about the graph whose vertices are these ordered triples and whose edges are rook moves?

share|improve this question
    
Can you prove what the maximal number of mutually non-attacking bishops is on an ordinary n×n chessboard? –  Zsbán Ambrus Jul 30 '12 at 21:52
    
The bishop question is easy - it's 2n-2. Put bishops along two opposite edges and remove two at adjacent corners. This is maximal since there are only 2n-1 different North-East diagonals, and two of these are opposite corners so only 2n-2 can be filled. –  Carl Jul 30 '12 at 22:27
2  
The graph is regular, of degree $2n$. If you put a rook on $(n,0,0)$, the problem reduces to finding the maximum number of non-attacking rooks on the board of order $n-2$. I think the graph has enough symmetry that no matter where you put the first rook you reduce the problem to that of order $n-2$, but I'm not sure. If the graph does have that symmetry, then by induction you get more-or-less $n/2$ rooks ($(n+2)/2$ if $n$ is even, $(n+1)/2$ if $n$ is odd). –  Gerry Myerson Jul 30 '12 at 23:01
    
That's a nice idea, but I don't think it works. If you remove (2,1,0) from $G_3$, you get a path of length $3$, not a cycle. –  David Speyer Jul 30 '12 at 23:23
4  
One of the coordinates must have an average value of no more than $n/3$ among all the rooks. The maximal number of distinct nonnegative integers whose avergae is $n/3$ is $2n/3+1$. This is a better bound. –  Will Sawin Jul 31 '12 at 1:00

4 Answers 4

up vote 12 down vote accepted

Here is a paper about this problem: "Non-attacking queens on a triangle".

And here's another one "Putting Dots in Triangles"

share|improve this answer
    
Good references. The first paper (Nivasch-Lev, Mathematics Magazine 2005) ends up giving another proof of the $\lfloor 2n/3 \rfloor + 1$ bound, and the same construction to attain this bound. –  Noam D. Elkies Jul 31 '12 at 15:23
    
Cristi, thanks! I didn't know about either of these references. –  Jeremy Martin Jul 31 '12 at 19:35
    
You're welcome, Jeremy. –  Cristi Stoica Jul 31 '12 at 20:21

Nice question!

For the maximum number of pairwise non-defending rooks, Will Sawin proved an upper bound of $(2n/3) + 1$ in his comment to the original question. This bound is attained, at least to within $O(1)$, by two rows of $n/3 - O(1)$ rooks each, starting from around $(2n/3,n/3,0)$ and $(n/3,2n/3,1)$ and proceeding by steps of $(-1,-1,2)$ until reaching the $y=0$ or $x=0$ edge of the triangle. This construction generalizes Sawin's five-Rook placement for $n=6$.

On further thought, it seems we actually achieve $\lfloor (2n/3) + 1 \rfloor$ exactly for all $n$. Here's how it works for $n=12$ and $n=15$, with $(2n/3)+1 = 9$ and $11$ respectively:

                                            .   
                                           . . 
                                          . . . 
            .                            . . . . 
           . .                          . . . . . 
          . . .                        R . . . . . 
         . . . .                      . . . . . . R 
        R . . . .                    . R . . . . . . 
       . . . . . R                  . . . . . . . R . 
      . R . . . . .                . . R . . . . . . . 
     . . . . . . R .              . . . . . . . . R . . 
    . . R . . . . . .            . . . R . . . . . . . . 
   . . . . . . . R . .          . . . . . . . . . R . . . 
  . . . R . . . . . . .        . . . . R . . . . . . . . . 
 . . . . . . . . R . . .      . . . . . . . . . . R . . . . 
. . . . R . . . . . . . .    . . . . . R . . . . . . . . . . 

Starting from such a solution with $n=3m$, we can add an empty row to get an optimal solution for $n=3m+1$, and remove an edge (and the Rook it contains) to get an optimal solution for $n=3m-1$. So this should solve the problem for all $n$.

Jeremy Martin also asks:

More generally, is anything known about the graph whose vertices are these ordered triples and whose edges are rook moves?

I don't remember reading about this graph before. Experimentally (for $3 \leq n \leq 16$) its adjacency matrix has all eigenvalues integral, the smallest being $-3$ with huge multiplicity $n-1\choose 2$; more precisely:

Conjecture. For $n \geq 3$ the eigenvalues of the adjacency matrix are: a simple eigenvalue at the graph degree $2n$; a $n-1\choose 2$-fold eigenvalue at $-3$; and a triple eigenvalue at each integer $\lambda \in [-2,n-2]$, except that $\mu := \lfloor n/2 \rfloor - 2$ is omitted, and $\mu - (-1)^n$ has multiplicity only $2$.

This is probably not too hard to show. For example, the $\lambda = -3$ eigenvectors constitute the codimension-$3n$ space of functions whose sum over each of the $3(n+1)$ Rook lines vanishes. [Added later: in the comment Jeremy Martin reports that he and Jennifer Wagner already made and proved the same conjecture.]

Given that the minimal eigenvalue is $-3$, it follows by a standard argument in "spectral graph theory" that the maximal cocliques have size at most $3(n+1)(n+2)/(4n+6) = 3n/4 + O(1)$. But that's asymptotically worse than $2n/3 + O(1)$, though it's still good enough to prove the optimality of Will Sawin's cocliques of size $5$ for $n=6$ and of size $7$ for $n=9$.

Here's some gp code to play with this graph and its spectrum:

{
R(n)=
  l = [];
  for(a=0,n,for(b=0,n-a,l=concat(l,[[a,b,n-a-b]])));
  matrix(#l,#l,i,j,vecmin(abs(l[i]-l[j]))==0) - 1
}

running "R($n$)" puts a list of the vertices in "l" and returns the adjacency matrix with the corresponding labeling. So for instance

matkerint(R(7)-2)~
matkerint(R(8)-1)~

returns matrices whose rows are nice generators of the $2$-dimensional eigenspaces of the $n=7$ and $n=8$ graphs.

share|improve this answer
1  
Noam, you've scooped me! :-) Jennifer Wagner and I have recently proved this conjecture by giving an explicit basis of eigenvectors. Writeup forthcoming. (Even more generally, we conjecture that the "simplicial rook graph" --- put a vertex at each lattice point in the $n$th dilate of the standard simplex in $\mathbb{R}^d$; edges are pairs of vertices at Hamming distance 2 -- has integer eigenvalues.) Corollary: the independence number of the triangular rook graph is at most $3(n+2)(n+1)/(2(2n+3))$. But, indeed, this bond is not tight. Back to the independence question: it appears tha –  Jeremy Martin Jul 31 '12 at 4:14
    
Seems like your comment was cut off by the 600-character limit. Anyway, it's not really a "scoop" since I only conjectured it (though I see that the lower bound of $-3$ on the spectrum is not hard, and likewise for your generalization to higher dimension). –  Noam D. Elkies Jul 31 '12 at 4:34
    
I was going to ask about the independence number about the higher-dimensional simplicial rook graph. The computational evidence I have suggests that the least eigenvalue is $\min(-n,-\binom{d}{2})$. E.g., for $d=4$, $n\geq 6$, this would imply that the independence number $\alpha(n)$ is at most $a(n)=\lfloor(n+1)(n+3)/3\rfloor$. This is not a tight bound (e.g., $a(6)=21$, $\alpha(6)=16$) and I would guess that it is not even asymptotically tight. –  Jeremy Martin Aug 1 '12 at 14:36
    
The eigenvalue bound (which you probably mean to be $\max(-n,-{d\choose 2})$, not $\min$) can be proved in the same way, by writing the adjacency matrix as the sum of $d\choose 2$ adjacency matrices (one for each direction) each with minimal eigenvalue $-1$. –  Noam D. Elkies Aug 1 '12 at 14:47

For n=6 you can fit 5 rooks

(0,2,4) (4,0,2) (1,4,1) (3,3,0) (2,1,3)

For n=9 you can fit 7 rooks

(0,3,6) (6,0,3) (2,6,1) (4,5,0) (3,1,5) (5,2,2) (1,4,4)

share|improve this answer

A visualization aid, $n=10$:
           HexChess n=10

And now here are Will Swain's rook placements:
HexRooks n=6,5HexRooks n=9,7

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.