Bài 29: Cho một bảng kích thước $2n \times 2n$ ô vuông. Người ta đánh dấu vào 3n ô bất kì của bảng. CMR có thể chọn ra n hàng và n cột sao cho các ô được đánh dấu đầu nằm trên các hàng, các cột này
Ta chọn ra n hàng chứa số ô được đánh dấu nhiều nhất. Ta sẽ chứng minh trong n hàng còn lại, số ô được đánh dấu không quá n
Giả sử ngược lại, tức là ở n hàng còn lại, có nhiều hơn n ô được đánh dấu.$\Rightarrow \exists$ có ít nhất 1 hàng trong n hàng không được chọn ra này có chứa nhiều hơn 2 ô được đánh dấu.$(1)$
Mặt khác, vì tổng số ô được đánh dấu trong các hàng được chọn ra $>n$ nên tổng số ô được đánh dấu $<2n$
$$\Rightarrow \exists$ 1 hàng trong các hàng được chọn ra chứa ít hơn 2 ô được đánh dấu. (2)
Từ $(1)(2)$ suy ra mâu thuẫn.
$\Rightarrow $ số ô được đánh dấu trong n hàng còn lại không vượt quá n ô.Nên, ta có thể chọn ra n cột chưa n ô này.
n cột và n hàng được chọn ra là cái ta cần tìm.
P/s: Bài 30 phức tạp kinh
Bài viết đã được chỉnh sửa nội dung bởi MoMo123: 27-05-2018 - 23:32