Đầu tiên, cần chứng minh với mọi cách chọn 2000 ô bất kì luôn tồn tại một hình vuông 2x2 chứa đúng 1 ô trong 2000 ô vuông đó.
Thật vậy, vì số hàng lớn hơn số ô được chọn nên tồn tại 2 hàng A1, A2 liền nhau sao cho A1 chứa ít nhất 1 ô, A2 không chứa ô nào. Số cột cũng lớn hơn số ô được chọn nên tồn tại 2 ô X,Y cạnh nhau và A1 có đúng 1 ô. Gọi C,D là 2 ô trên A2 và cùng cột với X,Y. Hình vuông 2x2 gồm 4 ô C,D,X,Y chỉ có đúng 1 ô được chọn.
Giả sử ta có thể thu được 2000 ô màu đỏ. Khi đó theo trên luôn tồn tại 1 hình vuông 2x2 chứa đúng 1 ô đỏ.Vì lúc đầu hình vuông đó có 4 ô xanh nên mỗi lần đổi màu trong hàng hoặc cột thì số ô đỏ và xanh luôn chẵn, mâu thuẫn. Vậy ta không thể thu được 2000 ô màu đỏ.