Consider an $n\times n$ board. Assume that the sides of the board are parallel to the north-south and the east-west directions. If a piece of "broken queen" is placed on this board, it "covers" each cell in the same column, each cell in the same row, each cell in its southeast direction, and each cell in its northwest direction. What is the minimum number of broken queens required to cover the board?
If $m_n$ is this minimum number, I know that $m_n\ge \lceil (2n-1)/3\rceil$. To show this, let $m=m_n$ and consider a 'covering' of the board by $m$ broken queens. When $n>1$ it is clear that $m<n$. Hence there are at least $n-m$ rows and $n-m$ columns that do not have any broken queens in them. The $(n-m)^2$ cells in the intersections of these rows and columns need at least $2(n-m)-1$ broken queens to cover them. Therefore $m\ge 2(n-m)-1$ giving $m\ge (2n-1)/3$.
I have a hard time finding an example that requires exactly $m_n$ broken queens for an arbitrary $n$. But I think that $m_n$ is sharp. Btw if you know where this problem came from plz let me know. I believe it is a contest question. I was asked by a friend, but the friend doesnt know where the question came from. If the cells are labelled by $(i,j)$ where $i$ increases from $1$ to $n$ as we go east and $j$ increases from $1$ to $n$ as we go north, my guess is that we place $m_n$ broken queens at cells $(i,j)$ with $i+j=2,5,8,…, 3m_n-1$. I'm not sure if the locations can be random. If not, I don't see a pattern yet.
Best Answer
I just figured out. Put the $m_n$ broken queens on the cells $(i,j)$ where $i\le j\le i+1$ and $i+j=2, 5,8,...,3m_n-1$.