Problem

Source: Gillis Olympiad 5777 (Israel National '16-'17) #7

Tags: national olympiad, combinatorics, games



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.