MathNet 2014 Câu hỏi 43

Các số $1,2,\ldots,10000$ được điền theo một thứ tự nào đó vào bàn ô vuông $100\times100$, mỗi ô một số. Pete đánh dấu các ô theo quy tắc sau. Ban đầu Pete tự chọn và đánh dấu $k$ ô. Trong mỗi bước tiếp theo, Pete được đánh dấu một ô chưa đánh dấu chứa số $a$ nếu (i) hàng của nó có một ô đã đánh dấu chứa số nhỏ hơn $a$, hoặc (ii) cột của nó có một ô đã đánh dấu chứa số lớn hơn $a$.

Tìm số $k$ nhỏ nhất sao cho với mọi cách sắp xếp các số, Pete đều có thể đánh dấu tất cả các ô. (S. Berlov)