Iran 3rd round 2013

[asif e elahi]

What is the maximal number of rooks can be placed on a $n\times n$ so that every rook is threatened by at most $2k$ rooks where $k$ is a given positive integer ?

[Phlembac Adib Hasan]

Seriously, nobody loves combi? I am really surprised not seeing any other post in this thread even after two days. Anyway, here is a hint:

This is a typical double counting problem. Count the number of threats posed by the rooks altogether. Also don't forget Jensen.

[asif e elahi]

How to apply Jensen? Please explain. I think Cauchy Schwarz does the work.

[Nirjhor]

How to apply Jensen? Please explain. I think Cauchy Schwarz does the work.

Suppose there are $a_k$ rooks on $k$th row and $b_k$ rooks on $k$th column. Then a rook on row $i$ is threatened by $\left(a_i-1\right)$ rooks (all excluding itself). Similarly a rook on column $i$ is threatened by $\left(b_i-1\right)$ rooks. So there are in total $a_i(a_i-1)$ threats on row $i$ and $b_i(b_i-1)$ threats on column $i$. Let $R=\sum a_i=\sum b_i$ be the total number of rooks. Summing over all rows and columns gives \[\begin{eqnarray} T &=&\sum_{j=1}^n a_j\left(a_j-1\right)+\sum_{j=1}^n b_j\left(b_j-1\right) \\ &\ge & n\dfrac{\sum a_j}{n}\left(\dfrac{\sum a_j}{n}-1\right)+n\dfrac{\sum b_j}{n}\left(\dfrac{\sum b_j}{n}-1\right) \\ &=& 2R\left(\dfrac{R}{n}-1\right) \end{eqnarray}\] where we've used the fact that $f(x)=x^2-x$ is convex (Jensen). On the other hand, since there can be at most $2k$ threats to each rook, the maximum total number of threats on all rooks is simply $2kR$, thus giving us $T\le 2kR$. Combining these bounds \[2kR\ge T\ge 2R\left(\dfrac{R}{n}-1\right)~\Longrightarrow~ R\le n(k+1).\] The equality configuration is $k+1$ rooks on each row and column. The placing is easy, so left to the reader.

@Asif, did you get the same result applying Cauchy Schwarz? I didn't.

[asif e elahi]

I got the same result. Use this
$(a_{1}^2+\cdots+a_{n}^2)(1+\cdots+1)\geq (a_{1}+\cdots+a_{n})^2$