Ta chọn ra \(n\) hàng có chứa số ô được đánh dấu nhiều hơn hoặc bằng \(n\) hàng còn lại. Sử dụng nguyên lý Dirichlet, ta sẽ chứng minh số ô được đánh dấu còn lại nhỏ hơn hoặc bằng \(n\).Giải chi tiết:Chọn ra \(n\) hàng có chứa số ô được đánh dấu nhiều nhất trên các hàng đó Ta sẽ chứng minh số ô được đánh dấu còn lại nhỏ hơn hoặc bằng \(n\)Giả sử số ô được đánh dấu còn lại lớn hơn hoặc bằng \(n + 1\)Còn lại \(2n - n = n\) hàng ta không chọn Theo nguyên lý Dirichlet sẽ có ít nhất một hàng (trong \(n\) hàng còn lại) chứa ít nhất hai ô đã đánh dấu.Mà theo cách chọn thì \(n\) hàng đã chọn có chứa số ô được đánh dấu nhiều nhất trên các hàng đó. Có một hàng còn lại chưa chọn có ít nhất 2 ô đánh dấu, nên suy ra mọi hàng trong \(n\) hàng đã chọn đều có ít nhất 2 ô đượ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 + \left( {n + 1} \right) > 3n\), trái giả thiết.Vậy sau khi chọn \(n\) hàng (với cách chọn như trên), sẽ còn lại không quá \(n\) ô được đánh dấu. Vì thế có nhiều nhất là \(n\) cột chứa chúng. Do đó, sẽ không còn ô đánh dấu nào nằm ngoài các hàng hay cột được chọn.Suy ra điều phải chứng minh.
