How many rooks can be placed in an $n\times n$ chessboard such that each rook is threatened by at most $2k$ rooks? (15 points) Proposed by Mostafa Einollah zadeh
Problem
Source: Iran 3rd round 2013- Combinatorics exam problem 2
Tags: modular arithmetic, combinatorics unsolved, combinatorics
20.09.2014 02:57
What is $k$?
25.09.2014 15:24
$k$ is a given natural number.
27.09.2014 06:47
02.10.2014 07:54
TAN768092100853 wrote:
I don't think this is correct. I'm not sure what theorem you wanted to use but this problem doesn't really required any high-powered results. It can be solved by using some ideas of double counting and convexity. It's quite a standard problem but instructive nonetheless. For each rook, let it's score be the number of rooks it's threatened by, and let the total sum of the scores of all the rooks be $s$. Let there be $r_i$ rooks in the $i$-th row and $c_i$ rooks in the $i$-th column. Let there be $x$ rooks in total. Then \[ 2n\frac{x}{n}(\frac{x}{n}-1) \leq \sum_{i=1}^{n} r_i(r_i-1) + \sum_{i=1}^{n} c_i(c_i-1) = s \leq 2kx, \] from which we obtain $x\leq n(k+1)$. Equality is obtained when there are exactly $k+1$ rooks in each row and column. We can achieve this by placing rooks in the $i, i+1, \cdots, i+k$-th squares of the $i$-th row for all $i$. (everything taken $\pmod{n}$ so the numbers $i, i+1, \cdots, i+k$ all lie between $1$ and $n$ inclusive)
02.10.2014 12:40
You're right. $k(n+1)$ is the answer. By the way,Fubini is just meaning "double counting".
06.07.2015 05:53
Would someone please explain the first inequality , and why does it hold ? Thanks in advance ! leminscate wrote: Then \[ 2n\frac{x}{n}(\frac{x}{n}-1) \leq \sum_{i=1}^{n} r_i(r_i-1) + \sum_{i=1}^{n} c_i(c_i-1) = s \leq 2kx, \]
07.07.2015 02:52
euh please ?
09.07.2015 20:38
It's an application of Jensen's inequality for the function $f(x)=x(x-1)$ and the numbers $c_1,...,c_n, r_1,...,r_n.$
26.03.2018 10:44
we can solve this problem with hall theorem. first convert the problem to bipartite graph format. one side columns and one side rows and connect rows and columns that has a rooks in their intersection. and know if 2 nodes are connected to each other the sum of degree of these two nodes is at most 2k+2. (1) know we prove that the maximum degree of all nodes is at most n(2k+2). consider the set of all nodes that their degree is more than k+1 in one side of this graph . from (1) and hall theorem we can find a matching to another side of graph and the same work for another side. and now we have only node with at most (k+1) degree and pair nodes with at most (2k+2) degree.