MathNet 2014 Câu hỏi 11

Các số $1,2,\dots,n^2$ được điền theo một thứ tự nào đó vào các ô của bàn cờ $n\times n$, mỗi ô một số. Pete thực hiện các lượt theo quy tắc sau. Trong lượt đầu, cậu đặt một quân vào một ô. Ở mỗi lượt sau, cậu có thể đặt một quân mới vào một ô tùy ý hoặc chuyển một quân theo phương ngang hay dọc từ ô mang số $a$ tới một ô bất kỳ mang số lớn hơn $a$. Mỗi khi một quân được đặt vào ô, ô ấy được đánh dấu; cấm đặt quân vào ô đã đánh dấu.

Tìm số nhỏ nhất $k$ sao cho với mọi cách sắp xếp các số, Pete có thể đánh dấu tất cả các ô bằng không quá $k$ quân.