Nhóm thuvientoan.net xin gửi đến các bạn đọc tài liệu Các bài toán về Tổ hợp và Suy luận ôn thi vào chuyên Toán.
Tài liệu gồm 101 trang tuyển chọn lý thuyết và bài tập về chủ đề này. Nội dung cụ thể bao gồm:
I. Nguyên lí Dirichlet.
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.
II. 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.
+ ‚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.
III. Một số ví dụ minh họa.
Ví dụ 1. 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.
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.
Ví dụ 4. Cho bảng vuông gồm n.n ô vuông. 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.
Ví dụ 5. Ở 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.
Ví dụ 7. Trong một cuộc tranh giải vô địch quốc gia về bóng đá có 20 đội tham gia. Số nhỏ nhất các trận đấu là bao nhiêu để trong 3 đội bất kỳ luôn tìm được 2 đội đã chơi với nhau.
....
Nhóm thuvientoan.net hy vọng với tài liệu Các bài toán về tổ hợp và suy luận sẽ giúp ích được cho các bạn đọc và được đồng hành cùng các bạn, cảm ơn!
.png)
Tài liệu
Like fanpage của thuvientoan.net để cập nhật những tài liệu mới nhất: https://bit.ly/3g8i4Dt.
THEO THUVIENTOAN.NET
