2

Rooks are place on a $n \times n$ chessboard satisfying the following condition: If the square $(i;j)$ is free, then at least $n$ rooks are on the $i$th row and $j$th column together. Show that there are at least $ n^2/2 $ rooks.

Among these $2n$ rows and columns I chose the one with the least number of rooks. Let that be a row. If $k$ is the number of rooks on this row and if $k$ is equal or bigger then $n/2$ then each row has $n/2$ rooks,and there will be at least $ n^2/2 $ rooks on the board. Now I'm having troubles proving it when $k$ is smaller then $n/2$.

epimorphic
  • 3,219
Sierra Res
  • 329
  • 1
    Hint: If $k<\frac{n}{2}$, how many columns can you find which don't have a rook where they intersect that specific row? What could you say about the number of rooks on each of these columns? The rest of the columns would require a coarser approach. – Jonathan Y. Jan 07 '16 at 18:04
  • @JonathanY. Interestingly, the estimate you hint at does not require $k<\frac n2$ to work. – Hagen von Eitzen Jan 07 '16 at 18:11
  • @HagenvonEitzen no it doesn't. OP's work for $k\geq \frac{n}{2}$ is still interesting, though. – Jonathan Y. Jan 07 '16 at 18:13

1 Answers1

1

If we have a row with $k\lt n/2$ rooks, then each column not represented must have a corresponding $(n-k)$ rooks. There are $(n-k)$ such columns, and the best we can hope for is at least $(n-k)^2+k^2$ rooks.

$(n-k)^2+k^2$ is minimized when $k=n/2$.

JMP
  • 21,771