Contest math problem about crossing out numbers in the table

Question

A table $n\times n$ is filled with pairwise different natural numbers. Ann and Ben are playing the following game: Ann chooses the greatest number, then crosses out the row and the column containing it. She then chooses the greatest number from what is remained and repeats the whole process unless table is crossed out completely.

Ben takes exactly the same table, and repeats the same process, but choosing the least number on each step.

We need to show that the sum $A$ of numbers chosen by Ann is greater (or equal) to the sum $B$ of numbers chosen by Ben.

I think it should be done via presenting such $C$ that $A\geq C\geq B$. However, if $a_i$ and $b_i$ are the numbers chosen by Ann and Ben on $i$-th step respectively, the inequality $a_i\geq b_{n-i+1}$ does not hold. So, I am stuck at this point.

Answer 1

Let $a_1,a_2\dots a_n$ be the numbers selected by Ann and $b_1,b_2,\dots b_n$ be the numbers selected by Benjamin.

Lemma: $a_i\geq b_{n+1-i}$ for all $1\leq i \leq n$.

Proof: Consider the set $A$ of all numbers that were eligible when we selected $a_i$ and the set $B$ of all the numbers eligible when we selected $b_{n+1-i}$. Notice that these two sets intersect (because $n-i+1$ rows are eligible in $A$ and $i$ rows are eligible in $B$, and the same happens with the columns) so the claim is true, since $a_i=\max(A)$ and $b_i=\min B$.

The problem follows from the lemma:

$\sum\limits_{i=1}^n a_i \geq \sum\limits_{i=1}^n b_{n+1-i} = \sum\limits_{i=1}^n b_i$

Answer 2

And in fact to add to @Jorge's answer strict inequality is not always possible: For any integer $n$ there are $n \times n$ tables $A$ that will force Player A and Player B to have the same sum: Let $A$ be any $n \times n$ table where the entries get larger as you head down a column, and to the right on a row: e.g., $A =[a_{ij}]$ where the $ij$-th entry is $i(n+1) + j$. [Note that all entries of $A$ are distinct.] Then both Player A and Player B will end up picking the diagonal elements of $A$: Player A will end up picking the diagonals southeast to northwest when Player B northwest to southeast.