A table with $m$ rows and $n$ columns is given. In each cell of the table an integer is written. Heisuke and Oscar play the following game: at the beginning of each turn, Heisuke may choose to swap any two columns. Then he chooses some rows and writes down a new row at the bottom of the table, with each cell consisting the sum of the corresponding cells in the chosen rows. Oscar then deletes one row chosen by Heisuke (so that at the end of each turn there are exactly $m$ rows). Then the next turn begins and so on. Prove that Heisuke can assure that, after some finite amount of turns, no number in the table is smaller than the number to the number on his right. Example: If we begin with $(1,1,1),(6,5,4),(9,8,7)$, Heisuke may choose to swap the first and third column to get $(1,1,1),(4,5,6),(7,8,9)$. Then he chooses the first and second rows to obtain $(1,1,1),(4,5,6),(7,8,9),(5,6,7)$. Then Oscar has to delete either the first or the second row, let's say the second. We get $(1,1,1),(7,8,9),(5,6,7)$ and Heisuke wins.
Problem
Source: Gillis Olympiad 5777 (Israel National '16-'17) #7
Tags: national olympiad, combinatorics, games
23.08.2019 02:19
If $n = 1$, the problem is trivial. Let's now solve it for $n = 2.$ Instead of considering rows of two numbers, we'll simply consider the first number minus the second number in each row. In this way, we've reduced the problem to the following: Given $m$ integers, Heisuke can add any set of them, and afterwards Oscar can delete one number from the original set. Show that Heisuke can force all the numbers to be of the same sign (either all nonnegative or all nonpositive). Let's solve this problem. We'll prove this by induction on $m.$ If $m = 1$, the problem is immediate. Suppose that the problem holds for $m = k.$ When $m = k+1$, if there is a zero, we're done by the inductive hypothesis. Otherwise, suppose that every number is strictly larger than zero or strictly less than zero. We will say that a multiset $A$ of integers is tastier than a multiset $B$ if either the maximum absolute value of the integers in $A$ is strictly greater than that of $B$, or the they are equal and the number of integers in $A$ with this maximum absolute value is greater than the number of integers in $B$. For example, $(4, 4, -2, -3, -4)$ is tastier than both $(3, 1, 2, 3, 1)$ and $(-4, 2, 3, 1, 4, 1, 2).$ We will describe a procedure on the set of $m$ integers which either makes all numbers the same sign, or makes the set less tasty than it was before. Simply consider the number with the greatest absolute value, say $x$. Assume that $x$ is positive (the case where $x$ is negative can be dealt with similarly). Let $-r_1, -r_2, \cdots, -r_k$ be the negative integers, where $k \ge 1$ since otherwise we're done. Then, simply apply the operation on $(x, -r_1)$. If Oscar deletes the $x$ afterwards, the set has become less tasty. Otherwise, repeat with $(x, -r_2).$ Continue repeating in this manner if Oscar still refuses to delete $x.$ At some point, either Oscar must delete the $x$, in which case the set becomes less tasty, or all the numbers are either positive or of the form $x- r_i$ for $1 \le i \le k.$ By our assumption on $x$, all $x-r_i$'s are nonnegative, and so we're done at this point. The induction is complete. By the above paragraph, we've solved the case when $n = 2.$ Let's now solve the case where $n> 2.$ Observe that if at any point all numbers in the first column are less than or equal to the corresponding number in the second column, this property will remain true as long as Heisuke doesn't switch any numbers. Heisuke's strategy is as follows. Firstly, apply the $n = 2$ case on the first two columns, until each number in the first column is greater (or less) than or equal to the corresponding number in the second column. Then apply a column switch if necessary to make each number in the first column greater than or equal to the corresponding one in the second column. Now, do the $n=2$ case for the first and third columns. If each number in the third column is greater than the corresponding number in the first column, then do a column switch. In any case, we have now that the each number in the first column is greater than the corresponding ones in the second, third columns. Repeat with the fourth row, etc. In this way, we can ensure that the maximum element of each row is in the first column. Applying induction on the $m \times (n-1)$ subgrid which excludes the first column now finishes. $\square$