Placing chess pieces so that n such pieces are always non-attacking

Question

I have a $12 \times 12$ chess board. I need to find:

1. the minimum number of rooks I can place on the chess board so that there always exist 7 rooks no two of which are attacking.
2. the minimum number of knights I can place so that there always exist 4 knights no two of which are attacking.

I have no idea what to do here. I do not wish for a complete answer; I just need some hint or resource I can use to understand the problem.

This problem is beyond my present curriculum and hence I can not find any help for the same.

Any help is appreciated.

Answer 1

Problem 1

Hint

The idea is to use the generalized pigeonhole principle; if you place $n$ pigeons into $k$ pigeonholes, then there will always exists a pigeonhole with $\lceil n/k\rceil$ pigeons. You need to partition the squares of the board into several "pigeonholes", such that whenever several rooks are in the same "pigeonhole," then the rooks will pairwise not attack each other. Assuming you found $k$ holes with this property, then you will conclude that whenever you place $6k+1$ rooks on the board, then some pigeonhole will contain $7$ rooks, meaning you have $7$ rooks where no two attack one another.

Since you want the minimum number of rooks, you want $k$ to be as small as possible. How can you partition the squares of the board into the fewest number of sets possible, where every set of squares has the property that no two squares in the set are in the same row or column?

Once you do this, you will then need to prove that your answer is optimal. That is, you know that any $6k+1$ rooks will have the desired property, so you then need to exhibit a placement of $6k$ rooks such that every subset of $7$ rooks contains an attacking pair.

Solution

Label each square of the chessboard with an ordered pair $(x,y)$, for $x,y\in \{1,\dots,12\}$. For each $d\in \{0,1,\dots,11\}$, define the $d^\text{th}$ broken diagonal to be the set of squares whose coordinates satisfy $x-y\equiv d\pmod 12$. Whenever you place $6\cdot 12 + 1=73$ rooks on the board, there must exist some broken diagonal with contains $7$ rooks, implying that these $7$ rooks are pairwise non-attacking.

This proves that $73$ rooks are sufficient. To prove that $72$ rooks are insufficient, you need find a way to place $72$ rooks on the board such that no seven of those rooks are pairwise non-attacking. To do this, fill any $6$ rows of the chessboard with rooks.

Problem 2

The same hint applies, but this time, $k$ will be much smaller. Think about finding a large set of squares, such that any two knights on that set will not attack each other. By the same logic as before, the answer will be $3k+1$, assuming you can find an arrangement of $3k$ knights where any four have an attacking pair.

Solution:

The mininum number of knights is $7$. For any placement of $7$ knights, there will be either four knights on black squares, or four knights on white squares. In either case, these four knights are non-attacking.

This is optimal, as illustrated by the following placement of six knights: a2, b4, c6, c1, d3, e5. You can partition these squares into three attacking pairs: {a2, c1}, {b4, d3}, and {c6, e5}. Therefore, any selection of four of these knights must contain an attacking pair.