What is $k$?

$k$ is a given natural number.

Click to reveal hidden text

TAN768092100853 wrote:

Click to reveal hidden text

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)

You're right. $k(n+1)$ is the answer. By the way,Fubini is just meaning "double counting".

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, \]

euh please ?

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.$

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.