Prove that if 33 rooks are placed on a chessboard, at least five don't attack one another

Solution 1:

Look at the extended diagonals, which I’ve numbered from $1$ through $8$ in the diagram below:

$$\begin{array}{|c|c|c|c|c|c|c|c|} \hline 1&2&3&4&5&6&7&8\\ \hline 2&3&4&5&6&7&8&1\\ \hline 3&4&5&6&7&8&1&2\\ \hline 4&5&6&7&8&1&2&3\\ \hline 5&6&7&8&1&2&3&4\\ \hline 6&7&8&1&2&3&4&5\\ \hline 7&8&1&2&3&4&5&6\\ \hline 8&1&2&3&4&5&6&7\\ \hline \end{array}$$

There are eight of them, each comprising eight squares, so one of them must contain at least five of the rooks.

Solution 2:

I suppose the problem here is to prove the statement is true regardless of their arrangement.

Your points about the rules are correct, but I would first correct you that 32 pieces could be placed on a chessboard with only four on any given rank or file (by placing all pieces on the white squares or all the black squares), so by placing the 33rd piece, one row and one column must have "five or more", not "more than five".

To be pedantic, a piece that can capture another piece on its turn is not "attacking", it's "threatening". And there is one more rule of note, just to be painfully obvious: a rook cannot move "through" another piece to capture a piece beyond it. You seem to have overlooked this, because you seem to be hung up on keeping the rooks on diagonals.

That leads to one possible proof; because one row must have five or more rooks no matter how they're placed, and one column must have five or more rooks regardless of placement, then there are three rooks in the row of five and three rooks in that column of five that are separated by at least one other rook from each other. In the worst case, two of these rooks are the same (the 33rd rook) and so, given a grid of rooks placed on only the black squares, by placing the 33rd rook on any row or column, you identify three in a row and two additional rooks in a column that can't touch each other.

This actually seems an extremely low estimate, because if you place 32 rooks on all the black spaces, there is a diagonal of 8 that don't threaten each other. So, let's imagine the worst-case scenario:

Any given rook threatens a maximum of only four other pieces; those being the four positioned nearest him on the same row or column. Those same 4 rooks are the only ones that threaten the original rook. The other 28 rooks are either on a different row and column, or they are separated from the rook in question by one or more other rooks. So, literally speaking, any one rook would be "neutral" to (neither threatening nor being threatened by) at least 28 other pieces, and as many as 30 (for a piece in a corner), and each of those would be a pair of rooks that don't attack each other. Of those 28, each of them can only attack four others at most, and so the number of pairs of non-threatening rooks is at least the number of combinations of 29 things taken 2 at a time, which is way more than five (406 in fact).

So, given one starting rook, there are no more than 4 that can attack him and no fewer than 28 that cannot. Let's pick the worst-case from the remaining 28; a rook threatened by four completely different rooks than the ones threatening the first. There are four rooks that threaten this rook as I just said, so out of 33 rooks we have two that simply cannot attack each other because there's a rook on each side, and have eliminated 8 more as possibilities because they threaten one of these two rooks we've identified. There are 23 more rooks to pick from; let's continue our pattern and choose another rook threatened by four others, so we have three rooks that can't attack each other and 18 left. Two more repetitions of this and you have a group of five rooks that don't threaten each other (because they're each threatened by four unique rooks that are definitely not any other rook in the group), 20 more that threaten one and only one rook out of those five (and so can't be part of the group), and you still have 8 additional rooks that could neither threaten nor be threatened by any of the five we've already identified.

That's the worst-case; basically five groups of five rooks each in cross formations, with eight other rooks placed arbitrarily, and we're choosing the five rooks that are threatened by the most other rooks, and so eliminate the most possibilities for other members of this group. We have more than enough additional rooks to repeat this cross motif one more time (and there are a few permutations of placements that allow six of these cross formations to fit on an 8x8 board), so in fact we can identify 6 pieces out of 30, worst-case, that can't threaten each other because each of them is already threatened by four other unique rooks.

On top of that, the 31st piece, no matter where you place it, cannot threaten any of the six we have identified and vice-versa (although this piece is now threatened by at least one rook from the ones threatening the other 6), so in fact it is possible to identify a group of at least seven rooks of these 33, in any permutation of placements, that do not threaten any other rook in the group.

The 32nd piece can trivially threaten the 31st; however, the last one placed, the 33rd, cannot form any formation in which the 31st, 32nd and 33rd pieces all threaten each other; two of them will be mutually non-threatening, and as we've established, cannot threaten the 6 cross centerpieces, and so there are, at least, 8 rooks in any formation of 33 that cannot threaten any other rook in that group.