Question 86
The cells of a $100\times100$ square table are numbered in some order from $1$ to $10000$. Petya colors cells by the following rules. Initially he colors any $k$ cells of his choice. On each later turn he may color one uncolored cell numbered $a$ if at least one condition holds: an already colored cell with a smaller number is in its row, or an already colored cell with a larger number is in its column. What is the least $k$ such that, regardless of the initial numbering, Petya can eventually color every cell?