12
$\begingroup$

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.

$\endgroup$
8
  • 1
    $\begingroup$ Nice question. Where does it come from? $\endgroup$
    – saulspatz
    Mar 1, 2019 at 17:56
  • 2
    $\begingroup$ "pairwise different" that phrase doesn't make sense. $\endgroup$
    – Acccumulation
    Mar 1, 2019 at 23:48
  • 1
    $\begingroup$ @Acccumulation : It literally means, "for all pairs of numbers in the table, $(x,y)$, the members of the pair are different, $x \neq y$". I.e., each natural number appears zero or one times in the table. $\endgroup$
    – Eric Towers
    Mar 1, 2019 at 23:55
  • 1
    $\begingroup$ @Accumulation : The correct question to follow being told "... filled with different natural numbers ... " is "Different from what?" I'm fine with "distinct" in that usage. And there is no such thing as a unique natural number. $\endgroup$
    – Eric Towers
    Mar 2, 2019 at 0:11
  • 2
    $\begingroup$ @EricTowers "Pairwise different" is common mathematical language. Different can potentially be misinterpreted for "at least two of them are different one from the other". $\endgroup$
    – Daniel Robert-Nicoud
    Mar 2, 2019 at 11:05

2 Answers 2

Reset to default
16
$\begingroup$

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$

$\endgroup$
7
  • $\begingroup$ What, exactly, does it mean for a row or column to be "eligible" and how does this translate into a proof that $A\cap B\not=\emptyset$? $\endgroup$
    – Barry Cipra
    Mar 1, 2019 at 18:28
  • $\begingroup$ @BarryCipra excellent question ! A row is eligible if no previous number has been selected in that row and the same definition applies for column! Now we can notice that if an element is in an eligible row and column, then it is eligible. I hope this help. Best regards. $\endgroup$
    – Asinomás
    Mar 1, 2019 at 18:46
  • $\begingroup$ @BarryCipra let $k$ be an index such that both (a) no entry in row $k$ was picked by Ann in her first $i-1$ picks and (b) no entry in row $k$ was picked by Ben in his first $n-i$ picks. There indeed is such a $k$ because $n-i + (i-1) = n-1 < n$. Let $A_k$ denote the $i$-th row. We now show that of the $n$ entries in $A$ there is at least one not picked by Ann or Ben. But now let $l$ be an index such that both (a) no entry in column $l$ was picked by Ann in her first $i-1$ picks and (b) no entry in column $l$ was picked by Ben in his first $n-i$ picks. ... $\endgroup$
    – Mike
    Mar 1, 2019 at 18:52
  • $\begingroup$ ... Then the entry $a_{kl}$ [the entry in the $k$-th row of $A$ and $l$-th column] is available to be picked by both Ann for her $i$-th pick and Ben's $n-i+1$-th pick. So what Ann picks then will be no larger than $a_{kl}$ and what Ben picks no larger. $\endgroup$
    – Mike
    Mar 1, 2019 at 18:53
  • 1
    $\begingroup$ I like how this proof generalizes, pretty much word-for-word, to the $k$-dimensional version of the problem. (+1) $\endgroup$
    – Micah
    Mar 1, 2019 at 19:45
7
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Good point! It makes it interesting as it raises the question as to why the numbers must be distinct. I guess it is so that the choosing number algorithm is easier to explain. $\endgroup$
    – Asinomás
    Mar 1, 2019 at 19:19
  • 2
    $\begingroup$ @JorgeFernándezHidalgo - in fact it is clear from your very nice proof that even if the original matrix contains repeats, and even if a player can choose any of the multiple maxima (or minima), the claim is still true. $\endgroup$
    – antkam
    Mar 1, 2019 at 20:59

You must log in to answer this question.