Matrix with max sum on all diagonals I knew this problem a long time ago but could not recall the solution. I know the solution is interesting though. Anybody want to help? Thanks.
There is a $n \times n$ matrix. A collection of $n$ entries of the matrix is called good if no two of them have a same row or column. For each good collection we consider the sum of its elements, and let $M$ be the maximum among all these sums. Now any entry of the matrix belongs to at least one good collection with sum $M$. Prove that every good collection has sum $M$.
 A: Let $\circ$ denote the Hadamard product, $A\circ B=(a _{ij} b _{ij}) _{1\le i,j\le n}$, and let $f(A)$ denote the sum of the entries of $A$. Each good set corresponds to a permutation in $S _n$. Let our matrix be $C$, then we are given that there are $k$ permutation matrices $P _{\sigma_i}$, $\sigma _i\in S _n$, such that $f(P _{\sigma _i}\circ C)=M$, and $\sum P _{\sigma _i}$ has all entries $\geq 1$. 
Let $\pi\in S_n$ be so that, $M _{0}=f(P _{\pi}\circ C) < M$, then we look at $\sum P _{\sigma _i}-P _{\pi}$, it has nonnegative entries and equal sums of rows and columns. Such a matrix can be written as a sum $\sum P _{\tau _i}$, $\tau _i\in S_n$, this is a simple exercise in combinatorics (maybe you have heard it in the form, every bipartite regular multigraph can be written as a union of perfect matchings). So we have 
$$kM-M _{0}=f\left((\sum P _{\sigma _i}-P _{\pi})\circ C\right)=f\left((\sum P _{\tau _i})\circ C\right)=\sum f(P _{\tau _i}\circ C)\le (k-1)M$$
which gives us a contradiction. So $f(P _{\pi}\circ C)=M$, but $\pi$ was arbitrary, so we are done.
