Các kiến thức cơ bản 1
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 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 chuồng có ít nhất n+m −1 m con thỏ, ở đây kí hiệu [α] để chỉ phần nguyên của số α.
Ta chứng minh nguyên lí Dirichlet mở rộng như sau : Giả sử trái lại mọi chuồng thỏ không có đến n+m −1 m n −1 m + 1 n −1 m
+ 1 con, thì số thỏ trong mỗi chuồng đều nhỏ hơn hoặc bằng n − 1 m con Từ đó suy ra tổng số con thỏ không vượt quá m. n −1 m
≥ n −1 con Điều này vô lí vì có n con thỏ Vậy giả thiết phản chứng là sai.
Nguyên lí Dirichlet mở rộng được chứng minh.
Nguyên lý Dirichlet, mặc dù có vẻ đơn giản, là một công cụ mạnh mẽ trong việc chứng minh nhiều kết quả quan trọng trong toán học Nguyên lý này có nhiều ứng dụng trong các lĩnh vực khác nhau của toán học Trong nhiều trường hợp, người ta có thể dễ dàng chứng minh sự tồn tại mà không cần tìm ra phương pháp cụ thể, và trong thực tế, việc chỉ ra sự tồn tại thường là đủ cho nhiều bài toán.
Nguyên lí Dirichlet thực chất là một định lí về tập hữu hạn Người ta có thể phát biểu chính xác nguyên lí này dưới dạng sau đây.
Nguyên lí Dirichlet dạng tập hợp
Cho hai tập hợp A và B, đều là các tập hợp khác rỗng và có số lượng phần tử hữu hạn, với số phần tử của A lớn hơn số phần tử của B Theo quy tắc ánh xạ, nếu mỗi phần tử của A tương ứng với một phần tử của B, thì sẽ có ít nhất hai phần tử khác nhau trong A mà chúng ánh xạ đến cùng một phần tử trong B.
Với cùng một cách diễn đạt như vậy, nguyên lí Dirichlet mở rộng có dạng sau đây.
Nguyên lí Dirichlet dạng tập hợp mở rộng
Giả sử A và B là hai tập hợp hữu hạn với số lượng phần tử lần lượt là S(A) và S(B) Nếu S(A) lớn hơn k lần S(B) với k là một số tự nhiên, thì sẽ có ít nhất k + 1 phần tử của A tương ứng với cùng một phần tử của B.
Chú ý: Khi k = 1, ta có ngay lại nguyên lí Dirichlet.
Ứng dụng nguyên lý Dirichlet vào bài toán hình học tổ hợp 4 Chương 3 Ứng dụng nguyên lí Dirichlet vào số học 25 Chương 4 Ứng dụng nguyên lí Dirichlet vào các bài toán khác 42 Tài liệu tham khảo
Dirichlet vào bài toán hình học tổ hợp
Chương này giới thiệu phương pháp ứng dụng nguyên lý Dirichlet để giải quyết các bài toán hình học tổ hợp Chúng tôi sẽ trình bày một số mệnh đề, cụ thể là các nguyên lý Dirichlet áp dụng cho độ dài đoạn thẳng, diện tích hình phẳng và thể tích vật thể, thường được sử dụng trong nhiều bài toán hình học tổ hợp trong chương này.
Mệnh đề 2.1 Nguyên lí Dirichlet cho diện tích
Nếu K là một hình phẳng, cònK 1 , K 2 , , K n là các hình phẳng sao choK i ⊆ K với i= 1, n và
| K | < | K 1 |+ | K 2 |+ ã ã ã + | K n | Ở đây | K | là diện tích của hình phẳng K, còn | K i | là diện tích của hình phẳng
K i , i= 1, n, thì tồn tại ít nhất hai hình phẳng H i , H j ,(1 ≤ i ≤ j ≤ n) sao cho H i và
Điểm P được gọi là điểm trong của tập hợp A trên mặt phẳng nếu tồn tại một hình tròn với tâm P và bán kính đủ nhỏ, sao cho hình tròn này hoàn toàn nằm trong tập hợp A.
Tương tự nguyên lí Dirichlet cho diện tích, ta có nguyên lí Dirichlet cho độ dài các đoạn thẳng, thể tích các vật thể.
Nguyên lí Dirichlet còn được phát biểu cho trường hợp vô hạn như sau.
Nguyên lý Dirichlet vô hạn khẳng định rằng khi phân chia một tập hợp vô hạn các quả táo vào một số hữu hạn ngăn kéo, thì ít nhất một ngăn kéo sẽ chứa vô hạn quả táo.
Ta bắt đầu sử dụng nguyên lí Dirichlet để giải các bài toán hình học tổ hợp sau đây.
Trong mặt phẳng, với sáu điểm không có ba điểm nào thẳng hàng, khi nối từng cặp điểm bằng các đoạn thẳng màu đỏ hoặc xanh, có thể chứng minh rằng luôn tồn tại ba điểm trong số đó tạo thành ba đỉnh của một tam giác có các cạnh cùng màu.
Xét điểm A trong số sáu điểm cho trước, ta có năm đoạn thẳng nối A với các điểm còn lại Theo nguyên lý Dirichlet, ít nhất ba trong năm đoạn thẳng này sẽ cùng màu, với giả thuyết rằng các đoạn AB1, AB2, AB3 đều có màu xanh Do đó, chỉ có hai khả năng xảy ra.
Nếu có ít nhất một trong ba đoạn B1B2, B2B3, B3B1 có màu xanh, thì sẽ tồn tại một tam giác với ba cạnh màu xanh, và trong trường hợp này, kết luận của bài toán là đúng.
2 Nếu không phải như vậy, tức là B 1 B 2 , B 2 B 3 , B 3 B 1 màu đỏ, thì ba điểm phải tìm là B 1 , B 2 , B 3 , vì B 1 B 2 B 3 là tam giác với ba cạnh đỏ
Trong hình chóp có đáy là một đa giác chín cạnh, tất cả các cạnh bên và 27 đường chéo của đa giác đáy được tô màu đỏ hoặc xanh Cần chứng minh rằng luôn tồn tại ba đỉnh của hình chóp tạo thành một tam giác với các cạnh cùng màu.
Xét chín cạnh bên được bôi bằng hai màu đỏ hoặc xanh, theo nguyên lý Dirichlet, sẽ tồn tại năm cạnh bên cùng màu Giả sử các cạnh bên SA1, SA2, SA3, SA4, SA5 được bôi màu đỏ, và các điểm A1, A2, A3, A4, A5 được sắp xếp theo chiều ngược kim đồng hồ Từ đó, ta có thể xem xét đa giác A1A2A3A4A5 với hai khả năng xảy ra.
1 Nếu A 1 A 2 là đường chéo của đáy, khi đó dĩ nhiên A 2 A 4 , A 4 A 1 cũng là các đường chéo của đáy.
Lại có hai khả năng sau xảy ra:
(a) Nếu cả ba đoạn A 1 A 2 , A 2 A 4 , A 4 A 1 cùng bôi màu xanh Khi đó A 1 , A 2 , A 4 là ba đỉnh cần tìm, vì tam giác A 1 A 2 A 4 là tam giác với ba cạnh xanh.
(b) Nếu một trong các đoạn A 1 A 2 , A 2 A 4 , A 4 A 1 là đỏ Giả sử A 2 A 4 đỏ, thì
SA 2 A 4 là tam giác với ba cạnh đỏ Lúc này S, A 2 , A 4 là ba đỉnh cần tìm. Trường hợp 1 đã giải quyết xong.
2 Nếu A 1 A 2 là cạnh đáy Khi đó dĩ nhiên A 1 A 3 , A 3 A 5 chắc chắn là đường chéo đáy.
(a) Nếu A 1 A 5 là đường chéo đáy thì ta quay về trường hợp 1 vừa xét, với
A 1 A 3 A 5 là tam giác với ba cạnh là ba đường chéo đáy.
(b) Nếu A 1 A 5 là cạnh đáy Khi đó rõ ràngA 1 A 3 , A 1 A 4 là các đường chéo đáy.
NếuA 3 A 4 là đường chéo đáy, ta quay về trường hợp 1, nếu A 3 A 4 là cạnh bên. Lại xét hai khả năng sau:
1 Nếu A 2 A 3 là đường chéo đáy, thì tam giác A 2 A 3 A 5 là tam giác với ba cạnh là ba đường chéo đáy, ta quay về trường hợp 1.
2 NếuA 2 A 3 là cạnh đáy Khi đó xét tam giác A 2 A 4 A 5 và quay về trường hợp 1. Tóm lại bài toán đã được giải quyết xong hoàn toàn
Trong một hình vuông đơn vị có cạnh bằng 1, tồn tại 101 điểm Cần chứng minh rằng trong số các điểm này, ít nhất có năm điểm có thể được bao phủ bởi một đường tròn có bán kính 1.
Chia hình vuông ra làm 25 hình vuông bằng nhau, mỗi cạnh của hình vuông là
Theo nguyên lý Dirichlet, với 101 điểm và chỉ 25 hình vuông, chắc chắn sẽ có ít nhất một hình vuông nhỏ chứa ít nhất năm điểm trong số 101 điểm đã cho Hình vuông này nằm trong đường tròn có bán kính R.
7 nên dĩ nhiên đường tròn đồng tâm với đường tròn ngoại tiếp trên và có bán kính 1
7 chứa ít nhất năm điểm nói trên
Trên mặt phẳng có 25 điểm, với điều kiện rằng trong bất kỳ ba điểm nào luôn tồn tại hai điểm cách nhau nhỏ hơn 1 Điều này cho thấy rằng có ít nhất một hình tròn bán kính 1 có thể chứa không dưới 13 trong số các điểm đã cho.
Lấy A là một trong số 25 điểm đã cho Xét hình trònΩ 1 (A; 1) tâmA, bán kính
1 Chỉ có hai khả năng sau xảy ra:
1 Nếu tất cả các điểm đã cho nằm trongΩ 1 thì kết luận của bài toán hiển nhiên đúng.
2 Tồn tại điểm A 6= B (B thuộc trong số 25 điểm đã cho), sao choB / ∈ Ω 1 Vì
B vì không thuộc Ω 1, nên khoảng cách AB lớn hơn 1 Xét hình tròn Ω 2 với tâm B và bán kính 1, chọn điểm C từ 25 điểm đã cho sao cho C không bằng A và B Dựa vào giả thiết và điều kiện AB > 1, ta có min { CA, CB } nhỏ hơn 1, dẫn đến C thuộc Ω 1 hoặc Ω 2 Điều này chứng minh rằng cả hai hình tròn Ω 1 và Ω 2 đều chứa tất cả 25 điểm đã cho Theo nguyên lý Dirichlet, ít nhất một trong hai hình tròn này chứa không ít hơn 13 điểm trong số đó.
Chú ý: Bài toán có dạng tổng quát như sau (cách giải hoàn toàn tương tự).
Cho 2n + 1 điểm trên mặt phẳng (với n ≥ 3), trong bất kỳ ba điểm nào trong số đó, luôn có hai điểm cách nhau nhỏ hơn 1 Do đó, tồn tại một hình tròn bán kính 1 chứa ít nhất n + 1 điểm trong số các điểm đã cho.
Ví dụ 2.5 Cho chín đường thẳng cùng có tính chất là mỗi đường thẳng chia hình vuông thành hai tứ giác có tỉ số diện tích bằng 2
3 Chứng minh rằng có ít nhất ba đường thẳng trong số đó cùng đi qua một điểm.
Các đường thẳng đã cho không thể cắt các cạnh kề nhau của hình vuông, vì nếu vậy, chúng sẽ chia hình vuông thành một tam giác và một ngũ giác, thay vì hai hình tứ giác Do đó, mọi đường thẳng trong số chín đường thẳng đều cắt hai cạnh đối của hình vuông mà không đi qua đỉnh nào Giả sử một đường thẳng cắt hai cạnh đối BC và AD tại các điểm M và N.
E và F là các trung điểm của đoạn thẳng AB và CD Các điểm E, F, P, Q lần lượt là trung điểm của các đoạn AB, BC, CD và DA Đồng thời, J1, J2 là hai điểm nằm trên EF, còn J3, J4 nằm trên PQ, và chúng phải thỏa mãn một số điều kiện nhất định.