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$ 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
    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$ 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$ 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
    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$ Jul 31, 2012 at 15:23
  • $\begingroup$ Cristi, thanks! I didn't know about either of these references. $\endgroup$ 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
    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$ 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$ 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$ 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$ 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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