Nonattacking "queens" on tiled triangles

Question

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):

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.

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:

Or, as another example,

---

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.

Answer 1

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$.