Combinatorics problem from All-Russian Olympiad

[hearty lotus]

Can I please have a hint for this problem? Here is what I got so far: ||I am suspecting that k=1. Define a cell to be “connected” if it is possible to paint this cell without using a move. Call a cell “disconnected” if otherwise. Notice that there can only be a maximum of 1 “disconnected” cells (since it needs to be the largest of a column and the smallest of a row). Indeed, suppose that there are two cells x,y that are both the largest of their columns and smallest of their rows. Without loss of generality, let x>y. Notice that x,y needs to be in distinct rows and columns, however, x<the cell in the same column as y. Which contradicts the assumption that y is the largest of its columns. ||
||I need to show that in the absence of a “disconnected” cell, painting a number will be sufficient and that when there is a “disconnected” cell, painting the disconnected cell will be sufficient||

[hearty lotus]

Combinatorics problem from All-Russian Olympiad

[tough jungle]

Yeah i think you are along the right track, for the disconnected cell, paint it, then you can paint everything else in the same row and column.

If there are no disconnected cells, you can consider alternatingly

• go to smallest in row
• go to biggest in column
  and eventually you must loop.

Maybe consider this graph

[hearty lotus]

Would this work? || Now, if we have a "disconnected" cell, then we paint it. So now we are left with a board without "disconnected" cells. Suppose that after Petya has painted all of the cells that he could paint, there still remains cells that are unpainted. Consider cell $x$ in row $i$ and column $j$, it is left unpainted because the smallest cell in row $i$ is left unpainted and cell $x$ is larger than all of the painted cells in column $j$. In this column $j$, there must be a biggest cell in row $k$ ($k$ can be equal to $i$). Now consider row $k$, it has an unpainted cell, which means that the smallest cell in row $k$ is left unpainted, which means that it must be the largest cell in its column. This is a contradiction. ||

[fossil saffron]

One more