8
$\begingroup$

I'll start with what my question is not. My question is not Nonattacking rooks on a triangular chessboard or The number of spacing $k$ non-attacking towers on the board $\left\{(i,j):1 \le i \le j \le n \right\}$. Those questions are about taking a square grid and making a "triangular chessboard" by removing the squares of a chessboard above the diagonal.

My question is about tiled triangles of the following form (not truncated square grids):

Tiled triangle

I will define a "queen" on this tiled triangle to attack in the three directions parallel to the triangle on which the queen is located. Below, I have placed a queen on the darkest blue triangle and the light blue triangles are where the queen attacks.

Tiled triangle with shading

I am interested in the maximal number of non-attacking queens I can place on this tiled triangle. For example, I can imagine placing down queens until every triangle is under attack: enter image description here

Or, as another example, enter image description here


My questions are: For a tiled equilateral triangle of side length $n$, what is the maximal number of non-attacking queens I can add to the triangle? How many configurations have the maximal number of non-attacking queens? By side length, I mean for example that the above tiled triangles have a side-length of five.


I think my trouble has been that I'm unsure of a good coordinate system for the tiled triangle. It's two dimensional, but I take out three straight lines corresponding to the horizontal, diagonal, and antidiagonal directions when I add a queen. Further, knowing which horizontal row and diagonal I am in does not typically fix the antidiagonal I am in (there are typically two choice for the antidiagonal).

From inspection, it looks like the maximum number of non-attacking queens on a tiled triangle of sidelength $n$ is $\lceil n/2 \rceil$. Maybe induction on the length of the sides could work? It looks like adding row of triangles at the base of a maximal-number-of-queens odd $n$ triangle gives a maximal number-of-queens even $n+1$ triangle, but I am unsure of how to show this.

$\endgroup$
1
  • 1
    $\begingroup$ Are you familiar with setting up a coordinate system on a triangular grid? You have 3 directions to move in, and it uses 3 coordinates. $\endgroup$
    – Calvin Lin
    Commented Jan 29, 2021 at 2:24

1 Answer 1

2
+50
$\begingroup$

Your problem is similar to the one of placing non-attacking rooks on a triangular array of hexagons, discussed in this Math Overflow post: https://mathoverflow.net/questions/103540/hexagonal-rooks/103610. The same proof method works in your problem. I am generalizing the proof of optimality in this comment.


The maximal number of queens is $\left\lfloor 2n+1\over 3\right\rfloor$.

To place that many queens, do the following:

  1. Letting $k=\left\lfloor 2n+1\over 3\right\rfloor$, place a queen in the leftmost triangle in the $k^{th}$ row from the bottom.

  2. Place a queen in the rightmost triangle in the row below the previous.

  3. Go down the rows one by one. For each row, either place a queen in the triangle below the queen in step $1$, or the queen in step $2$, alternating each time.

Here is an illustration when $n=10$:

Here is how you prove this is optimal. Each triangle has a triple of coordinates $(x,y,z)$, where $x$ is the number of triangles a queen must move to reach the left edge, and $y$ and $z$ are the corresponding distances for the right and bottom edges. Orient the entire grid so a vertex points upward, as in your pictures. You can show that:

  • For an upward pointing triangle, $x+y+z=2n-2$, and $x,y$ and $z$ are all even.

  • For downward pointing triangle, $x+y+z=2n-1$, and $x,y$ and $z$ are all odd.

For example, when $n=4$, you can verify the possible coordinates are permutations of $(0,0,6),(0,2,4),(2,2,2),(1,1,5)$ or $(1,3,3)$.

Now, for a placement of $k$ queens, let $\Sigma_x$ be the sum of the $x$-coordinates of the queens, and define $\Sigma_y$ and $\Sigma_z$ similarly. Furthermore, let $d$ be the number of queens on downward pointing triangles. The preceding two bullets imply $$ \Sigma_x+\Sigma_y+\Sigma_z=k\cdot (2n-2)+d $$ Therefore, at least one of the $\Sigma_x,\Sigma_y$ or $\Sigma_z$ must be at most $(k(2n-2)+d)/3$. WLOG, say $$\Sigma_x\le \frac{k(2n-2)+d}3.\tag1$$

Furthermore, as $i$ ranges over the $x$-coordinates of the queens, the values $\lfloor i/2\rfloor$ must be distinct, else the queens with the same value would attack each other in the direction parallel to the line $x=0$. If there are $k$ queens, the smallest possible value of $\Sigma_x$ for which the values $\lfloor i/2\rfloor$ are distinct is

$$ \Sigma_x \ge (0+2+4+\dots+2(k-1))+d=k(k-1)+d\tag2 $$ this is because the smallest value is attained by starting with the list $0,2,\dots,2(k-1)$, and increasing $d$ of these values by $1$, since the $d$ coordinates of the downard pointing triangles must be odd.

Combining $(1)$ and $(2)$, you get $$ k(k-1)+d\le {k(2n-2)+d\over 3} $$ Divide both sides by $k$ and rearrange to get $$ k\le {2n-2\over 3}+1- {2d\over 3k}\le {2n-2\over 3}+1 $$ so $k\le \left\lfloor 2n+1\over 3\right\rfloor$.

$\endgroup$
3
  • $\begingroup$ By similar you mean equivalent, right? $\endgroup$
    – RobPratt
    Commented Jan 29, 2021 at 22:26
  • $\begingroup$ @RobPratt No, I mean similar. Every rook placement on a hexagon grid translates to a queen placement on a triangle grid (just restrict your attention to the upward-pointing triangles only), but not the other way around. This means the proof of the upper bound for the triangle grid requires a bit of extra work to rule out the extra possibilities. $\endgroup$ Commented Jan 29, 2021 at 23:10
  • $\begingroup$ Very nice! That link to MathOverflow is also helpful to see some of the literature, as one of the answers discusses an alternative style of proof of optimality in this link. $\endgroup$
    – user196574
    Commented Jan 29, 2021 at 23:18

You must log in to answer this question.

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