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
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
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\).
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.
PH/HS 2K10 THAM GIA NHÓM ĐỂ CẬP NHẬT ĐIỂM THI, ĐIỂM CHUẨN MIỄN PHÍ!
>> Học trực tuyến lớp 9 và Lộ trình UP10 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. Lộ trình học tập 3 giai đoạn: Học nền tảng lớp 9, Ôn thi vào lớp 10, 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ả. PH/HS tham khảo chi tiết khoá học tại: Link
 |
 |
 |
 |
 |
 |
Hỗ trợ - Hướng dẫn
-
024.7300.7989
-
1800.6947
(Thời gian hỗ trợ từ 7h đến 22h)
Email: lienhe@tuyensinh247.com
