com Nguyễn Công Lợi CHUYÊN ĐỀ CÁC BÀI TOÁN VỀ TỔ HỢP VÀ SUY LUẬN Nghệ An, tháng 9 năm 2019 1 Website:tailieumontoan.com CHUYÊN ĐỀ TỔ HỢP VÀ SUY LUẬN LỜI NÓI ĐẦU Nhằm đáp ứng nhu cầu về của giáo viên toán THCS và học sinh về các chuyên đề toán THCS, website tailieumontoan.com giới thiệu đến thầy cô và các em chuyên đề về các bài toán tổ hợp và suy luận. Chúng tôi đã kham khảo qua nhiều tài liệu để viết chuyên đề này nhằm đáp ứng nhu cầu về tài liệu hay và cập nhật được các dạng toán mới về toán tổ hợp và suy luận thường được ra trong các kì thi gần đây. Chuyên đề này gôm các chủ đề toán sau: - Chủ đề 1: Các dạng toán về nguyên lý Dirichlet - Chủ đề 2: Các bài toán về ứng dụng nguyên lý cực hạn - Chủ đề 3: Các bài toán về đại lượng bất biến và ứng dụng - Chủ đề 4: Một số bài toán tổ hợp suy luận tổng hợp Các vị phụ huynh và các thầy cô dạy toán có thể dùng có thể dùng chuyên đề toán tổ hợp và suy luận để giúp con em mình học tập. Hy vọng chuyên đề này sẽ có thể giúp ích nhiều cho học sinh phát huy nội lực giải toán nói riêng và học toán nói chung.
Mặc dù đã có sự đầu tư lớn về thời gian, trí tuệ song không thể tránh khỏi những hạn chế, sai sót. Mong được sự góp ý của các thầy, cô giáo và các em học! Chúc các thầy, cô giáo và các em học sinh thu được kết quả cao nhất từ chuyên đề này! Tác giả: Nguyễn Công Lợi TÀI LIỆU TOÁN HỌC 2 Website:tailieumontoan.com MỘT SỐ BÀI TOÁN TỔ HỢP Chủ đề 1 CÁC BÀI TOÁN ỨNG DỤNG NGUYÊN LÝ DIRICHLET I. Nguyên lí Dirichlet - còn gọi là nguyên lí chim bồ câu (The Pigeonhole Principle) hoặc nguyên lý những cái lồng nhốt thỏ hoặc nguyên lí sắp xếp đồ vật v|o ngăn kéo (The Drawer Principle) - đưa ra một nguyên tắc về phân chia phần tử các lớp. Nguyên lý Dirichlet cơ bản: Nếu nhốt n 1 con thỏ vào n cái chuồng thì bao giờ cũng có một chuồng chứa ít nhất hai con thỏ.
Nguyên lý Dirichlet tổng quát: Nếu có N đồ vật được đặt vào trong k hộp thì sẽ tồn tại một hộp N chứa ít nhất đồ vật. (Ở đ}y x là số nguyên nhỏ nhất có giá trị nhỏ hơn hoặc bằng x) k Nguyên lí Dirichlet mở rộng: Nếu nhốt n con thỏ vào m 2 cái chuồng thì tồn tại một n m 1 chuồng có ít nhất con thỏ. m Nguyên lí Dirichlet dạng tập hợp: Cho A và B là hai tập hợp khác rỗng có số phần tử hữu hạn, mà số lượng phần tử của A lớn hơn số lượng phần tử của B. Nếu với một quy tắc n|o đó, mỗi phần tử của A cho tương ứng với một phần tử của B, thì tồn tại ít nhất hai phần tử khác nhau của A m| chúng tương ứng với một phần tử của B.
Phương pháp ứng dụng. Nguyên lí Dirichlet tưởng chừng như đơn giản như vậy, nhưng nó l| một công cụ hết sức có hiệu quả dùng để chứng mình nhiều kết quả hết sức sâu sắc của toán học. Nguyên lí Dirichlet cũng được áp dụng cho các bài toán của hình học, điều đó được thể hiện qua hệ thống bài tập sau: Để sử dụng nguyên lý Dirichlet ta phải làm xuất hiện tình huống nhốt ‚thỏ‛ v|o ‚chuồng‛ v| thoả mãn c{c điều kiện: + Số ‘thỏ‛ phải nhiều hơn số chuồng. Tác giả: Nguyễn Công Lợi TÀI LIỆU TOÁN HỌC 3 Website:tailieumontoan.com + ‚Thỏ‛ phải được nhốt hết vào các ‚chuồng‛, nhưng không bắt buộc chuồng nào cũng phải có thỏ.
Thường thì phương ph{p Dirichlet được áp dụng kèm theo phương ph{p phản chứng. Ngoài ra nó còn có thể áp dụng với các nguyên lý khác. Một số ví dụ minh họa. Cho bảng ô vuông kích thước 10.10 gồm 100 ô vuông đơn vị.
Điền v|o mỗi ô vuông của bảng n|y một số nguyên dương không vượt qu{ 10 sao cho hai số ở hai ô vuông chung cạnh hoặc chung đỉnh nguyên tố cùng nhau. Chứng minh rằng trong bảng ô vuông đã cho có một số xuất hiện ít nhất 17 lần. Lời giải Xét hình vuông cạnh 2x2 , do hình vuông n|y có mỗi hình vuông nhỏ luôn chung cạnh hoặc chung đỉnh nên tồn tại nhiều nhất 1 số chẵn, nhiều nhất 1 số chia hết cho 3 do đó có ít nhất 2 số lẻ không chia hết cho 3. Bảng 10x10 được chia th|nh 25 hình vuông có cạnh 2x2 nên có ít nhất 50 số lẻ không chia hết cho 3.
Từ 1 đến 0 có 3 số lẻ không chia hết cho 3 là 1, 5, 7. Áp dụng nguyên lí Dirichlet ta được một trong ba số trên xuất hiện ít 50 nhất 1 17 lần 3 Ví dụ 2. Giả sử 1 bàn cờ hình chữ nhật có 3x7 ô vuông được sơn đen hoặc trắng. Chứng minh rằng với c{ch sơn m|u bất kì thì trong bàn cờ luôn tồn tại hình chữ nhật gồm các ô ở 4 góc là các ô cùng màu.
Lời giải Mẫu sơn m|u có thể xảy ra với bàn cờ này có dạng từ 1 đến 8. Giả sử một trong số các cột thuộc dạng 1. Bài toán sẽ được chứng minh nếu tất cả các cột còn lại thuộc dạng 1, 2, 3 hoặc 4. Giả sử tất cả các cột còn lại thuộc dạng 5, 6, 7, 8 khi đó theo nguyên lí Dirichlet thì hai trong số sau cột có 2 cột cùng 1 dạng v| như vậy b|i to{n cũng được chứng minh Chứng minh ho|n to|n tương tự nếu 1 cột có dang 8.
Giả sử không có cột nào trong các cột 1, 8 thì theo nguyên lí Dirichlet cũng có 2 cột cùng dạng v| b|i to{n cũng đựoc chứng minh Tác giả: Nguyễn Công Lợi TÀI LIỆU TOÁN HỌC 4 Website:tailieumontoan. Trong hình chữ nhật kích thước 1.2 ta lấy 6n 2 1 điểm với n là số nguyên dương. Chứng 1 minh rằng tồn tại 1 hình tròn có bán kính chứa không ít hơn 4 trong số c{c điểm đã cho. n Lời giải Chia các cạnh của hình chữ nhật th|nh n đoạn v| 2n đoạn bằng nhau ,mỗi đoạn có độ dài 1.
Nối c{c điểm chia bằng c{c đường thẳng song songvới các cạnh của hình chữ nhật ta được n 1 n.2n 2n 2 hình vuông nhỏ với cạnh là. Nếu mỗi hình vuông chứa không qu{ 3 điểm thì tổng n số điểm đã cho không qu{ 3. Do đó phải tồn tại 1 hình vuông chứa 1 2 không ít hơn 4 điểm. Rõ ràng hình vuông cạnh nội tiếp đường tròn bán kính là v| đường n 2n 1 tròn n|y được chứa trong đường tròn đồng tâm bán kính.
Cho bảng vuông gồm n. Mỗi ô vuông ghi một trong các số 1; 0; 2. Chứng minh rằng không tìm được bảng vuông nào mà tổng các số trên cột, trên h|ng, trên đường chéo là các số khác nhau. Lời giải Do trong các ô có thể nhận một trong ba số 0; 1; 2 nên có thể có trường hợp tất cả các ô của một hàng hoặc một cột hoặc một đường chéo nhận giá trị 0 hoặc nhận giá trị 2.
Do đó tổng các số trên cột hoặc trên hàng hoặc trên đường chéo có giá trị nhỏ nhất là 0.n 0 và giá trị lớn nhất là 2. Như vậy các tổng các số trên mỗi hàng, mỗi cột, mỗi đường chéo có thể nhận 2n 1 giá trị là 0;1; 2;.; 2n Do bảng ô vuông n.n nên sẽ có n hàng, n cột v| hai đường chéo. Do đó sẽ có 2n 2 tổng nhận một trong 2n 1 giá trị số nguyên từ 0 đến 2n. Theo nguyên tắc Dirichlet phải có ít nhất 2 tổng có giá trị bằng nhau.
Điều n|y có nghĩa l| không tìm được bảng vuông nào mà tổng các số trên cột, trên h|ng, trên đường chéo là các số khác nhau. Ở vòng chung kết cờ vua có 8 bạn tham gia. Hai bạn bất kỳ đều phải đấu với nhau một trận v| người n|o cũng phải gặp đủ 7 đấu thủ của mình. Chứng minh rằng trong mọi thời điểm của cuộc đấu, bao giờ cũng có hai đấu thủ đã đấu một số trận như nhau.
Tác giả: Nguyễn Công Lợi TÀI LIỆU TOÁN HỌC 5 Website:tailieumontoan.com Lời giải Giả sử số trận thi đấu của các bạn tham gia thi đấu cờ vua là a1 ; a 2 ;. Do hai bạn thi đấu với nhau một trận nên ta có 0 a i 7, 1 i 8. Xét c{c trường hợp sau: Tính đến thời điểm đó có một bạn chưa đấu trận nào suy ra không có bạn n|o đấu đủ 7 trận. Khi đó 0 a i 6, 1 i 8 do đó tồn tại a k a m có nghĩa l| có hai đấu thủ đã đấu một số trận như nhau.
Tính đến thời điểm đang xét, mỗi bạn đều đã đấu ít nhất một ván. Khi đó ta có 0 a i 7, 1 i 8 , do đó tồn tại a k a m có nghĩa l| có hai đấu thủ đã đấu một số trận như nhau. Vậy b|i to{n được chứng minh. Cho 40 số nguyên dương a1 ,a 2 ,., b21 thoả mãn hai điều kiện: 1 a1 a 2 .
b21 200 Chứng minh rằng tồn tại bốn số a i ;a j ;bk ;bp với 1 i, j 19;1 k,p 21 thỏa mãn a i a j ; bk bp a j a i bp bk Lời giải Xét các tổng có dạng a m bn với a m a1 ; a 2 ;. Do tập hợp a1 ;a 2 ;.;a 19 có 19 phần tử và tập hợp b1 ; b2 ;.; b 21 có 21 phần tử nên, nên ta có tất cả 19.21 399 tổng dạng a m bn như thế. Nên các tổng a m bn nhận các giá trị nguyên dương từ 2 đến 400. Đến đ}y ta xét c{c trường hợp sau: Nếu các tổng trên nhận đủ 399 giá trị từ 2 đến 400.
Khi đó từ giả thiết cảu b|i to{n ta được Tác giả: Nguyễn Công Lợi TÀI LIỆU TOÁN HỌC 6 Website:tailieumontoan.com a1 b1 2 a b1 1 1 a19 b21 400 a19 b21 200 a a19 ; b1 b21 Từ đó ta suy ra được 1 a19 a1 b21 b1 199 Nếu các tổng trên không nhận đủ 399 giá trị từ 2 đến 400.