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

Question

The question asks to prove that when 33 rooks are placed on an $8 \times 8$ chessboard that there are a total of 5 rooks that aren't attacking each other.

What I know:

1. 64 squares
2. Rooks attack in straight lines
3. at least 1 row must have more than 5 rooks
4. at least 1 column must have more than 5 rooks

I've set up an empty chessboard and randomly picked a row and place 5 and a column that contained five and found that no matter where you place them 1 X-shaped diagonal will have four rooks in it. So i counted all the holes that would have to have a rook placed in it to complete the diagonal of 5 and came up with 12. I just don't know how to use that.

I understand that concept that it works via diagonals and that 32 is the max number you can place on a chessboard with only having 4 in each diagonal. The minute you place the 33 one you make atleast one diaganol have 5 in it. Making it so that 5 aren't attacking each other.

But I don't know how to write that into the form of a proof. The proffesor said to use the pigeonhole principle, but I'm not sure what is the pigeon and what is the hole.

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

Answer 2

Here's a thought: if you take a row with five or more rooks in it (cal this row $r_1$), the first, third, and fifth rooks don't attack one another because there are other rooks in-between them. We know that such a row has to exist via the pigeonhole principle ($\lceil \frac{33}{8} \rceil = 5$).

So now all you need to do is find two rooks that don't attack any of these three. If any of the columns that these rooks are in have four or more additional rooks in them, we can apply the same argument to the column to get two more rooks that don't attack any of the others, and we're done.

So suppose that each of the columns containing one of the initial rooks has at most three other rooks in it. That means that of the 33 rooks we started with, there are 33 - 5 - 15 = 13 remaining rooks to place, and there are five columns where they could go. Pigeonholing again ($\lceil \frac{13}{5}\rceil = 4$) tells us that one of these columns must have at least three rooks in it, and the first and last rook in the column don't attack one another. So now we have our five rooks - the three from the row we started with, plus two in a column disjoint from any of the columns containing the initial rooks.

Hope this helps!

Answer 3

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.