Find the maximum numbers of rook to put in $6 \times 6$ board such that $2$ rooks don't attack each other?

Question

I have a question about probability but cannot find a good way to tackle it.

Here's the question:

Find the maximum numbers of rooks in the $6 \times 6$ board such that $2$ rooks don't attack each other?

My attempt: I can only think about guess and check method to solve this

First: We cannot put them adjacently or facing each other.

Second: I think the only way to put them in the board is diagonally, so the maximum rook To put is $6.$

Is my thought process correct or maybe somebody can provide a better way for me to tackle this problem? Thanks

Answer 1

You have only $6$ columns. So if you have more than $6$ rooks, at least two must be in the same column and therefore attacking each other.

So you can not have more than $6$. So $6$ is a theoretical absolute maximum. Now you have to prove that you can do $6$.

Which you can do if you put them diagonally

And you are DONE the maximum is $6$ because i) you can do $6$ and ii) you can't do more than $6$.

Nowhere in the question did you have to show that putting them diagonally is the only way.

Which it is not.

Not even remotely.

(Consider Rook 1 on $(a,2)$ and Rook 2 on $(b,1)$ and rooks $3$ to $6$ on $(c,3)$ to $(f,6)$).

In fact if you ever have Rook 1 on $(x, n)$ and Rook 2 on $(y, m)$ in a non-attacking way, you can switch to Rook 1 on $(x,m)$ and Rook 2 on $(y,n)$.

Are you sure that this was the actual question?

No offense but that seems way too easy, and it seems finding the total number of different ways to place the rooks (and not the number of rooks) is a much more interesting and relevant question.

There are $720$ ways to place $6$ rooks on a $6\times 6$ board where they aren't attacking each other. Can you figure out why?

Answer 2

You started off well; to finish off, perhaps just concretize your intuition into a well-formulated argument such as the following:

You've already shown 6 is possible, so if we can show 7 is impossible, the answer is 6.

Now suppose there are 7 rooks on the board. There are only 6 rows, so one row must contain at least 2 rooks (this is called the Pigeonhole Principle, but even if you haven't heard of the name, you should be able to think through why this must be the case). But if there are at least 2 rooks in the same row, they are attacking each other! So 7 rooks will never work.

Since 6 works, but 7 (or more) never does, 6 is the maximum.