USAMO 2000 — Ngày 1 và Ngày 2 Câu hỏi 4

Tìm số nguyên dương nhỏ nhất $n$ sao cho nếu tô màu $n$ ô của một bàn cờ $1000\times1000$ thì luôn có ba ô đã tô mà tâm của chúng tạo thành một tam giác vuông có hai cạnh góc vuông song song với các cạnh bàn cờ.