Nguyên lý dirichlet

Chia sẻ: ACB ABC | Ngày: | Loại File: DOC | Số trang:14

Thêm vào BST

Báo xấu

1.543
lượt xem 218
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Một số vấn đề liên quan đến nguyên lí dirichlet trong toán phổ thông

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Nguyên lý dirichlet

MỤC LỤC Chương Nội Dung Trang Vài nét về tiểu sử 1 Lời mở đầu 2 Chương I Đại cương về tổ hợp 4 Chương II Cơ sở lý thuyết nguyên lý Dirichlet II.1. Nguyên lý Dirichlet (Nguyên lý chim bồ câu) 4 II.2. Nguyên lý Dirichlet tổng quát 5 II.3. Nguyên lý Dirichlet đối ngẫu vô hạn phần tử 5 Chương III Bài tập ứng dụng III.1 Ứng dụng trong lý thuyết tổ hợp 6 III.2. Ứng dụng trong số học 8 III.3. Ứng dụng trong hình hoc 9 III.3.1.Baì toán về điểm và đường thẳng III.3.2. Bài toán về tô màu hình III.3.3. Bài toán về diện tích Kết luận 14 Tài liệu tham khảo 14 -1-
VÀI NÉT VỀ TIỂU SỬ Johann Peter Gustav Lejeune Dirichlet (13 tháng 2, 1805 – 5 tháng 5, 1859 ) là một nhà toán học người Đức được cho là người đưa ra định nghĩa hiện đại của hàm số. Gia đình ông xuất thân từ thị trấn Richelette ở Bỉ, do đó mà họ của ông là "Lejeune Dirichlet" ("le jeune de Richelette", tiếng Pháp nghĩa là "chàng trai trẻ từ Richelette") được đặt theo, và đó là nơi ông nội ông sống. Dirichlet được sinh ra ở Düren, nơi cha ông là một đứng đầu một trạm bưu điện. Ông được giáo dục ở Đức, và sau đó là Pháp, nơi ông học hỏi từ hầu hết các nhà toán học nổi tiếng nhất thời đó. Ông cũng học từ Georg Ohm. Bài báo đầu tiên của ông là về định lý Fermat bao gồm một phần của chứng minh cho trường hợp n = 5, được hoàn thiện bởi Adrien-Marie Legendre, một trong những người referees. Dirichlet cũng hoàn thiện chứng minh của ông trong cùng một thời gian; sau đó ông đã đưa ra toàn bộ lời giải cho trường hợp n = 14. Vào năm 1831, ông thành hôn với Rebecca Henriette Mendelssohn Bartholdy, một cô gái thuộc gia đình danh giá đã chuyển đổi từ đạo Do Thái sang Thiên chúa giáo; cô là cháu gái của triết gia Moses Mendelssohn, con gái của Abraham Mendelssohn Bartholdy và là em của nhà soạn nhạc Felix Mendelssohn Bartholdy và Fanny Mendelssohn. Ferdinand Eisenstein, Leopold Kronecker, và Rudolf Lipschitz là học trò của ông. Sau khi ông qua đời, các bài giảng của Dirichlet và các kết quả khác trong ngành số học được sưu tập, biên khảo và xuất bản bởi đồng nghiệp và cũng là bạn ông là nhà toán học Richard Dedekind dưới tựa đề Vorlesungen über Zahlentheorie (Các bài giảng về số học). -2-
LỜI MỞ ĐẦU Nguyên lí Dirichlet - còn gọi là nguyên lí chim bồ câu (The Pigeonhole Principle)-hoặc nguyên ý 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. Nguyên lí này được Dirichlet phát biểu đầu tiên năm 1834. 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. Nội dung của nguyên lí này hết sức đơn giản và dễ hiểu nhưng lại có tác dụng rất lớn, có nhiều hiệu quả bất ngờ trong giải toán. Sử dụng nó, chúng ta có thể chứng minh được nhiều kết quả sâu sắc của Toán học. Đô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. Nguyên lí Dirichlet có nhiều ứng dụng trong nhiều dạng bài tập của nhiều lĩnh vực khác nhau trong Toán học, tuy nhiên trong phạm vi đề tài này, chúng em chỉ tập trung khai thác “ứng dụng của nguyên lí Dirichlet trong các dạng bài tổ hợp , trong số học và hình học.” Các thành viên trong nhóm STT Họ tên học viên Công việc (Theo mục ) Ghi chú Nhận xét của Giáo Viên 1 Mai Xuân Kiên Chương II Chương III 2 Phạm Bình Chương I Nguyên Chương III 3 Lê Châu Vân Chương I Chương II 4 Đào Quang Hoà Lời mỡ đầu Chương III 5 Lê Thị Bích Huy Vài nét về tiểu sử Kết luận Tài liệu -3-
CHƯƠNG I: ĐẠI CƯƠNG V Ề TÔ HỢP Tổ hợp như là một lĩnh vực của toán học rời rạc, xuất hiện vào đầu thế kỷ 17. Hiện nay lý thuyết tổ hợp được áp dụng trong nhiều lĩnh vực khác nhau. Tổ hợp đụng chạm đến nhiều vấn đề khác nhau của toán học, do đó khó có thể định nghĩa nó một cách hình thức. Nói chung, lý thuyết tổ hợp gắn liền với việc nghiên cứu phân bố các phần tử vào các tập hợp. Thông thường, các phần tử này là hữu hạn và việc phân bố chúng phải thoả mãn những điều kiện nhất định nào đấy. Trong nhiều trường hợp việc xác định sự tồn tại một cấu hình thoả mãn tính chất nào đó cũng có ý nghĩa quan trọng về mặt lý thyết cũng nhực tế .Vì thế một bài toán tổ hợp là bài toán tồn tại: Xét sự tồn tại các cấu hình tổ hợp thoã mãn tính chất cho trước Bài toán tồn tại nghiên cứa từ rất lâu và góp phần đáng kể thúc đẩy sự phát triển của lý thuyết tổ hợp cũng như nhiều ngành toán học khác , các bài toán sau một phần nào minh hoạ về điều đó CHƯƠNG II: BÀI TOÁN NGUY ÊN LÝ DIRICHLET -CƠ SỞ LÍ THUYẾT- II.1. Nguyên lí Dirichlet – nguyên lí chim bồ câu II.1.1. Phát biểu nguyên lí • Nguyên lý Dirichlet :Nếu xếp nhiều hơn k đối tượng vào k cái hộp ( k ộ N* ) thì tồn tại hộp chứa ít nhất 2 đối tượng. Chứng minh Sử dụng phương pháp chứng minh phản chứng: Giả sử không có hộp nào chứa ít nhất 2 đối tượng thì số đối tượng không lớn hơn k. Điều này mâu thuẫn với giả thiết “ nhiều hơn k đối tượng “. Vậy nguyên lí đã được chứng minh. • Nguyên lí Dirichlet đối ngẫu. Cho tập hữu hạn S ≠ ∅ và S1, S2, …, Sn là các tập con của S sao cho | S1 | + | S2 | + … + | Sn | > k. | S |. Khi đó, tồn tại một phần tử x x S sao cho x là phần tử chung của k+ 1 tập Si ( i = 1, 2, … n). -4-
II.2. Nguyên lý Drichlet tổng quát Nếu xếp nhiều hơn m đối tượng vào n cái hộp ( n ,m ộ N* ) thì tồn tại hộp chứa ít nhất đối tượng ( ┐x┌ là số nguyên nhỏ nhất ≥ x). Chú thích: có tài liệu dùng 1 + [ ]với [x] là số nguyên lớn nhất nhỏ hơn hoặc bằng x. Chứng minh Sử dụng phương pháp chứng minh phản chứng: Giả sử không có hộp chứa ít nhất đối tượng thì số đối tượng không lớn hơn n. ( ) = m. Điều này mâu thuẫn với giả thiết số đối tượng nhiều hơn m. Vậy nguyên lí đã được chứng minh. II.3. Nguyên lý Dirichlet đối ngẫu vô hạn phần tử *Tập phần tử là một khoảng trên đường thẳng Trong mục này ta kí hiệu d(I) là độ dài của khoảng I ả R. • Định lý 1. Cho A là một khoảng giới nội, A 1, A2, … , An là các khoảng sao cho Ai i A (i = 1, 2, …, n) và d(A) < d(A1) + d(A2) + … + d(An). Khi đó ít nh ất có hai khoảng trong số các khoảng trên có một điểm trong chung. Chứng minh. Thật vậy, giả sử không có cặp nào trong những khoảng đã cho có điểm trong chung. Khi đó, d(A1 K A 2 … An) = d(A1) + d(A2) + … + d(An) > d(A). Mặt khác, từ Ai ừ A (i = 1, 2, …, n) suy ra d(A1 A 2 … An )≤ d(A). Các bất đẳng thức trên mâu thuẫn với nhau. Vậy ít nhất có hai khoảng trong số các khoảng trên có điểm trong chung. *Tập phần tử là miền phẳng giới hạn bởi một đường cong phẳng khép kín Trong mục này ta kí hiệu S(A) là diện tích miền A trong một mặt phẳng. Định lý 4. Nếu A là một miền giới hạn bởi một đường cong phẳng khép kín, còn A1, A2, … , An là các miền sao cho Ai A (i = 1, 2, …, n) và S(A) < S(A1) + S(A2) + … + S(An), thì ít nhất có hai miền trong số các miền nói trên có điểm trong chung. Chứng minh. Tương tự như chứng minh Định lí 1. -5-
CHƯƠNG III: BÀI TẬP ỨNG DỤNG Để 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’ thoả mãn các điều kiện : + 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. *Chú ý : Có nhiêù bài tập có kết luận “giống như” kết luận của nguyên lý Dirichlet, tuy nhiên, lời giải không hoàn toàn sử dụng nguyên lý Dirichlet III.1. Ứng dụng trong lí thuyết tổ hợp Áp dụng nguyên lí Dirichlet vào lí thuyết tổ hợp, còn gọi là lí thuyết Ramsey, tên của nhà Toán học người Anh. Lí thuyết Ramsey giải quyết những bài toán phân chia các tập con của một tập các phần tử. Bài toán sau đây là một ví dụ: Bài toán 1: Chọn 5 người bất kì chứng minh rằng có ít nhất có hai người có cùng số người quen. Giải: Ta chia 5 người thành i nhóm . 0 ≤ i ≤ 4 (i là số ngưòi quen) ta chia thành hai trường hợp +TH1: Có 1 người không quên ai hết khi đó 0 ≤ i ≤ 3.vậy theo nguyên lý Dirchlet tồn tại nhóm có ít nhất hai người quen nhau +TH2: Ai Cũng có người quen khi đó 1 ≤ i ≤ 4.vậy theo nguyên lý Dirchlet tồn tại nhóm có ít nhất hai người quen nhau Ta có thể tổng quát bài toán này như sau: Bài toán 2: Trong cuộc họp có n người bao giờ cũng có 2 người có số người quen bằng nhau. Giải: Ta chia người thành i nhóm . 0 ≤ i ≤ n-1 (i là số ngưòi quen) ta chia thành hai trường hợp +TH1: Có 1 người không quên ai hết khi đó 0 ≤ i ≤ n-2.vậy theo nguyên lý Dirchlet tồn tại nhóm có ít nhất hai người quen nhau +TH2: Ai Cũng có người quen khi đó 1 ≤ i ≤ n-1.vậy theo nguyên lý Dirchlet tồn tại nhóm có ít nhất hai người quen nhau -6-
Bài toán 3: Giả sử trong một nhóm 6 người mỗi cặp 2 hoặc là bạn hoặc là thù. Chứng tỏ rằng trong nhóm có 3 người là bạn lẫn nhau hoặc có 3 người là kẻ thù lẫn nhau. Giải: Gọi A một trong 6 người Trong số 5 người của nhóm hoặc là có ít nhất 3 người là bạn của A hoặc có ít nhất 5 3 người là kẻ thù của A, điều này suy ra từ nguyên lí Dirichlet tổng quát vì ┐2 ┌ =3 Trong trường hợp đầu ta gọi B, C, D là bạn của A Nếu trong 3 người này có 2 người là bạn thì họ cùng với A lập thành một bộ 3 người bạn của nhau ( không ai là kẻ thù của ai cả ), ngược lại, tức là nếu trong 3 người B, C, D không có ai là bạn ai cả thì chứng tỏ họ là bộ ba người thù lẫn nhau Tương tự như trên ta có thể chứng minh trong trường hợp có ít nhất 3 người là kẻ thù của A. Bài toán 4:Chứng minh rằng nếu f là một hàm từ X vào Y, trong đó X và Y là các tập hữu hạn và m = ┐ | X|/|Y| ┌ khi đó có ít nhất m phần tử của X được gán với cùng một giá trị của Y. Điều này có nghĩa là có m phần tử Giải: Xem hàm f từ X vào Y là một quy tắc sắp xếp X vật f(x) với x Є X vào Y cái hộp, mỗi hộp 1 vật. Áp dụng nguyên lí Dirichlet tổng quát ta suy ra điều phải chứng minh *Ta có một số các bài toán : Bài toán 5:Chứng minh rằng trong 1 nhóm có 10 người (trong đó có 2 người bất kì là bạn hoặc là thù) luôn có nhóm 3 người là bạn hoặc 4 người là kẻ thù lẫn nhau và có nhóm 3 người là kẻ thù hoặc 4 người là bạn của nhau. Bài toán 6:Trong một giải vô địch bóng đá có 11 đội tham gia . hai đội bất kì phải thi đấu với nhau cùng một trận . chứng minh rằng tại một thời diẻm của giải luôn có hai đội có cùng số trận đấu bằng nhau -7-
III.2. Ứng dụng trong số học Các bài toán số học thường khó khăn trong việc tìm lời giải ,Tuy nhiên có một số lượng bài không nhỏ sử dụng nguyên lý Dirichlet để giải quyết rất hiệu quả , mà trình bày tương đối đơn giản mà dễ hiểu . Sau đây là một số ví dụ điển hình Bài toán 1:Chứng minh rằng trong số bất kì thuộc tập hợp luôn chọn được hai số mà số này là bội của số kia. Giải: Viết số đã cho dưới dạng: Trong đó b1,b2,……bn+1 là các số lẻ. Ta có 1≤ b1,b2,……bn+1 ≤ 2n-1 Mặt khác trong khoảng từ 1 đến có đúng n số lẻ nên tồn tại hai số . Khi đó, trong hai số và có một số là bội của số kia Baì toán 3: Cho a1,a2…………..,an l à c ác s ố nguy ên kh ác nhau trong khoảng [100;200] thoả điều kiện a1+a2+…………..+an ≥ 11100 Ch ứng minh r ằng các số này có ít nhất âôjt số mà nó viết dưới dạng thập phân cos ít nhất hai chữ số giống nhau Giải Chúng ta lập danh sách các số trong khoảng [100;200] ,mà chúng viết ở hệ thập phân ít nhất có hai chữ số trùng nhau 100, 101, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 121, 131, 141, 151, 161, 171, 181, 191, 199, 200. Tổng của tất cả các số nói trên là 4050 . Mặt khác tổng của tất cả các số nguyên trong khoảng [100;200] là 15150 . Nếu trong những số đã cho a 1,a2…………..,an không có số nào trong danh sách trên thì a1+a2+…………..+an ≤ 15150-4050=11100 điều này vô lý .Nghĩa là trong các số a1,a2…………..,an c ó ít nhất một số mà viết nó dưới dạng thập phân có ít nhất hai chữ số giống nhau -8-
Bài toán 4: Chứng minh rằng từ tập hợp tuỳ ý gồm n số tự nhiên luôn tách ra được một tập hợp con (khác rỗng ) chứa các số mà tổng của chúng chia hết cho n Giải : Gỉa sử một tập nào đó mà chứa các số từ a1,a2,…..,an. mà không thoả mãn khẳng định của bài toán .Khi đó không có số nào trong các số : S1=a1,S2= a1+a2; …………,Sn= a1+a2+………+an.mà chia hết cho n. Và các số dư khác không trong phép chia cho n là n-1, nên theo nguyên lý Dirichlet ta tìm được hai số S i và Sj (1 ≤ i ≤ j ≤ n) có cùng số dư. Suy ra hiệu của Si − Sj chia hết cho n Điều này mâu thuẩn với gỉa sử nói trên, vậy được điều phải chứng minh Ta có các bài toán sau: Bài toán 5.Chứng minh rằng 52 số tụ nhiên bất kì sao cho hoặc tổng hoặc hiệu của hai số đó chia hết co 100. Kết luận còn đúng kông với 51 số Bài toán 6.Chứng minh rằng từ 12 số tự nhiên bất kì luôn chon được hai số có hiệu chia hết cho 11 Bài toán 7. Viết n số tự nhiên thành một hàng ngang .Chứng minh rằng có một số chia hết cho n hoặc có một số số liên tiếp chia hết cho n III.3. Ứng dụng trong hình học (Nguyên lý Dirichlet vô han) Nếu chia một tập hợp vô hạn các quả táo vào hưu hạn các ngăn kéo thì có ít nhất một ngăn kéo có vô hạn các quả táo III.3.1. Bài toán về các điểm, các đường thẳng Bài toán1: Trong hình vuông cạnh bằng 1 , đặt 51 điểm bất kì , phân biệt . Chứng 1 minh rằng có ít nhất 3 trong số 51 điểm đó nằm trong một hình tròn bán kính 7 Giải : 1 Chia hình vuông đã cho thành 25 hình vuông con bằng nhau có cạnh bằng .Theo 5 nguyên lý Dirichlet ,tồn tại ít nhất một hình vuông con (a) chứa ít nhất điểm trong 1 1 số 51 điểm đó . Đường tròn ngoại tiếp (a) có bá kính 5 .Vậy ba điểm nói trên 5 2 7 1 nằm trong hình tròn đồng tâm với đường tròn (a) có bán kính 7 -9-
Bài toán 2:Cho ( xi,yi,zi), i = 1, 2, 3, 4, 5, 6, 7, 8, 9 là một tập hợp gồm 9 điểm khác nhau có các tọa độ nguyên trong không gian. Chứng minh rằng trung điểm của đường nối ít nhất một trong các cặp điểm này có tọa độ nguyên. Giải: Gọi tọa độ hai điểm bất kì trong không gian là A (a, b, c) và B (d, e, f) Vậy trung điểm của đoạn AB là O( , , ) Các tọa độ của điểm O nguyên nếu và chỉ nếu a và d; b và e; c và f cùng chẵn hoặc cùng lẻ Vì có 23 = 8 bộ ba chẵn lẻ khác nhau (( c, c, c ); (l, l, l ); ( c, c, l ); ( c, l, l ); (c, l, c ); ( l, c, c ); ( l, c, l ); ( l, l, c )) nên theo nguyên lí Dirichlet có ít nhất 2 trong 9 điểm có cùng bộ ba chẵn lẻ như nhau. Vậy có ít nhất một cặp điểm mà điểm chính giữa của chúng có tọa độ nguyên. • Bài toán 3: Trong một hình vuông có cạnh là 1 chứa một số đường tròn. Tổng tất cả chu vi của chúng là 10. Chứng minh rằng tồn tại một đường thẳng cắt ít nhất 4 đường tròn trong những đường tròn đó? Giải. Ta chọn một cạnh hình vuông rồi chiếu vuông góc các đư ờng tròn xuống cạnh đó (xem hình 1). Ta có, hình chi ếu của một đường tròn bán kính R xuống AB là một đoạn thẳng có độ dài 2R. Vì vậy trên cạnh hình vuông đã chọn 10 10 có những đoạn thẳng chiếu xuống với tổng độ dài là Mà > 3. Nên theo π π nguyên lý Dirichlet đối ngẫu (Định lí 3) suy ra có một điểm M nào đó thuộc AB là điểm trong chung c ủa ít nhất 4 đoạn thẳng đã c hiếu xuống. Khi đó, đường thẳng đi qua M vuông góc với AB cắt ít nhất 4 trong những đường tròn đó. Bài toán 4:Cho một hình vuông và 13 đường thẳng, mỗi đường thẳng đều chia hình vuông thành hai tứ giác có tỉ số diện tích 2 : 3.Chứng minh rằng trong số 13 đường thẳng đã cho, có ít nhất 4 đường thẳng cùng đi qua một điểm. Giải: A M B d E F I - 10 -
D N C Gọi d là đường thẳng chia hình vuông ABCD thành hai tứ giác có tỉ số diện tích là 2 : 3 Đường thẳng d không thể cắt hai cạnh kề nhau của hình vuông Giả sử d cắt hai cạnh AB và CD tại M và N, khi đó nó cắt đường trung bình EF tại I Giả sử thì Như vậy mỗi đường thẳng đã cho chia các đường trung bình của hình vuông theo tỉ số 2 : 3 Có 4 điểm chia các đường trung bình của hình vuông theo tỉ số 2 : 3 Có 13 đường thẳng, mỗi đường thẳng đi qua một trong 4 điểm Vậy theo nguyên lý Dirichlet có ít nhất 4 đường thẳng cùng đi qua 1 điểm. Bài toán 5: Bên trong tam giác đều ABC cạnh 1 đặt 5 điểm.Chứng minh rằng tồn tại 2 điểm có khoảng cách nhỏ hơn 0,5 Giải: 0,5 0,5 0,5 0,5 0,5 0,5 Các đường trung bình của tam giác đều cạnh 1 sẽ chia nó ra làm 4 tam giác đều cạnh 0,5 Do đó trong một tam giác nhỏ đó có ít nhất 2 điểm đã cho, và các điểm đó không thể rơi vào các đỉnh của tam giác .Vậy khoảng cách giữa hai điểm đó nhỏ hơn 0,5 Ta có một số bài toán sau: Bài toán 6. Trong một hình vuông đơn vị chọn tuỳ ý 101 điểm (có thể thuộc cạnh cuả hình vuông ) sao cho không có ba điểm nào thẳng hang . Chứng minh rằng tồn tại tam giác với ba đỉnh là các điểm được chọn và có diẹn tích nhỏ hơn 0,01 - 11 -
Bài toán 7. Cho 5 điểm trên mặt phẳng có toạ độ nguyên . Chứng minh rằng tồn tại hai điểm có trung độ nguyên III.3.3. Bài toán về tô màu hình vẽ Bài toán 1: Giả sử mỗi điểm trong mặt phẳng được tô bằng một trong 2 màu đỏ và xanh. Ch ứng minh t ồn t ại m ột h ình ch ữ nh ật c ó c ác đ ỉnh c ùg m àu Giải : Giả sử ta có một lưới ô vuông tạo bởi 3 đường nằm ngang và 9 đường thẳng đứng , mỗi nút lưới được tô bởi một màu xanh hoặc đỏ. A X B Y C Z Xét 3 nút lưới của một đường dọc , mỗi nút có hai cách tô m àu nên mỗi bộ ba nút trên đường dọc ấy có cách tô màu Có 9 đường dọc, mỗi đường có 8 cách tô màu nên theo nguyên lý Dirichlet tồn tại hai đường có cách tô màu như nhau .Chẳng hạn hai bộ ba điểm đó là A, B, C và X, Y, Z Vì 3 điểm A, B, C chỉ được tô bởi hai màu nên tồn tại hai điểm cùng màu , chẳng hạn B và C khi đó hình chữ nhật BYZC có 4 đỉnh cùng một màu Ta có các bài toán sau: Bai toán 2: Một số cung tròn của một đường tròn được tô màu đen , các cung còn lại được tô màu đỏ . Biết rằng tổng độ dài các cung màu đen nhỏ hơn nữa chu vi của đường tròn . Chứng minh rằng có thể kẻ đựoc một đường kính của đường tròn với hai đầu mút được tô màu đỏ B ài toán 3: Cho bàn cờ kích thước 3 x 7 với các ô được tô màu xanh hoặc đỏ . Chứng minh rằng bàn cờ chứa hình chữ nhât không tầm thường (tức không có cạnh bằng 1) sao cho các ô ở bốn góc cùng màu. III.3.4. Bài toán diện tích Bài toán 1. Cho 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 ba điểm tạo thành một tam giác có diện tích bé hơn 1 - 12 -
Giải: Chia hình tròn thành (C) thành 8 hình quạt bằng nhau , mỗi hình quat có diện tích bằng 1 .Theo nguyên lý Dirichlet ,tồn tại ít nhất một hình quạt (a) chứa 3 điểm trong số 17điểm đã cho .Tam giác có 3 đỉnh là 3 điểm đó nằm tron trong hình quạt (a) nên có diện tích nhỏ hơn diện tích hình quạt ,tức là bé hơn 1 Bài toán 2:.Trong hình vuông cạnh 15 đặt 20 hình vuông nhỏ cạnh 1 từng đôi một không cắt nhau.Chứng minh rằng trong hình vuông lớn có thể đặt một hình tròn bán kính 1 sao cho nó không cắt hình vuông nào. Giải: Xét hình gồm tất cả các điểm cách hình vuông nhỏ cạnh 1 một khoảng không lớn hơn 1 Rõ ràng hình tròn bán kính 1 có tâm nằm ngoài hình đó nên không thể cắt hình vuông nhỏ Diện tích hình đó bằng 5+п Tâm hình tròn cần tìm cũng cần phải cách các cạnh của hình vuông lớn hơn một khoảng lớn hơn 1, tức là ở bên trong hình vuông cạnh 13 Vì 20(5+п) < 132 Hình tròn có tâm tại điểm không bị phủ sẽ có tính chất thỏa mãn đề bài. *Ta có các bài toán sau: Bài toán 3. Cho một tờ giấy kẻ caro vô tận và một hình có diện tích nhỏ hơn diện tích một ô giấy. Chứng minh rằng hình đó có thể đặt trên giấy để nó không che một đỉnh ô nào. Bài toán 4. Cho hình đa giác đều 9 cạnh, mỗi đỉnh của nó được tô hai màu trắng hoặc đen Chứng minh rằng tồn tại hai tam giác phân biệt có diện ích bằng nhau ,mà các đỉnh của mỗi tam giác được tô cùng màu - 13 -
KẾT LUẬN Trên đây chỉ xét ba ứng dụng tiêu biểu của nguyên lí Dirichlet. Xin chân thành cảm ơn PGS.TSKH Trần Quốc Chiến đã tận tình hướng dẫn và cảm ơn các anh chị em trong lớp Cao học Phương pháp Toán sơ cấp khoá 2009 – 2011 đã giúp đỡ chúng tôi trong việc sưu tầm tài liệu tham khảo để hoàn thành tiểu luận này. Trong quá trình nghiên cứu sẽ không tránh khỏi những thiếu sót, rất mong nhận được nhiều những ý kiến đóng góp quý báu để tiểu luận được hoàn thiện hơn. TÀI LIỆU THAM KHẢO [1] Giáo trình Lí thuyết tổ hợp – PGS.TSKH Trần Quốc Chiến [2] Chuyên đề chọn lọc Tổ hợp và toán rời rạc – GS.TSKHNguyễn Văn Mậu [3] Bài báo về nguyên lí Dirichlet – Trương công nên [4] Bài báo về nguyên lí Dirichlet – Nguyễn Văn Linh - 14 -