Let us have a $2n+1\times 2n+1$ symmetric matrix $A$ where $n$ is a nonnegative integer. We write the numbers $1,2,...,2n+1$ in every row and column, in an arbitrary sequence.
Prove that in the main diagonal, every number from $1,2,...,2n+1$ can be found exactly once.
The task seems kind of "obvious" for me, I tried it for smaller $n$'s and because the matrix is symmetric, this has to be true.
Any idea how to do the solid proving? Thanks :)
On
Every number $1\leq i\leq 2n+1$ must appear $2n+1$ times in your matrix (Once in every row.)
Suppose that there is some number $i$ which never appears in the diagonal. Let $p$ be the number of times $i$ appears in the top half of our matrix, and $q$ the number of times $i$ appears in the lower half of our matrix. Since the matrix is symmetric, $p=q$. But since $i$ never appears on the diagonal, then $p+q=2n+1$, i.e $2n+1$ is even, which is a contradiction.
Therefore, every number from $1$ to $2n+1$ appears at least once on the main diagonal. Since there are $2n+1$ spots, then every number appears exactly once on the main diagonal .
Every $i\in\{1,2,\ldots,2n+1\}$ is in exactly $2n+1$ entries.
On the other hand, if there is an $i$ not appearing on the main diagonal, then it must appear in an even number of entries since the matrix is symmetric. This would contradict the first fact.