Một bảng kích thước \(2n \times 2n\) ô vuông, \(n\) là số nguyên dương. Người ta đánh dấu vào

Câu hỏi số 502735:

Vận dụng cao

Một bảng kích thước \(2n \times 2n\) ô vuông, \(n\) là số nguyên dương. Người ta đánh dấu vào \(3n\) ô bất kỳ của bảng. Chứng minh rằng có thể chọn ra \(n\) hàng và \(n\) cột của bảng sao cho các ô được đánh dấu đều nằm trên \(n\) hàng và \(n\) cột này.

Quảng cáo

Xem lời giải

Câu hỏi:502735

Phương pháp giải

Ta chọn ra \(n\) hàng có chứa số ô được đánh dấu nhiều hơn hoặc bằng \(n\) hàng còn lại. Sử dụng nguyên lý Dirichlet, ta sẽ 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 sẽ 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\)

Còn lại \(2n - n = n\) hàng ta không chọ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.

Tham Gia Group 2K10 Ôn Thi Vào Lớp 10 Miễn Phí

Câu hỏi trước Câu tiếp theo

>> Học trực tuyến lớp 9 & lộ trình Up 10! trên Tuyensinh247.com Đầy đủ khoá học các bộ sách (Kết nối tri thức với cuộc sống; Chân trời sáng tạo; Cánh diều), theo lộ trình 3: Nền Tảng, Luyện Thi, Luyện Đề. Bứt phá điểm lớp 9, thi vào lớp 10 kết quả cao. Hoàn trả học phí nếu học không hiệu quả.