Chọn ra n hàng có chứa ô được đánh dấu nhiều trên hàng đó nhất. Ta chứng
minh rằng số ô được đánh dấu còn lại nhỏ hơn hoặc bằng n. Giả sử trái lại không
phải như vậy, tức là số ô được đánh dấu còn lại lớn hơn hoặc bằng n + 1. Số các
hàng còn lại chưa chọn là n. Vậy theo nguyên lí Dirichlet sẽ có ít nhất một hàng
(trong số n hàng còn lại) chứa ít nhất hai ô đánh dấu.
Chú ý rằng theo cách chọn thì n hàng đã chọn chứa số ô được đánh dấu nhiều
trên hàng đó nhất. Có một hàng còn lại chưa chọn có ít nhất hai ô đánh dấu, nên
suy ra mọi hàng trong số n hàng đã chọn đều có ít nhất hai ô được chọn, tức là
trên n hàng đã chọn không có ít hơn 2n ô đã được đánh dấu. Nếu vậy, số ô được
đánh dấu lớn hơn hoặc bằng $2n + (n + 1) > 3n$.
Đó là điều vô lí (vì chỉ có 3n ô được đánh dấu). Vậy nhận xét được chứng minh.
Như vậy, sau khi đã chọn ra n hàng (với cách chọn như trên), theo nhận xét
còn lại không quá n ô được đánh dấu. Vì thế có cùng lắm là có n cột chứa chúng.
Vì lẽ đó sẽ không thấy ô đánh dấu nào nằm ngoài các hàng hay cột đã chọn.
*Hình minh họa ở dưới
