Luận Văn Thạc Sĩ Về Phương Pháp Đếm Trong Hình Học Tổ Hợp

Luận văn thạc sĩ toán học phân tích hay một số phương pháp đếm trong các bài toán hình học tổ hợp, đánh giá thực trạng, chỉ ra hạn chế, đề xuất giải pháp khả thi cho thực tiễn.

• Tác giả: Dương Thúy Quỳnh
• Người hướng dẫn: GS. Nguyễn Văn Mậu
• Trường học: Đại học Thái Nguyên
• Chuyên ngành: Phương Pháp Toán Sơ Cấp
• Đề tài: Một Số Phương Pháp Đếm Trong Các Bài Toán Hình Học Tổ Hợp
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2016
• Địa điểm: Thái Nguyên

Mục lục chi tiết

• MỞ ĐẦU
• 1. CHƯƠNG 1: Một số kiến thức chuẩn bị
• 1.1. Các quy tắc đếm cơ bản
• 1.2. Một số nguyên lý cơ bản
• 2. CHƯƠNG 2: Phân loại và các phương pháp giải các bài toán đếm trong hình học tổ hợp
• 2.1. Phân loại các bài toán đếm
• 2.1.1. Đếm đối tượng tạo bởi điểm, đoạn thẳng, đường thẳng
• 2.1.2. Đếm đối tượng tạo thành miền trong mặt phẳng
• Tài liệu tham khảo

Tóm tắt

I. Tổng Quan Về Phương Pháp Đếm Trong Hình Học Tổ Hợp

Phương pháp đếm trong hình học tổ hợp là một lĩnh vực quan trọng trong toán học, giúp giải quyết các bài toán phức tạp liên quan đến việc xác định số lượng các cấu trúc hình học. Hình học tổ hợp không chỉ xuất hiện trong các bài thi học sinh giỏi mà còn trong nhiều ứng dụng thực tiễn. Việc nắm vững các phương pháp đếm sẽ giúp học sinh và sinh viên có thể tiếp cận và giải quyết các bài toán một cách hiệu quả hơn.

1.1. Khái Niệm Cơ Bản Về Hình Học Tổ Hợp

Hình học tổ hợp là một nhánh của toán học nghiên cứu về các cấu trúc hình học và mối quan hệ giữa chúng. Các bài toán trong lĩnh vực này thường yêu cầu người giải phải sử dụng các phương pháp đếm để xác định số lượng các đối tượng hình học.

1.2. Tầm Quan Trọng Của Phương Pháp Đếm

Phương pháp đếm không chỉ giúp giải quyết các bài toán lý thuyết mà còn có ứng dụng thực tiễn trong nhiều lĩnh vực như khoa học máy tính, thống kê và thiết kế đồ họa. Việc hiểu rõ các phương pháp này sẽ giúp nâng cao khả năng tư duy logic và phân tích.

II. Các Vấn Đề Thách Thức Trong Phương Pháp Đếm

Mặc dù phương pháp đếm trong hình học tổ hợp rất hữu ích, nhưng vẫn tồn tại nhiều thách thức trong việc áp dụng chúng vào các bài toán cụ thể. Các vấn đề này thường liên quan đến việc xác định đúng các quy tắc đếm và phân loại các đối tượng cần đếm.

2.1. Khó Khăn Trong Việc Phân Loại Bài Toán

Việc phân loại các bài toán đếm là rất quan trọng, nhưng không phải lúc nào cũng dễ dàng. Các bài toán có thể thuộc nhiều loại khác nhau, và việc xác định đúng loại sẽ giúp chọn phương pháp giải phù hợp.

2.2. Ứng Dụng Các Quy Tắc Đếm

Các quy tắc đếm như quy tắc cộng và quy tắc nhân thường được sử dụng, nhưng việc áp dụng chúng một cách chính xác trong các bài toán phức tạp có thể gặp khó khăn. Cần có sự hiểu biết sâu sắc về các quy tắc này để tránh sai sót.

III. Phương Pháp Đếm Cơ Bản Trong Hình Học Tổ Hợp

Có nhiều phương pháp đếm cơ bản trong hình học tổ hợp, bao gồm quy tắc cộng, quy tắc nhân, và các nguyên lý như nguyên lý Dirichlet. Những phương pháp này là nền tảng để giải quyết các bài toán phức tạp hơn.

3.1. Quy Tắc Cộng Và Quy Tắc Nhân

Quy tắc cộng cho phép xác định số cách thực hiện một công việc khi có nhiều phương án khác nhau, trong khi quy tắc nhân áp dụng cho các công việc có thể chia thành nhiều công đoạn. Việc hiểu rõ hai quy tắc này là rất cần thiết.

3.2. Nguyên Lý Dirichlet Trong Đếm

Nguyên lý Dirichlet, hay còn gọi là nguyên lý chuồng chim, là một công cụ mạnh mẽ trong việc chứng minh sự tồn tại của các đối tượng trong các bài toán đếm. Nguyên lý này giúp đơn giản hóa nhiều bài toán phức tạp.

IV. Ứng Dụng Thực Tiễn Của Phương Pháp Đếm

Phương pháp đếm trong hình học tổ hợp không chỉ có giá trị lý thuyết mà còn có nhiều ứng dụng thực tiễn trong các lĩnh vực như khoa học máy tính, thống kê và thiết kế đồ họa. Việc áp dụng các phương pháp này giúp giải quyết nhiều bài toán thực tế.

4.1. Ứng Dụng Trong Khoa Học Máy Tính

Trong khoa học máy tính, phương pháp đếm được sử dụng để phân tích thuật toán và tối ưu hóa quy trình. Việc hiểu rõ các phương pháp đếm giúp lập trình viên phát triển các giải pháp hiệu quả hơn.

4.2. Ứng Dụng Trong Thống Kê

Trong thống kê, phương pháp đếm giúp xác định xác suất và phân tích dữ liệu. Việc áp dụng các quy tắc đếm giúp đưa ra các kết luận chính xác hơn từ dữ liệu thu thập được.

V. Kết Luận Về Phương Pháp Đếm Trong Hình Học Tổ Hợp

Phương pháp đếm trong hình học tổ hợp là một lĩnh vực quan trọng, cung cấp nhiều công cụ hữu ích để giải quyết các bài toán phức tạp. Việc nắm vững các phương pháp này không chỉ giúp trong học tập mà còn trong các ứng dụng thực tiễn.

5.1. Tương Lai Của Phương Pháp Đếm

Với sự phát triển của công nghệ và khoa học, phương pháp đếm trong hình học tổ hợp sẽ tiếp tục được nghiên cứu và phát triển. Các ứng dụng mới sẽ mở ra nhiều cơ hội cho việc áp dụng các phương pháp này.

5.2. Khuyến Khích Nghiên Cứu Thêm

Cần khuyến khích nghiên cứu thêm về các phương pháp đếm và ứng dụng của chúng trong các lĩnh vực khác nhau. Việc này sẽ giúp nâng cao hiểu biết và khả năng giải quyết vấn đề trong toán học.

Nội dung chính

Tổng quan nghiên cứu

Hình học tổ hợp là một lĩnh vực quan trọng trong toán học, đặc biệt trong tổ hợp và hình học, với ứng dụng rộng rãi trong các kỳ thi học sinh giỏi và Olympic toán học. Theo ước tính, các bài toán đếm trong hình học tổ hợp thường có độ phức tạp cao, đòi hỏi sự linh hoạt và sáng tạo trong phương pháp giải. Tuy nhiên, tài liệu tham khảo về lĩnh vực này tại Việt Nam còn hạn chế, đặc biệt là các tài liệu chuyên sâu về phương pháp đếm trong hình học tổ hợp. Luận văn này nhằm mục tiêu cung cấp một hệ thống các phương pháp đếm hiệu quả, bao gồm nguyên lí bất biến, nguyên lí Dirichlet và nguyên lí cực hạn, áp dụng cho các bài toán đếm trong hình học tổ hợp. Phạm vi nghiên cứu tập trung vào các bài toán đếm đối tượng tạo bởi điểm, đoạn thẳng, đường thẳng, cũng như các đối tượng tạo thành miền trong mặt phẳng, với các ví dụ minh họa từ các đề thi học sinh giỏi quốc gia và quốc tế. Ý nghĩa của nghiên cứu được thể hiện qua việc cung cấp tài liệu tham khảo bổ ích cho học sinh phổ thông và giáo viên, đồng thời góp phần phát triển phương pháp giải bài toán tổ hợp trong toán học sơ cấp.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên ba nguyên lí cơ bản trong toán học tổ hợp và hình học tổ hợp:

• Nguyên lí bất biến: Tính chất hoặc đại lượng không thay đổi qua các phép biến đổi trong hệ thống, giúp chứng minh sự tồn tại hoặc không tồn tại của các đối tượng trong bài toán.
• Nguyên lí Dirichlet (Nguyên lí chuồng bồ câu): Nếu phân phối nhiều đối tượng vào ít ngăn chứa, sẽ có ít nhất một ngăn chứa nhiều hơn một đối tượng, được áp dụng để chứng minh sự tồn tại các cấu hình đặc biệt trong hình học tổ hợp.
• Nguyên lí cực hạn: Trong tập hợp hữu hạn các số thực, luôn tồn tại giá trị lớn nhất hoặc nhỏ nhất, được sử dụng để phân tích các phần tử biên trong bài toán.

Các khái niệm chính bao gồm quy tắc cộng, quy tắc nhân, tổ hợp, chỉnh hợp, hoán vị, cũng như các đối tượng đếm như điểm, đoạn thẳng, đường thẳng, miền trong mặt phẳng, và các cấu hình tô màu, đếm cấu hình.

Phương pháp nghiên cứu

Nghiên cứu sử dụng phương pháp tổng hợp lý thuyết toán học với các ví dụ minh họa cụ thể từ các bài toán thực tế và đề thi học sinh giỏi. Nguồn dữ liệu chính là các bài toán hình học tổ hợp được phân loại và phân tích chi tiết trong luận văn. Phân tích được thực hiện thông qua việc áp dụng các nguyên lí bất biến, Dirichlet và cực hạn để giải quyết các bài toán đếm phức tạp. Cỡ mẫu nghiên cứu bao gồm hàng chục bài toán với các trường hợp đa dạng, được chọn lọc từ các đề thi và tài liệu chuyên ngành. Timeline nghiên cứu kéo dài trong năm 2016, với sự hướng dẫn của GS.TSKH Nguyễn Văn Mậu tại Trường Đại học Khoa học, Đại học Thái Nguyên.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Phân loại bài toán đếm trong hình học tổ hợp: Các bài toán được chia thành đếm đối tượng tạo bởi điểm, đoạn thẳng, đường thẳng và đếm đối tượng tạo thành miền trong mặt phẳng. Ví dụ, số giao điểm lớn nhất của n đường thẳng không song song và không đồng quy là $\binom{n}{2}$, số giao điểm lớn nhất của n đường tròn là $n^2 - n + 2$.

2. Hiệu quả của nguyên lí bất biến: Áp dụng nguyên lí bất biến giúp giải quyết các bài toán phức tạp như xác định dấu còn lại sau nhiều lần thay đổi, chứng minh không thể lát kín nền nhà bằng các viên gạch kích thước khác nhau, hoặc chứng minh không thể đi hết các ô trên bàn cờ vua bằng quân mã trong điều kiện nhất định. Ví dụ, trong bài toán với 2015 dấu cộng và 2016 dấu trừ, dấu còn lại sau 4030 lần thay đổi là dấu cộng (+).

3. Ứng dụng nguyên lí Dirichlet trong chứng minh tồn tại: Nguyên lí Dirichlet được sử dụng để chứng minh sự tồn tại của các điểm hoặc cấu hình đặc biệt, như tồn tại ít nhất 3 điểm trong một hình tròn bán kính nhỏ hơn, hoặc tồn tại đường thẳng cắt ít nhất 4 đường tròn khi tổng chu vi các đường tròn vượt quá một giá trị nhất định. Ví dụ, trong hình vuông cạnh 1 chứa 51 điểm, tồn tại ít nhất 3 điểm nằm trong một hình tròn bán kính $\frac{1}{\sqrt{7}}$.

4. Phương pháp nguyên lí cực hạn giúp giải quyết bài toán tối ưu: Nguyên lí cực hạn được vận dụng để chứng minh các bất đẳng thức về diện tích tam giác, tính chất tứ giác, và các bài toán về khoảng cách giữa các điểm trong không gian. Ví dụ, khi tất cả các cạnh tam giác đều nhỏ hơn 1, diện tích tam giác nhỏ hơn $\frac{\sqrt{3}}{4}$.

Thảo luận kết quả

Các phương pháp được nghiên cứu đều có tính ứng dụng cao và bổ sung cho nhau trong việc giải các bài toán đếm phức tạp. Nguyên lí bất biến giúp giữ vững các đại lượng quan trọng trong quá trình biến đổi, nguyên lí Dirichlet chứng minh sự tồn tại mà không cần xây dựng cụ thể, còn nguyên lí cực hạn tập trung vào các giá trị biên để rút gọn bài toán. So sánh với các nghiên cứu khác, luận văn đã hệ thống hóa và minh họa rõ ràng các phương pháp này trong hình học tổ hợp, đồng thời cung cấp các bài tập có lời giải chi tiết, sáng tạo. Dữ liệu có thể được trình bày qua bảng tổng hợp số lượng giao điểm, biểu đồ minh họa các cấu hình tô màu, hoặc sơ đồ các phép biến đổi bất biến, giúp người đọc dễ dàng hình dung và áp dụng.

Đề xuất và khuyến nghị

1. Phát triển tài liệu giảng dạy chuyên sâu về hình học tổ hợp: Cần biên soạn thêm sách và tài liệu tham khảo dựa trên các phương pháp đếm đã nghiên cứu, nhằm nâng cao chất lượng giảng dạy và học tập trong các trường phổ thông và đại học.

2. Tổ chức các khóa đào tạo và hội thảo chuyên đề: Định kỳ tổ chức các khóa học, hội thảo về phương pháp giải bài toán tổ hợp và hình học tổ hợp cho giáo viên và học sinh nhằm nâng cao kỹ năng giải toán sáng tạo.

3. Ứng dụng các phương pháp vào nghiên cứu và thi đấu toán học: Khuyến khích học sinh, sinh viên áp dụng các phương pháp này trong các kỳ thi học sinh giỏi, Olympic toán học để nâng cao hiệu quả giải bài và phát triển tư duy toán học.

4. Phát triển phần mềm hỗ trợ giải bài toán đếm: Xây dựng các công cụ phần mềm mô phỏng và giải các bài toán đếm trong hình học tổ hợp, giúp người học thực hành và kiểm tra kết quả nhanh chóng.

Đối tượng nên tham khảo luận văn

1. Học sinh phổ thông có đam mê toán học: Luận văn cung cấp tài liệu bổ ích giúp học sinh nâng cao kỹ năng giải các bài toán tổ hợp và hình học tổ hợp, đặc biệt trong các kỳ thi học sinh giỏi.

2. Giáo viên và giảng viên toán học: Tài liệu giúp giáo viên có thêm phương pháp giảng dạy sinh động, hiệu quả, đồng thời hỗ trợ giảng viên đại học trong việc nghiên cứu và giảng dạy môn toán sơ cấp.

3. Nghiên cứu sinh và sinh viên chuyên ngành toán học: Luận văn là nguồn tham khảo quý giá cho các nghiên cứu sâu hơn về tổ hợp và hình học tổ hợp, cũng như phát triển các phương pháp giải mới.

4. Người tổ chức và huấn luyện viên các kỳ thi toán học: Giúp xây dựng đề thi, huấn luyện thí sinh với các bài toán đếm đa dạng, nâng cao chất lượng và tính sáng tạo trong thi cử.

Câu hỏi thường gặp

1. Phương pháp nguyên lí bất biến là gì và khi nào nên sử dụng?
   Nguyên lí bất biến là tính chất không đổi qua các phép biến đổi trong hệ thống. Nó được sử dụng khi bài toán có các phép biến đổi lặp đi lặp lại và cần chứng minh sự tồn tại hoặc không tồn tại của trạng thái cuối cùng. Ví dụ, trong bài toán thay đổi dấu trên bảng, tích các dấu là bất biến.

2. Nguyên lí Dirichlet giúp giải quyết bài toán như thế nào?
   Nguyên lí Dirichlet chứng minh sự tồn tại của ít nhất một đối tượng thỏa mãn điều kiện nhất định khi phân phối nhiều đối tượng vào ít ngăn chứa. Ví dụ, chứng minh tồn tại ít nhất 3 điểm trong một hình tròn nhỏ khi đặt nhiều điểm trong hình vuông.

3. Nguyên lí cực hạn có vai trò gì trong hình học tổ hợp?
   Nguyên lí cực hạn giúp xác định các phần tử biên như giá trị lớn nhất hoặc nhỏ nhất trong tập hợp, từ đó rút gọn bài toán và chứng minh các bất đẳng thức hoặc tính chất hình học. Ví dụ, chứng minh diện tích tam giác nhỏ hơn một giá trị khi các cạnh nhỏ hơn 1.

4. Làm thế nào để áp dụng các phương pháp này vào giải bài toán thực tế?
   Cần phân tích bài toán để xác định tính chất bất biến, phân phối đối tượng hoặc phần tử biên, sau đó lựa chọn nguyên lí phù hợp để chứng minh hoặc tìm lời giải. Các ví dụ trong luận văn minh họa cách áp dụng cụ thể từng phương pháp.

5. Có thể kết hợp các phương pháp này trong một bài toán không?
   Có, nhiều bài toán phức tạp yêu cầu kết hợp nguyên lí bất biến, Dirichlet và cực hạn để giải quyết hiệu quả. Ví dụ, sử dụng nguyên lí cực hạn để xác định phần tử biên, nguyên lí Dirichlet để chứng minh tồn tại, và nguyên lí bất biến để giữ tính chất không đổi trong quá trình biến đổi.

Kết luận

• Luận văn hệ thống hóa và minh họa ba phương pháp đếm chính trong hình học tổ hợp: nguyên lí bất biến, nguyên lí Dirichlet và nguyên lí cực hạn.
• Cung cấp các bài toán mẫu với lời giải chi tiết, giúp người học phát triển tư duy sáng tạo và kỹ năng giải toán tổ hợp.
• Đề xuất phát triển tài liệu giảng dạy, tổ chức đào tạo và ứng dụng rộng rãi trong giáo dục và nghiên cứu.
• Khuyến khích áp dụng các phương pháp kết hợp để giải quyết các bài toán phức tạp hơn trong tương lai.
• Mời độc giả tiếp tục nghiên cứu, thực hành và phát triển các phương pháp đếm trong hình học tổ hợp nhằm nâng cao chất lượng học thuật và ứng dụng thực tiễn.

Hãy bắt đầu áp dụng các phương pháp này trong nghiên cứu và giảng dạy để nâng cao hiệu quả giải toán tổ hợp và hình học tổ hợp!

Trích đoạn nội dung tài liệu

Chương 1 Một số kiến thức chuẩn bị 1.1 Các quy tắc đếm cơ bản 1.1 Quy tắc cộng và quy tắc nhân Quy tắc cộng: Nếu công việc A có hai phương án thực hiện (loại trừ lẫn nhau), phương án 1 có n1 cách thực hiện, phương án 2 có n2 cách thực hiện thì công việc A có n1 + n2 cách thực hiện. Trên ngôn ngữ tập hợp: A∩B = ∅ thì |A ∪ B| = |A| + |B|. Quy tắc nhân: Nếu công việc A có thể chia thành 2 công đoạn tiếp nối nhau, công đoạn 1 có n1 cách thực hiện, công đọan 2 có n2 cách thực hiện thì công việc A có n1 .n2 cách thực hiện. Trên ngôn ngữ tập hợp: |A.

Quy tắc phần bù: |A| = |X| − |A|, trong đó A là phần bù của A trong X.2 Tổ hợp và chỉnh hợp Xét tập hợp X gồm n phần tử. Từ tập hợp cơ bản này, ta có thể xây dựng các đối tượng tổ hợp phong phú. Tập các tập con của tập X : Tập các tập con của X được ký hiệu là P (X). Các tập con của một tập hợp là một đối tượng xuất hiện khá nhiều trong các bài toán đếm.

Chỉnh hợp: Chỉnh hợp chập k của một tập hợp là một bộ k phần tử phân LUAN VAN CHAT LUONG download : add [e-mail] 4 biệt được sắp thứ tự của tập hợp ấy. Ví dụ nếu X = {1, 2, 3} và k = 2 thì ta có các chỉnh hợp là (1, 2), (1,3), (2, 1), (2, 3), (3, 1), (3, 2). Số các chỉnh hợp chập k của n phần tử được ký hiệu là Akn. Hoán vị: Hoán vị của n phần tử là chỉnh hợp chập n của n phần tử đó, nói cách khác, là một cách sắp thứ tự các phần tử đó.

Hoán vị của X còn có thể định nghĩa như một song ánh từ X vào X. Số các hoán vị của n phần tử được ký hiệu là Pn. Tổ hợp: Tổ hợp chập k của một tập hợp là một bộ k phần tử phân biệt không sắp thứ tự của tập hợp ấy. Nói cách khác, đó là một tập con k phần tử.

Ví dụ nếu X = {1, 2, 3} và k = 2 thì ta có các tổ hợp là {1, 2}, {1, 3}, {2, 3}. Số các tổ chập k của n phần tử được ký hiệu là Cnk. Chỉnh hợp lặp: Chỉnh hợp lặp chập k của một tập hợp là một bộ k phần tử không nhất thiết phân biệt được sắp thứ tự của tập hợp ấy. Ví dụ nếu X = {1, 2, 3} và k = 2 thì ta có các chỉnh hợp lặp là {1, 1}, {1, 2}, {1, 3}, {2, 1}, {2, 2}, {2, 3}, {3, 1}, {3, 2}, {3, 3}.

Số các chỉnh hợp lặp chập k của k n phần tử được ký hiệu là An. Tổ hợp lặp: Tổ hợp lặp chập k của một tập hợp là một bộ k phần tử không nhất thiết phân biệt không sắp thứ tự của tập hợp ấy. Ví dụ nếu X = {1, 2, 3} và k = 2 thì ta có các tổ hợp lặp là {1, 1}, {1, 2}, {1, 3}, {2, 2}, {2, 3}, {3, 3}. Số các tổ hợp lặp chập k của n phần tử được ký hiệu k là C n .2 Một số nguyên lý cơ bản 1.1 Bất biến a) Khái niệm bất biến Giả sử ta có một hệ thống (X) các đại lượng và các phép biến đổi theo thứ tự.

Tính chất P được gọi là bất biến sau s bước trong hệ thống (X) nếu cứ sau s bước biến đổi ta đều nhận lại được tính chất P. b) Ứng dụng nguyên lý bất biến LUAN VAN CHAT LUONG download : add [e-mail] 5 Bất biến là những đại lượng (hay tính chất) không thay đổi trong quá trình chúng ta thực hiện các phép biến đổi. Chẳng hạn khi thực hiện phép tịnh tiến thì khoảng cách giữa hai điểm sẽ không thay đổi. Với phép vị tự thì khác, khoảng cách có thể sẽ thay đổi nhưng sẽ có một bất biến khác, đó là tỉ lệ giữa hai đoạn thẳng.

Có hai mẫu bài toán tổng quát thường được giải quyết bằng bất biến Bài toán tổng quát 1. Có một tập hợp các trạng thái X và tập hợp các phép biến đổi T từ X vào X. Có hai trạng thái a và b thuộc X , hỏi có thể dùng hữu hạn các phép biến đổi thuộc T để đưa trạng thái a về trạng thái b được không? Bài toán tổng quát 1. Có một tập hợp các trạng thái X và tập hợp các phép biến đổi T từ X vào X.

Cần chứng minh rằng bắt đầu từ một trạng thái a bất kì, sau một số hữu hạn các phép biến đổi từ T , ta sẽ đi đến trạng thái kết thúc (trong nhiều trường hợp đó là trạng thái ổn định, tức là sẽ không thay đổi khi tiếp tục tác động các phép biến đổi từ T ).2 Nguyên lí Dirichlet a) Nguyên lí Dirichlet Nguyên lí Dirichlet - còn gọi là nguyên lí chuồng chim bồ câu (The Pi- geonhole 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). Nguyên lí này được nhà toán học người Đức Johann Dirichlet phát biểu đầu tiên năm 1834 khi ông đề cập tới nó với tên gọi "nguyên lí ngăn kéo". Vì vậy, một tên gọi thông dụng khác của nguyên lý chuồng bồ câu chính là "nguyên lí ngăn kéo Dirichlet" hay đôi khi gọi gọn là "nguyên lí Dirichlet". Trong một số ngôn ngữ như tiếng Pháp, tiếng Ý và tiếng Đức, nguyên lí này cũng vẫn được gọi bằng tên "ngăn kéo" chứ không phải "chuồng bồ câu".

Nguyên lí Dirichlet cơ bản: LUAN VAN CHAT LUONG download : add [e-mail] 6 Nếu nhốt n + 1 con thỏ vào n cái chuồng thì bao giờ cũng có ít nhất một chuồng chứa ít nhất hai con thỏ, với n là số nguyên dương. 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 chứa ít hN i nhất đồ vật (ở đây kí hiệu [α] để chỉ phần nguyên của số α). hN i Giả sử mọi hộp đều chứa ít hơn vật. Khi đó tổng số đồ vật là: k h N i  hN i k −1 <k = N.

k k Điều này mâu thuẫn với giả thiết là có N đồ vật cần xếp. 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 hn + m − 1i nhất con thỏ. hn + m − 1i hn − 1i Giả sử trái lại mọi chuồng thỏ không có đến = +1 m h m n−1 i con, thì số thỏ trong mỗi chuồng đều nhỏ hơn hoặc bằng con.

hn − 1i m Từ đó suy ra tổng số con thỏ không vượt quá m. m Đ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.

b) Ứng dụng nguyên lí Dirichlet Nguyên lí Dirichlet là một công cụ rất hiệu quả dùng để chứng minh nhiều kết quả sâu sắc của toán học. Nó đặc biệt có nhiều áp dụng trong lĩnh vực khác nhau của toán học. Nguyên lí này trong nhiều trường hợp người ta dễ dàng chứng minh được sự tồn tại mà không đưa ra được phương pháp tìm được vật cụ thể, nhưng trong thực tế nhiều bài toán ta chỉ cần chỉ ra sự tồn tại là đủ rồi. Đôi khi có những bài toán người ta đã dùng rất nhiều phương pháp khác nhau để giải mà vẫn chưa đi đến được kết quả, nhưng nhờ nguyên lí Dirichlet mà bài toán trở nên dễ dàng giải quyết.

Để 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: LUAN VAN CHAT LUONG download : add [e-mail] 7 + Số "thỏ" phải hiề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 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 phép biến hình.3 Nguyên lí cực hạn a) Nguyên lý cực hạn Nguyên lí cực hạn được phát biểu đơn giản như sau: Nguyên lí 1: Trong một tập hữu hạn và khác rỗng các số thực luôn luôn có thể chọn được số bé nhất và số lớn nhất. Nguyên lí 2: Trong một tập khác rỗng các số tự nhiên luôn luôn có thể chọn được số bé nhất.

b) Ứng dụng nguyên lý cực hạn Sử dụng nguyên lí cực hạn là một phương pháp được vận dụng cho nhiều lớp bài toán khác, đặc biệt nó có ích khi giải các bài toán tổ hợp nói chung và hình học nói riêng. Trong quá trình tìm kiếm lời giải nhiều bài toán hình học, sẽ rất có lợi nếu chúng ta xem xét các phần tử biên, phần tử tới hạn (cực biên) nào đó, tức là phần tử mà tại đó mỗi đại lượng hình học có thể nhận giá trị lớn nhất hoặc giá trị nhỏ nhất, chẳng hạn như cạnh lớn nhất, cạnh nhỏ nhất của một tam giác, góc lớn nhất hoặc góc nhỏ nhất của một đa giác. Những tính chất của các phần tử biên, phần tử tới hạn nhiều khi giúp chúng ta tìm kiếm được lời giải thu gọn của bài toán. Nguyên lí cực hạn thường được sử dụng kết hợp với các phương pháp khác, đặc biệt là phương pháp phản chứng, được vận dụng trong trong trường hợp tập các giá trị cần khảo sát là tập hợp hữu hạn (nguyên lí 1) hoặc có thể có vô hạn nhưng tồn tại một phần tử lớn nhất hoặc nhỏ nhất (nguyên lí 2).

Khi vận dụng nguyên lí này, ta phải tiến hành các bước sau: Bước 1: Chứng minh rằng trong tất cả các giá trị cần khảo sát luôn tồn LUAN VAN CHAT LUONG download : add [e-mail] 8 tại giá trị lớn nhất hoặc giá trị nhỏ nhất. Bước 2: Xét bài toán trong trường hợp riêng khi nó nhận giá trị này (nhỏ nhất hoặc lớn nhất). Bước 3: Chỉ ra một mâu thuẫn, chỉ ra một giá trị còn nhỏ hơn (hay lớn hơn) giá trị ta đang khảo sát. Theo nguyên lí của phương pháp phản chứng, ta sẽ suy ra điều phải chứng minh.

LUAN VAN CHAT LUONG download : add [e-mail] 9 Chương 2 Phân loại và các phương pháp giải các bài toán đếm trong hình học tổ hợp 2.1 Phân loại các bài toán đếm 2.1 Đếm đối tượng tạo bởi điểm, đoạn thẳng, đường thẳng Bài toán 2. Một lưới tạo bởi m đường thẳng ngang và n đường thẳng đứng. Có bao nhiêu đỉnh phân biệt trong lưới này? Lời giải.