23
$\begingroup$

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?

$\endgroup$
9
  • $\begingroup$ Can you prove what the maximal number of mutually non-attacking bishops is on an ordinary n×n chessboard? $\endgroup$ Commented Jul 30, 2012 at 21:52
  • $\begingroup$ 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. $\endgroup$
    – user25199
    Commented Jul 30, 2012 at 22:27
  • 2
    $\begingroup$ 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). $\endgroup$ Commented Jul 30, 2012 at 23:01
  • $\begingroup$ 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. $\endgroup$ Commented Jul 30, 2012 at 23:23
  • 4
    $\begingroup$ 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. $\endgroup$
    – Will Sawin
    Commented Jul 31, 2012 at 1:00

5 Answers 5

13
$\begingroup$

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

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Commented Jul 31, 2012 at 15:23
  • $\begingroup$ Cristi, thanks! I didn't know about either of these references. $\endgroup$ Commented Jul 31, 2012 at 19:35
  • $\begingroup$ An earlier reference is Problem 131 in Which Way Did the Bicycle Go?, Konhauser, Velleman, and Wagon (1996). $\endgroup$
    – RobPratt
    Commented Jan 29, 2021 at 22:25
14
$\begingroup$

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.

$\endgroup$
4
  • 2
    $\begingroup$ 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 $\endgroup$ Commented Jul 31, 2012 at 4:14
  • $\begingroup$ 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). $\endgroup$ Commented Jul 31, 2012 at 4:34
  • $\begingroup$ 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. $\endgroup$ Commented Aug 1, 2012 at 14:36
  • $\begingroup$ 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$. $\endgroup$ Commented Aug 1, 2012 at 14:47
7
$\begingroup$

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

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

$\endgroup$
6
$\begingroup$

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)

$\endgroup$
2
$\begingroup$

This has a connection with additive permutations, asked about here: Are there enough additive permutations? .

http://oeis.org/A002047 has references to a similar problem involving a hexagonal board and counting the number of placements. (The Bennett and Potts reference calls the piece a 'brook'.) This number also counts the permutations. A recent ArXiv paper http://arxiv.org/abs/1510.05987 appears to provide an asymptotic estimate. Note that placement on a hexagonal board gives one for the triangle, but there may be placements in a triangle corner that are not realizable in the hexagon.

Gerhard "Cutting Corners For More Results" Paseman, 2017.03.13

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .