TAILIEUCHUNG - Nguyên Lí Dirichle & Cực Hạn

Nguyên lý Dirichle và nguyên lý cực hạn là hai nguyên lý có nội dung khá đơn giản, song lại có thể áp dụng rộng rãi trong việc chứng minh các bài toán hình học tổ hợp, số học, đại số, . Bài viết này sẽ giới thiệu một cách tổng quan về hai nguyên lý này. lý Dirichle thiệu: -Dạng 1: Nếu có một ánh xạ từ tập hợp M có n+1 phần tử vào tập hợp có n phần tử thì có ít nhất 2 phần tử của tập hợp M có cùng một ảnh của tập hợp. | Nguyên lý Dirichle và nguyên lý cực hạn Nguyên lý Dirichle và nguyên lý cực hạn là hai nguyên lý có nội dung khá đơn giản song lại có thể áp dụng rộng rãi trong việc chứng minh các bài toán hình học tổ hợp số học đại số . Bài viết này sẽ giới thiệu một cách tổng quan về hai nguyên lý này. lý Dirichle I. Giới thiệu -Dạng 1 Nếu có một ánh xạ từ tập hợp M có n 1 phần tử vào tập hợp có n phần tử thì có ít nhất 2 phần tử của tập hợp M có cùng một ảnh của tập hợp N qua ánh xạ đó. -Dạng 2 Nếu nhốt N chú thỏ vào n chuồng mà N nk thì có ít nhất một chuồng nhốt nhiều hơn hai chú thỏ. Mở rộng nếu chia tập hợp vô hạn các chú thỏ vào hữu hạn chuồng thì tồn tại ít nhất một chuồng có vô hạn chú thỏ . II. Ví dụ Các bài toán trong phần này sẽ giúp bạn đọc làm quen với cách áp dụng nguyên lý này. Bài toán 1 Cho bảng vuông gồm n x n ô vuông. Mỗi ô vuông ghi một trong các số 0 1 2. CM không tồn tại bảng vuông nào mà tổng các ô trên hàng ngang cột dọc và đường chéo là các số khác nhau hoàn toàn. Giải Giá trị trên cột hàng đường chéo có giá trị nhỏ nhất là 0 x n 0 và có giá trị lớn nhất là 2n mà ta có 2n 2 tổng nhưng chỉ có 2n 1 giá trị từ 0 đến 2n nên theo nguyên lý Dirichle phải có ít nhất 2 tổng có giá trị bằng nhau đpcm. Bài toán 2 Cho hình tròn diện tích S lấy n điểm bất kỳ n 2 .CMR có ba điểm tạo thành tam giác có diện tích nhỏ hơn S k với k là số nguyên lớn nhất nhỏ hơn n-1 2 Giải Ta dễ dàng nghĩ đến việc chia đường tròn thành k phần hình quạt bằng nhau theo nguyên lý Dirichle tồn tại 3 điểm thuộc cùng một hình quạt. Gọi ba điểm đó là A B có SABC Shình quạt S k đpcm . Bài toán 3 Bên trong hình tròn bán kính 5 lấy 10 điểm bất kỳ có khoảng cách nhỏ hơn 4 Nhật-97 Giải đầu tiên ta nghĩ đến việc chia hình tròn thành 9 hình quạt bằng nhau như bài toán 2 nhưng cách chia này sẽ không giải quyết được bài toán vì tồn tại 2 điểm trong hình quạt có khoảng cách lớn hơn 4. Sau một lát suy nghĩ ta nhận thấy không cần phải chia hẹp và y dài như thế từ đó ta có cách chia hợp lý như

TỪ KHÓA LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.