Đánh giá năng lực Hà Nội
Đánh giá năng lực Hà Nội
Một bảng kích thước ô vuông, là số nguyên dương. Người ta đánh dấu vào
Một bảng kích thước ô vuông, là số nguyên dương. Người ta đánh dấu vào ô bất kỳ của bảng. Chứng minh rằng có thể chọn ra hàng và cột của bảng sao cho các ô được đánh dấu đều nằm trên hàng và cột này.
Quảng cáo
Ta chọn ra hàng có chứa số ô được đánh dấu nhiều hơn hoặc bằng 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 .
Chọn ra 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
Giả sử số ô được đánh dấu còn lại lớn hơn hoặc bằng
Còn lại hàng ta không chọn
Theo nguyên lý Dirichlet sẽ có ít nhất một hàng (trong hàng còn lại) chứa ít nhất hai ô đã đánh dấu.
Mà theo cách chọn thì 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 hàng đã chọn đều có ít nhất 2 ô được chọn, tức là trên hàng đã chọn không có ít hơn ô đã được đánh dấu .
Nếu vậy, số ô được đánh dấu lớn hơn hoặc bằng , trái giả thiết.
Vậy sau khi chọn hàng (với cách chọn như trên), sẽ còn lại không quá ô được đánh dấu. Vì thế có nhiều nhất là 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í
>> Học trực tuyến Lớp 9 & Lộ trình UP10 trên Tuyensinh247.com
>> Chi tiết khoá học xem: TẠI ĐÂY
Đầ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ả.
 |
 |
 |
 |
 |
 |
Hỗ trợ - Hướng dẫn
-
024.7300.7989
-
1800.6947
(Thời gian hỗ trợ từ 7h đến 22h)
Email: lienhe@tuyensinh247.com
