CHUYÊN ĐỀ: Một số vấn đề của tóan tổ hợp rời rạc và ứng dụng
$\xi 1$ NGUYÊN LÝ DIRICHLET
Nguyên lý Dirichlet hay còn gọi là nguyên lý "chuồng và thỏ".Đây là nguyên lý thóat nhìn có vẻ đơn giản và hiển nhiên nhưng ứng dụng rất hiệu quả và to lớn trong chứng minh tóan học,đặc biệt là trong việc chứng minh về sự tồn tại của một đối tượng thỏa mãn tính chất nào đó
nguyên lý Dirichlet được phát biểu như sau:
Nếu nhốt $m.n+r$ ( $m,n,r$ là các số nguyên dương ) con thỏ vào $n$ cái chuồng thì phải có ít nhất một chuồng chứa không ít hơn $m+1$ con thỏ
Nhìn thóang qua thì có vẻ đơn giản và dễ hiểu nhưng áp dụng thì không hề dễ dàng.Phải biết linh hoạt trong việc chọn chuồng và thỏ mới thấy được tính "Dirichlet" trong đó
Một số dạng áp dụng của nguyên lý Dirichlet:
-Phân chia tập hợp để tạo thành n-chuồng ( nội dung của phương pháp là chia đối tượng lớn thành nhiều đối tượng nhỏ )
-Xây dựng các n-chuồng theo đối tượng xuất phát ( nội dung của phương pháp là từ một đối tượng xuất phát mà mình đã chọn,ta lập luận để xây dựng các đối tượng tiếp theo )
-Xây dựng các dãy số ( nội dung của phương pháp là tạo ra các dãy số từ bài tóan. Sau đó áp dụng nguyên lý Dirichlet cho các số hạng của dãy số được chọn )
-Xây dựng bảng ( nội dung của phương pháp là lập các bảng, Sau đó áp dụng nguyên lý Dirichlet cho các hàng ( hoặc cột ) để suy ra tính chất cần thiết )
BÀI TẬP ÁP DỤNG:
1. Chứng minh rằng từ 5 số nguyên bất kỳ,luôn tìm được 3 số có tổng chia hết cho 3
2. Trong hình tròn $(C)$ có diện tích bằng 8 đặt 17 điểm phân biệt bất kì. Chứng minh rằng bao giờ cũng tìm được ít nhất 3 điểm tạo thành 1 tam giác có diện tích bé hơn 1
3. Trên mặt phẳng cho 5 điểm A,B,C,D,E có các tọa độ là các sô nguyên. Chứng minh rằng trong số các tam giác được tạo thành từ 5 điểm đó có ít nhất 3 tam giác có diện tích nguyên
4. Chứng minh rằng từ 52 số tự nhiên bất kì luôn chọn được 2 số sao cho tổng,hoặc hiệu của 2 số đó chia hết cho 100. Kết luận còn đúng không đối với 51 số?
5. Có 200 chiếc kẹo được chia cho 21 học sinh. Chứng minh rằng với mọi cách chia,luôn tồn tại hai học sinh có số kẹo như nhau ( kể cả được 0 chiếc kẹo )
6. Chứng minh rằng không tồn tại một đường thẳng không đi qua đỉnh và cắt các cạnh của một tam giác. Hỏi còn đúng không đối với trường hợp $2n+1$-giác
7. Chứng minh rằng trong 11 số tự nhiên tùy ý,luôn có thể chọn ra hai số có hiệu bình phương chia hết cho 20
8. Chứng minh rằng có thể tìm được số tự nhiên có dạng 201520152015...2015000...0 chia hết cho 1999
9. Viết $n$ số thành 1 hàng ngang. Chứng minh rằng hoặc có một số chia hết cho $n$ hoặc có một số số liên tiếp có tổng chia hết cho $n$ ( $n>1$ )
10. Trong một giải vô địch bóng đá có 10 đội tham gia,hai đội bất kì phải đấu với nhau đúng một trận. Chứng minh rằng tại mọi thời điểm của giải đấu,luôn có 2 đội có số trận đấu bằng nhau
$\xi 2$ NGUYÊN LÝ CỰC HẠN
nguyên lý cực hạn được phát biểu như sau:
Một tập hợp hữu hạn ( khác rỗng ) các số thực bất kì đều có phần tử lớn nhất hoặc phần tử nhỏ nhất
$(*)$ các trường hợp đặc biệt:
- Đối với một đa giác,các điểm đặc biệt là những điểm thuộc cạnh ( điểm biên ) , các đỉnh ( điểm cực biên ) hoặc các điểm mà tại đó có một đặc trưng nào đó đạt giá trị đặc biệt. Cũng có thể là trọng tâm,tâm tỉ cự,... của 1 hình
- Đối với một tập hợp sắp thứ tự, các điểm đặc biệt là những phần tử nhỏ nhất hoặc lớn nhất của tập hợp
- Một số điểm đặc biệt của trục số $0,1,-1,+\infty,-\infty$
- Đối với một bài tóan có điều kiện,các trường hợp xảy ra khi các biến có mặt bằng nhau hoặc xảy ra dấu đẳng thức trong các đánh giá của điều kiện
- Đối với một hàm số, các điểm đặc biệt là những điểm mà tại đó thì hàm sô không xác định, đạt cực trị,...
Các trường hợp nói trên được gọi là các điểm cực hạn
BÀI TẬP ÁP DỤNG:
1. Chứng minh rằng bốn hình tròn có các đường kính là bốn cạnh của một tứ giác lồi thì phủ kín miền tứ giác đó
2. Chứng minh rằng phương trình $x^2-7y^2=0$ có nghiệm nguyên duy nhất $x=y=0$
3. Bảy người đi câu cá đã câu được 100 con cá. Biết rằng không có hai người nào câu được số cá như nhau. Chứng minh rằng có 3 người trong 7 người câu được câu được tổng số cá không ít hơn 50 con cá
4. Một quốc gia có 100 sân bay. Khoảng cách giữa các sân bay là khác nhau. Mỗi sân bay chỉ có một chuyến bay đến sân bay gần nhất. CMR không có sân bay nào có quá 5 chuyến bay đến
5. Chứng minh rằng trong 15 số nguyên dương thuộc $(2,3,...,1992)$ và đôi một nguyên tố cùng nhau,có ít nhất 1 số nguyên tố
BÀI TẬP TỔNG HỢP VỀ TỔ HỢP RỜI RẠC,CÁC BÀI TÓAN LẬP LUẬN :
1. Có một số bộ các quả cân có tính chất sau:
- Trong bộ có ít nhất 5 quả cân có trọng lượng khác nhau
- Với 2 quả cân bất kì,tìm được 2 quả cân khác có tổng trọng lượng bằng trọng lượng của 2 quả cân đó
Hỏi có ít nhất mấy quả cân?
2. Mặt phẳng phân hoạch thành các tam giác đều bằng nhau sao cho 2 tam giác bất kì hoặc chỉ có đỉnh chung,hoặc chỉ có cạnh chung. Chứng minh rằng tồn tại một hình tròn chứa đúng 2005 đỉnh của các tam giác đó
3. Một đống sỏi có 2009 viên. Chia nó thành 2 phần 1 cách tùy ý. Đếm số sỏi trong mỗi phần rồi ghi lại tích của chúng. Lại chia 1 trong 2 đống sỏi nhỏ ( có số sỏi lớn hơn 1 ) thành 2 phần và ghi lại tích của số viên sỏi trong hai đống nhỏ mới thu được. Cứ làm như vậy cho đến khi thu được 2009 đống sỏi nhỏ mà mỗi đống có đúng một viên. Hãy tính tổng của tất cả các số được ghi lại
4. CMR với mọi $a,b\epsilon N*,(36a+b)(36b+a)$ không thể là một lũy thừa của 2
Bài viết đã được chỉnh sửa nội dung bởi ducvipdh12: 08-05-2015 - 20:46