23rd Junior Turkish Mathematical Olympiad

Answer: $\lfloor 3n/2\rfloor$.

Each column contains at most two rooks, otherwise the uppermost and lowermost rooks on this column do not satisfy the conditions. Let us consider two columns each containing two rooks. Let $a_1,a_2$ and $b_1,b_2$ be rooks on the first and second columns, respectively ($a_1$ is above $a_2$ and $b_1$ is above $b_2$). Let us show that any two of these rooks cannot be on the same line. On the contrary, assume that $a_1$ and $b_1$ are on the same line. Without loss of generality assume that the line containing $a_2$ is not above the line containing $b_2$. Then the squares $a_2$ and $b_1$ do not satisfy the conditions. Now assume that $a_1$ and $b_2$ are on the same line. Then $a_2$ and $b_1$ do not satisfy the conditions. The cases when $a_2$ and $b_2$ are on the same line or $a_2$ and $b_1$ are on the same line are completely similar. The proof is completed. (Similar arguments show that there are only two possibilities: either both lines containing $b_1$ and $b_2$ are between the lines containing $a_1$ and $a_2$, or vice versa, but this fact is not used in the proof.)

Now by pigeonhole principle the total number of columns containing two rooks is at most $\lfloor n/2\rfloor$. Therefore, even if each remaining column contains one rook, the total number of rooks on the board will be at most $2\lfloor n/2\rfloor +n-\lfloor n/2\rfloor =\lfloor 3n/2\rfloor$.

Now we give an example for $\lfloor 3n/2\rfloor$ rooks satisfying the conditions. Let us numerate lines by $1,2,...,n$ starting from the lowest line and numerate columns by $1,2,...,n$ starting from the leftmost column. Let the square on the intersection of column $i$ and line $j$ be $(i,j)$. For each $1\le i\le n$, let us place a rook to the square $(i,n+1-i)$ ($n$ rooks in total) and for each $1\le i\le \lfloor n/2\rfloor$ let us place a rook to the square $(i,i)$ ($\lfloor n/2\rfloor$ rooks in total). The obtained configuration satisfies the conditions.