Game theory problem about a 5x5 table with 25 entries and 2 players There is a 5x5 table with 25 cells, each of which has a different positive integer inside. Person A and B play a game.
They both receive a copy of the table.
Person A first picks the largest number that has not been crossed out, then crosses out the number, and all numbers in its row and column, then repeats this 5 times (until all numbers are crossed out).
Person B does the same, but with the smallest number available.
Can the table be filled in such a way that the sum of the 5 numbers person B picked is larger than the sum of the 5 numbers person A picked?
I tried to prove that the answer is no by changing the order, as in the last number person A picks is at least equal to the first number person B picks, the second last number person A picks is equal to the second number person B picks, and so on, but I don't know how to finish the proof.
 A: That's a helpful start. If the cells chosen by A in order are $A_1, \ldots, A_5$ and the cells chosen by B in order are $B_1, \ldots, B_5$, and the number in a cell $C$ is $N(C)$, it is in fact possible to show
$$N(A_{6-k}) \geq N(B_k)$$
for every $k$ in $1, \ldots, 5$.
We know that $B_k$ was chosen from the set of cells not in the same row or column as any of $B_1, \ldots, B_{k-1}$. $A_{6-k}$ was chosen from the set of cells not in the same row or column as any of $A_1, \ldots, A_{5-k}$. Consider these restrictions together, as though on a fresh copy of the board we cross out the rows and columns containing cells $B_1, \ldots, B_{k-1}$ AND the rows and columns containing cells $A_1, \ldots, A_{5-k}$. This is at most $(k-1)+(5-k)=4$ different rows and at most $4$ different columns, so at least one cell $C$ remains. That is, cell $C$ was not crossed out on A's board when $A_{6-k}$ was chosen, and was not crossed out on B's board when $B_k$ was chosen. Since A always chooses a cell with largest value and B always chooses a cell with smallest value,
$$ N(A_{6-k}) \geq N(C) \geq N(B_k) $$
Nothing about the number $5$ was really used here, so the same proof works for a more general game with any size square table.
