Iran 3rd round 2013
- asif e elahi
- Posts:185
- Joined:Mon Aug 05, 2013 12:36 pm
- Location:Sylhet,Bangladesh
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
- Posts:1016
- Joined:Tue Nov 22, 2011 7:49 pm
- Location:127.0.0.1
- Contact:
Re: Iran 3rd round 2013
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:
Welcome to BdMO Online Forum. Check out Forum Guides & Rules
- asif e elahi
- Posts:185
- Joined:Mon Aug 05, 2013 12:36 pm
- Location:Sylhet,Bangladesh
Re: Iran 3rd round 2013
How to apply Jensen? Please explain. I think Cauchy Schwarz does the work.
Re: Iran 3rd round 2013
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 e elahi wrote:How to apply Jensen? Please explain. I think Cauchy Schwarz does the work.
@Asif, did you get the same result applying Cauchy Schwarz? I didn't.
- What is the value of the contour integral around Western Europe?
- Zero.
- Why?
- Because all the poles are in Eastern Europe.
Revive the IMO marathon.
- Zero.
- Why?
- Because all the poles are in Eastern Europe.
Revive the IMO marathon.
- asif e elahi
- Posts:185
- Joined:Mon Aug 05, 2013 12:36 pm
- Location:Sylhet,Bangladesh
Re: Iran 3rd round 2013
I got the same result. Use this
$(a_{1}^2+\cdots+a_{n}^2)(1+\cdots+1)\geq (a_{1}+\cdots+a_{n})^2$
$(a_{1}^2+\cdots+a_{n}^2)(1+\cdots+1)\geq (a_{1}+\cdots+a_{n})^2$