Tài liệu Skkn nguyên lí cực hạn trong các bài toán tổ hợp

BM 01-Bia SKKN SỞ GIÁO DỤC VÀ ĐÀO TẠO ĐỒNG NAI Đơn vị THPT chuyên Lương Thế Vinh Mã số: ................................ (Do HĐKH Sở GD&ĐT ghi) SÁNG KIẾN KINH NGHIỆM NGUYÊN LÍ CỰC HẠN TRONG CÁC BÀI TOÁN TỔ HỢP Người thực hiện: Phạm Doãn Lê Bình Lĩnh vực nghiên cứu: - Quản lý giáo dục  - Phương pháp dạy học bộ môn: Toán  - Lĩnh vực khác: .......................................................  Có đính kèm: Các sản phẩm không thề hiện trong bản in SKKN  Mô hình  Phần mềm  Phim ảnh  Hiện vật khác Năm học: 2016 - 2017 BM02-LLKHSKKN SƠ LƯỢC LÝ LỊCH KHOA HỌC I. THÔNG TIN CHUNG VỀ CÁ NHÂN 1. Họ và tên: Phạm Doãn Lê Bình 2. Ngày tháng năm sinh: 23/04/1986 3. Nam, nữ: Nam 4. Địa chỉ: 1123, KP7, P. Long Bình, TP. Biên Hòa, Đồng Nai 5. Điện thoại: 0613930245 (nhà riêng) ; ĐTDĐ: 01683531100 6. Fax: E-mail: [email protected] 7. Chức vụ: Giáo viên 8. Đơn vị công tác: Trường THPT chuyên Lương Thế Vinh. II. TRÌNH ĐỘ ĐÀO TẠO - Học vị (hoặc trình độ chuyên môn, nghiệp vụ) cao nhất: Thạc sĩ - Năm nhận bằng: 2012 - Chuyên ngành đào tạo: Đại số và lý thuyết số III. KINH NGHIỆM KHOA HỌC - Lĩnh vực chuyên môn có kinh nghiệm: Sư phạm Toán Số năm có kinh nghiệm: 9 - Các sáng kiến kinh nghiệm đã có trong 5 năm gần đây: + Phương pháp đại lượng bất biến, đơn biến trong các bài toán tổ hợp. (2014) + Các bài toán tổ hợp trong các kỳ thi học sinh giỏi (2016) NGUYÊN LÍ CỰC HẠN TRONG CÁC BÀI TOÁN TỔ HỢP Phạm Doãn Lê Bình Giáo viên trường THPT chuyên Lương Thế Vinh Tháng 4 năm 2017 Mục lục 1 Lý do chọn đề tài 2 2 Nội 2.1 2.2 2.3 2 2 2 9 dung đề tài Nêu vấn đề . . . . . . . . . . . . . . . . . . . . . . . . . . . . Một số ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . Bài tập tự luyện . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Hiệu quả của đề tài 10 4 Tài liệu tham khảo 11 Trang 1 1 Lý do chọn đề tài Nguyên lí cực hạn là một nguyên lí đơn giản và dễ hiểu nhưng nếu vận dụng khéo léo sẽ giúp chúng ta giải quyết được nhiều lớp bài toán, đặc biệt là các bài toán tổ hợp. 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. Nó giúp chúng ta giải quyết các bài toán mà trong tập hợp những đối tượng phải xét của nó tồn tại các đối tượng có giá trị lớn nhất, giá trị nhỏ nhất theo một nghĩa nào đó. Nguyên lí cực hạn tuy dễ hiểu nhưng để vận dụng nó vào các bài toán thì lại không phải đơn giản. Với lí do đó, tôi chọn đề tài này để làm tài liệu giảng dạy cho giáo viên và tài liệu học tập cho học sinh trong quá trình tiếp cận các bài toán tổ hợp. 2 Nội dung đề tài 2.1 Nêu vấn đề 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 hợp khác rỗng các số tự nhiên luôn luôn có thể chọn được số bé nhất. Để vận dụng các nguyên lí cực hạn giải các bài toán tổ hợp, người ta thường dùng một lược đồ chung để giải như sau: • Đưa bài toán đang xét về dạng có thể sử dụng nguyên lí 1 (hoặc nguyên lí 2) để chứng tỏ rằng trong tất cả các giá trị cần khảo sát của bài toán phải có giá trị lớn nhất (hoặc nhỏ nhất). • Xét bài toán tương ứng khi nó nhận giá trị lớn nhất (hoặc nhỏ nhất) này. • Chỉ ra một mâu thuẫn, hoặc đưa ra một giá trị còn lớn hơn (hoặc nhỏ hơn) giá trị lớn nhất (hoặc nhỏ nhất) mà 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. Ta xét một số ví dụ sau: 2.2 Một số ví dụ Ví dụ 1. 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 một số nguyên tố. Trang 2 Lời giải. Giả sử tìm được 15 số lấy từ {2; 3; . . . ; 1992} sao cho chúng đều là hợp số và đôi một nguyên tố cùng nhau. Khi đó mỗi một số này đều phải có √ ước số nguyên tố nhỏ hơn 45 ( 1992 < 45). Vì chỉ có 14 số nguyên tố nhỏ hơn 45 nên phải tồn tại ít nhất 2 trong 15 số trên có cùng ước số nguyên tố. Nhưng khi đó chúng không nguyên tố cùng nhau, mâu thuẫn. Vậy điều giả sử là sai, tức là tồn tại một trong 15 số đã cho là số nguyên tố. Ví dụ 2. Chứng minh rằng bốn hình tròn có đường kính là bốn cạnh của một tứ giác lồi thì phủ kín tứ giác đã cho. Lời giải. Lấy M là một điểm tùy ý của tứ giác lồi ABCD. Có hai khả năng xảy ra: 1. Nếu M nằm trên một cạnh của tứ giác ABCD. Khi đó M nằm trong hình tròn có đường kính là cạnh ấy. 2. Nếu M nằm bên trong tứ giác lồi ABCD. Khi đó ta có AM B + BM C + CM D + DM A = 360◦ . Theo nguyên lý cực hạn, tồn tại α = max{AM B, BM C, CM D, DM A}. Khi ấy, α ≥ 90◦ . Không mất tính tổng quát, giả sử α = AM B. Suy ra M nằm trong hình tròn đường kính AB. Vậy M bị phủ bởi hình tròn này. Như thế, do M là điểm bất kỳ của tứ giác ABCD và M luôn thuộc một hình tròn nào đó có đường kính là một cạnh của tứ giác ABCD nên tứ giác ABCD sẽ bị phủ kín bởi 4 hình tròn có đường kính là bốn cạnh. Ví dụ 3. Trên mặt phẳng vô hạn được kẻ ô vuông, người ta điền các số tự nhiên vào các ô vuông sao cho mỗi số tùy ý luôn bằng trung bình cộng của bốn số tự nhiên trong bốn ô vuông có cạnh chung với ô vuông chứa nó. Chứng minh rằng khi đó tất cả các số được điền đều bằng nhau. Lời giải. Xét tập hợp các số được điền. Đây là tập hợp các số tự nhiên khác rỗng, nên theo nguyên lí cực hạn phải tồn tại phần tử nhỏ nhất mà ta kí hiệu là a. Trang 3 Giả sử kết luận của bài toán không đúng, tức là các số được điền không phải tất cả đều bằng nhau. Như vậy sẽ có một ô chứa số a mà trong bốn ô cạnh chung với nó sẽ có ít nhất một số b = a. Giả sử ba ô còn lại có cạnh chung với ô chứa số a này là c, d, e. Theo cách xác định số a, ta có: b > a, c ≥ a, d ≥ a, e ≥ a. Từ đó suy ra a< b+c+d+e . 4 Điều này mâu thuẫn với giả thiết a là trung bình cộng của b, c, d, e. Vậy giả thiết phản chứng là sai, tức là tất cả các số viết trong bảng đều bằng nhau. Ví dụ 4. Cho n điểm xanh và n điểm đỏ trên mặt phẳng, trong đó không có 3 điểm nào thẳng hàng. Chứng minh rằng ta có thể nối 2n điểm này bằng n đoạn thẳng có đầu mút khác màu sao cho chúng đôi một không giao nhau. Lời giải. Với mỗi cách nối 2n điểm bằng n đoạn thẳng xanh-đỏ, ta tính tổng độ dài các đoạn thẳng được nối. Do số cách nối là hữu hạn nên tồn tại cách nối có tổng độ dài nói trên là nhỏ nhất. Ta chứng minh rằng cách nối này thỏa mãn yêu cầu bài toán. Giả sử ngược lại, tồn tại hai đoạn thẳng cắt nhau, giả sử đó là AB và CD cắt nhau tại O (A, C được tô màu đỏ, còn B, D được tô màu xanh). Áp dụng bất đẳng thức tam giác, ta có AD < OA + OD và BC < OB + OC. Suy ra AD + BC < AB + CD. Như vậy, nếu ta giữ nguyên n − 2 đoạn nối còn lại và thay AB, CD bằng AD, BC thì tổng các đoạn nối của cách nối mới nhỏ hơn cách nối cũ. Mâu thuẫn với tính nhỏ nhất. Vậy tồn tại cách nối 2n điểm bằng n đoạn thẳng xanh-đỏ sao cho chúng không cắt nhau. Ví dụ 5. Tập hợp S các sinh viên của một trường đại học có tính chất: bất kì hai sinh viên có cùng số người quen trong S thì không có người quen chung trong S. Chứng minh rằng tồn tại sinh viên chỉ có đúng một người quen trong S. Trang 4 Lời giải. Do tập hợp S có hữu hạn sinh viên nên tồn tại một sinh viên quen với nhiều người nhất. Gọi sinh viên đó là A và Ai (i = 1, . . . , n) là những sinh viên người đó quen. Do các sinh viên Ai cùng quen A nên số người quen của họ không bằng nhau và không lớn hơn n. Do đó số người quen của các sinh viên này lần lượt là 1, 2, . . . , n. Vậy tồn tại một sinh viên chỉ quen với đúng 1 người. Ví dụ 6. Có 3 trường học, mỗi trường học có n học sinh. Mỗi học sinh quen với ít nhất n + 1 học sinh từ hai trường khác. Chứng minh rằng người ta có thể chọn ra từ mỗi trường một bạn sao cho ba học sinh được chọn đôi một quen nhau. Lời giải. Gọi A là học sinh có nhiều bạn nhất ở một trường khác. Gọi số bạn là k. Giả sử A ở trường 1 và những bạn quen A là B1 , B2 , . . . , Bk ở n+1 . Cũng theo giả thiết, có ít nhất 1 học sinh C ở trường 2. Ta có k ≥ 2 trường 3 quen với A. Giả sử C không quen với Bi với mọi i = 1, 2, . . . , k thì C quen với nhiều nhất n − k học sinh của trường 2. Suy ra C quen với ít nhất n + 1 − (n − k) = k + 1 học sinh ở trường 1, điều này mâu thuẫn với cách chọn A. Vậy C phải quen với một bạn Bi nào đó. Khi đó A, Bi và C chính là 3 học sinh cần tìm. Ví dụ 7. Một nước có 100 sân bay, mà khoảng cách giữa hai sân bay nào cũng khác nhau. Mỗi máy bay cất cánh từ một sân bay và bay đến sân bay nào gần nhất. Chứng minh rằng không có sân bay nào có quá 5 chuyến bay đến. Lời giải. Giả sử tồn tại một sân bay có hơn 5 chuyến bay đến. Gọi O là sân bay đó và Ai (i ∈ {1, . . . , 6}) là một trong các sân bay bay đến O. Không mất tính tổng quát, ta có thể giả sử thứ tự các sân bay này duyệt theo chiều kim đồng hồ từ A1 là A1 A2 A3 A4 A5 A6 . 6 Ai OAi+1 = 360◦ nên tồn tại i để Ai OAi+1 ≤ 60◦ (xem A7 ≡ A1 ). Khi đó i=1 Do đó, một trong hai góc còn lại của tam giác Ai OAi+1 lớn hơn 60◦ (do các khoảng cách không bằng nhau) ⇒ Ai Ai+1 < max{OAi , OAi+1 }, mâu thuẫn với giả thiết (vì nếu Ai Ai+1 < OAi thì sân bay Ai có chuyến bay đến Ai+1 chứ không phải đến O). • Chú ý: Con số 100 trong đề bài thực ra không có tác dụng gì ngoài việc cho thấy là có thể có khả năng một sân bay có hơn 5 chuyến bay đến (cần ít nhất là 7 sân bay để có thể có điều đó). Ta có thể thay nó bằng 1 con số khác lớn hơn hoặc bằng 7 và cách giải quyết bài toán này cũng như vậy. Ví dụ 8. (Định lí Sylvester) Cho tập hợp S gồm hữu hạn các điểm trên mặt phẳng thỏa mãn tính chất sau: Một đường thẳng đi qua hai điểm thuộc S đều đi qua ít nhất một điểm khác thuộc S. Khi đó tất cả các điểm của S nằm trên một đường thẳng. Trang 5 Lời giải. Giả sử phản chứng là tồn tại một tập hợp S gồm hữu hạn điểm không thẳng hàng nhưng mọi đường thẳng qua hai điểm trong S đều chứa ít nhất ba điểm thuộc S. Xét tập hợp A = {h|h > 0 và h là khoảng cách từ một điểm thuộc S đến một đường thẳng đi qua hai điểm thuộc S}. Do giả thiết phản chứng nên A = ∅ và A là tập hợp có hữu hạn phần tử. Theo nguyên lí cực hạn thì A có phần tử nhỏ nhất h◦ . Giả sử h◦ M là khoảng cách từ M đến đường thẳng đi qua E B, C (M, B, C ∈ S). Theo giả thiết phản chứng thì tồn tại D ∈ S và D nằm trên đường thẳng F BC. Kẻ M H⊥BC thì M H = h◦ . Rõ ràng trong 3 điểm B, C, D thì theo nguyên lí Dirichlet phải có ít nhất 2 điểm nằm cùng phía so với H trên B H C D đường thẳng BC. Giả sử C nằm giữa H và D. Kẻ HE và CF vuông góc với MD. Rõ ràng ta có CF < HE < M H. Mà CF ∈ A và CF < h◦ nên giả thiết phản chứng bị sai, tức là tất cả các điểm thuộc S thẳng hàng với nhau. Ví dụ 9. Trong một cuộc thi Toán có 65 học sinh tham gia đến từ hai trường. Mỗi học sinh thi một trong 4 môn Toán, Lí, Hoá, Anh Văn. Biết rằng trong 5 học sinh thi cùng một môn thì có hai học sinh cùng tuổi. Chứng minh rằng trong 65 học sinh có ít nhất 3 học sinh đến từ một trường, thi cùng một môn và bằng tuổi nhau. Lời giải. Giả sử không có 3 học sinh nào thoả yêu cầu bài toán. Vì có 65 học sinh đến từ hai trường nên có ít nhất 33 học sinh đến từ một trường. Xét 33 học này thì có ít nhất 9 học sinh thi cùng một môn. Ta xét 9 học sinh này: Lấy 5 học sinh bất kì trong 9 học sinh trên. Khi đó sẽ có hai học sinh cùng tuổi, ta giả sử đó là hai học sinh A1 , B1 . Ta loại hai học sinh này còn lại 7 trong học sinh và trong 7 học sinh nay ta tìm được hai học sinh cùng tuổi A2 , B2 . Sau khi loại hai học sinh này ta còn lại 5 học sinh và tiếp tục chọn được 2 học sinh A3 , B3 . Xét 3 học sinh A1 , A2 , A3 ta có tuổi của ba học sinh này đôi một khác nhau. Xét 5 học sinh gồm ba học sinh A1 , A2 , A3 với 2 trong ba học sinh còn lại, khi đó hai học sinh còn lại ta kí hiệu A4 , B4 cùng tuổi nhau. Xét 5 học sinh gồm 4 học sinh A1 , A2 , A3 , A4 và học sinh còn lại (ta kí hiệu là A5 ). Khi đó A5 sẽ cùng tuổi với 1 trong 4 học sinh A1 , A2 , A3 , A4 . Chẳng hạn A5 , A1 cùng tuổi. Khi đó A1 , B1 , A5 thoả yêu cầu bài toán . Điều này mâu thuẫn với điều giả sử ở trên. Vậy bài toán được chứng minh. Ví dụ 10. (Trận đấu toán học Nga 2010) Một quốc gia có 210 thành phố. Ban đầu giữa các thành phố chưa có đường. Người ta muốn xây dựng một số con đường một chiều nối giữa các thành phố sao cho: Nếu có đường Trang 6 đi từ A đến B và từ B đến C thì không có con đường đi từ A đến C. Hỏi có thể xây dựng được nhiều nhất bao nhiêu đường? Lời giải. Gọi A là thành phố có nhiều đường đi nhất (gồm cả đường đi xuất phát từ A và đường đi đến A). Ta chia các thành phố còn lại thành 3 loại. • Loại I - có đường đi xuất phát từ A. • Loại II - có đường đi đến A. • Loại III - không có đường đi đến A hoặc xuất phát từ A. Đặt m = |I|, n = |II|, p = |III|. Ta có m + n + p = 209. Dễ thấy giữa các thành phố loại I không có đường đi. Tương tự, giữa các thành phố loại II không có đường đi. Số các đường đi liên quan đến các thành phố loại III không vượt quá p(m+n) (Do bậc của A = m + n là lớn nhất). Tổng số đường đi bao gồm: • Các đường đi liên quan đến A: m + n. • Các đường đi liên quan đến III: ≤ p(m + n). • Các đường đi giữa I và II: ≤ mn. Suy ra tổng số đường đi nhỏ hơn 2102 (m + n + p + 1)2 = . mn + (p + 1)m + (p + 1)n ≤ 3 3 Dấu bằng xảy ra với đồ thị 3 phe, mỗi phe có 70 thành phố, thành phố phe 1 có đường đi đến thành phố phe 2, thành phố phe 2 có đường đi đến thành phố phe 3, thành phố phe 3 có đường đi đến thành phố phe 1. Ví dụ 11. Trong quốc hội Mỹ, mỗi một nghị sĩ có không quá 3 kẻ thù. Chứng minh rằng có thể chia quốc hội thành 2 viện sao cho trong mỗi viện, mỗi một nghị sĩ có không quá một kẻ thù. Lời giải. Ta chia quốc hội ra thành 2 viện A, B một cách bất kỳ. Với mỗi viện A, B, ta gọi s(A), s(B) là tổng của tổng số các kẻ thù của mỗi thành viên tính trong viện đó. Vì số cách chia là hữu hạn nên phải tồn tại cách chia (A0 , B0 ) sao cho s(Ao ) + s(B0 ) nhỏ nhất. Ta chứng minh cách chia này thỏa mãn yêu cầu bài toán. Giả sử rằng cách chia này vẫn chưa thoả mãn yêu cầu, tức là vẫn có một nghị sĩ nào đó có nhiều hơn 1 kẻ thù trong viện của mình. Không mất tính tổng quát, giả sử nghị sĩ x thuộc A0 có ít nhất 2 kẻ thù trong A0 . Khi đó ta thực hiện phép biến đổi sau: chuyển x từ A0 sang B0 để được cách chia mới là A = A0 \ {x} và B = B0 \ {x}. Vì x có ít nhất 2 kẻ thù trong A0 và A không cón chứa x nên ta có s(A ) ≤ s(A0 ) − 4 (trong tổng mất đi ít nhất 2 Trang 7 của s(x) và 2 của các kẻ thù của x trong A0 ). Vì x có không có quá 3 kẻ thù và có ít nhất 2 kẻ thù trong A0 nên x có nhiều nhất 1 kẻ thù trong B0 (hay B ) cho nên s(B ) ≤ s(B0 ) + 2. Từ đó s(A ) + s(B ) ≤ s(A0 ) + s(B0 ) − 2. Mâu thuẫn với tính nhỏ nhất của s(A0 ) + s(B0 ). Vậy điều giả sử là sai, tức là cách chia (A0 , B0 ) thỏa mãn yêu cầu bài toán. Ví dụ 12. Chứng minh rằng trên mặt phẳng tọa độ, không thể tìm được năm điểm nguyên là đỉnh của một ngũ giác đều. (Một điểm M (x; y) trên mặt phẳng tọa độ được gọi là “điểm nguyên” nếu cả hai tọa độ x, y của nó đều là những số nguyên) Lời giải. Giả thiết trái lại, tồn tại một ngũ giác đều sao cho 5 đỉnh của nó đều là các “điểm nguyên”. Ta xét tập hợp sau: Ω = {a2 |a là cạnh của ngũ giác đều có năm đỉnh là các “điểm nguyên”}. Dễ thấy, do a là cạnh của ngũ giác đều với các đỉnh nguyên, nên a2 là số nguyên dương. Thật vậy, giả sử Aa A2 A3 A4 A5 là đa giác giác đều thuộc Ω. Giả sử Ai (xi ; yi ), i = 1, n, thì nếu gọi a là cạnh của ngũ giác đều này, ta có: a2 = A1 A2 = (x1 − x2 )2 + (y1 − y2 )2 . 2 Do xi , yi ∈ Z, ∀i = 1, 5 nên a2 là số nguyên dương. Tập Ω = ∅, điều này suy ra từ giả thiết phản chứng. Tập Ω các số tự nhiên, khác rỗng nên theo nguyên lí cực hạn suy ra tồn tại phần tử nhỏ nhất, tức là tồn tại ngũ giác đều ABCDE sao cho a2 là số 0 nhỏ nhất, ở đây a0 là cạnh của ngũ giác đều này. Dễ thấy ABCB , BCDC , CDED , DEAE và EABA đều là các hình bình hành với BD ∩ CE = A , AD ∩ CE = B , AD ∩ BE = C , AC ∩ BE = D , AC ∩ BD = E . Từ hình bình hành EABA suy ra xA = xB + xE − xA yA = yB + yE − yA . Do A, B, C, D, E là các “điểm nguyên” nên suy ra A cũng là “điểm nguyên”. Tương tự ta có B , C , D , E cũng là các “điểm nguyên”. Rõ ràng A B C D E Trang 8 là ngũ giác đều có các đỉnh là các “điểm nguyên” mà nếu gọi cạnh của ngũ giác đều này là a0 thì rõ ràng a02 < a2 (mâu thuẫn với việc a2 là giá trị nhỏ 0 0 nhất). Vậy giả thiết phản chứng là sai nên không tồn tại ngũ giác đều có các đỉnh đều là “điểm nguyên”. 2.3 Bài tập tự luyện Bài tập 1 Trên đường thẳng cho 50 đoạn thẳng. Chứng minh rằng hoặc có 8 đoạn thẳng trong chúng đôi một giao nhau, hoặc có 8 đoạn thẳng trong chúng đôi một rời nhau. Bài tập 2 Chứng minh rằng mọi đa giác lồi có diện tích bằng 1 đều có thể phủ bằng một hình chữ nhật có diện tích không lớn hơn 2. Bài tập 3 Có một bộ quả cân có tính chất sau: i) Trong bộ có ít nhất 5 quả cân có trọng lượng khác nhau. ii) Với hai quả cân bất kì, tìm được hai quả cân khác có tổng trọng lượng bằng với tổng trọng lượng của hai quả cân đó. Hỏi bộ quả cân này có ít nhất là bao nhiêu quả cân? Bài tập 4 Chứng minh rằng nếu a, b là các số nguyên dương sao cho k = a2 + b2 là số nguyên thì k = 5. ab − 1 Bài tập 5 Một số thực dương được viết lên bảng. Tổng của các tích đôi một của chúng bằng 1. Chứng minh rằng ta có thể xóa đi một số để √ tổng các số còn lại nhỏ hơn 2. Bài tập 6 Trong mặt phẳng cho n điểm (n > 1). Hai người chơi lần lượt nối một cặp điểm chưa được nối bằng một vector với một trong hai chiều. Nếu sau nước đi của người nào đó, tổng các vector đã vẽ bằng 0 thì người thứ hai thắng; nếu cho đến khi không còn vẽ được vector nào nữa mà tổng vẫn chưa có lúc nào bằng 0 thì người thứ nhất thắng. Hỏi ai là người thắng cuộc nếu chơi đúng? Bài tập 7 Trên mặt phẳng kẻ những đường thẳng song song cách đều. Chứng minh rằng không thể dựng được một ngũ giác đều có đỉnh chỉ nằm trên các đường thẳng này. Bài tập 8 Cho đa giác lồi A1 A2 A3 . . . An . Chứng minh rằng tồn tại ba đỉnh liên tiếp sao cho hình tròn qua ba đỉnh này chứa toàn bộ đa giác đã cho. Trang 9 Bài tập 9 Trên một đường thẳng đánh dấu n điểm khác nhau A−1, A2 , . . . , An theo thứ tự từ trái qua phải (n ≥ 4). Mỗi điểm được tô bằng một trong bốn màu khác nhau và cả bốn màu đều được dùng. Chứng minh rằng tồn tại một đoạn thẳng chứa đúng hai điểm của hai màu và ít nhất của hai màu còn lại. Bài tập 10 Từ một điểm M cho trước ở trong một đa giác lồi hạ các đường vuông góc xuống các cạnh của đa giác. Chứng minh rằng tồn tại một cạnh của đa giác mà chân đường vuông góc hạ từ M xuống cạnh này thì nằm ở phía trong của nó. Bài tập 11 Cho 997 điểm khác nhau trên mặt phẳng. Chứng minh rằng tồn tại ít nhất 1991 trung điểm khác nhau từ các cặp điểm này. Khi nào thì có đúng 1991 trung điểm khác nhau. Bài tập 12 Trên mặt phẳng cho một số hữu hạn điểm không cùng nằm trên một đường thẳng. Chứng minh rằng tồn tại ba điểm sao cho đường tròn đi qua ba điểm đó không chứa điểm nào ở bên trong. Bài tập 13 Bên trong một hình vuông cạnh 1 cho n điểm sao cho không có ba điểm nào thẳng hàng. Chứng minh rằng tồn tại một tam giác có đỉnh tại các điểm đã cho và diện tích S của nó thỏa mãn bất 1 . đẳng thức: S < n−2 3 Hiệu quả của đề tài Học sinh có thêm kinh nghiệm trong việc xử lý các bài toán tổ hợp bằng phương pháp sử dụng nguyên lí cực hạn. Trang 10 4 Tài liệu tham khảo 1. Đoàn Quỳnh - Doãn Minh Cường - Trần Nam Dũng - Đặng Hùng Thắng (2010), “Tài liệu chuyên toán đại số 10”, Nhà xuất bản giáo dục Việt Nam, 2012. 2. Phan Huy Khải, “Chuyên đề bồi dưỡng học sinh giỏi toán Trung học phổ thông: Các bài toán hình học Tổ hợp”, Nhà xuất bản Giáo dục, 2007. 3. Trần Nam Dũng, “Nguyên lí cực hạn)”, 2012. Người thực hiện Phạm Doãn Lê Bình Trang 11 BM04-NXĐGSKKN SỞ GD&ĐT ĐỒNG NAI Đơn vị THPT chuyên Lương Thế Vinh CỘNG HOÀ XÃ HỘI CHỦ NGHĨA VIỆT NAM Độc lập - Tự do - Hạnh phúc ................................, ngày tháng năm PHIẾU NHẬN XÉT, ĐÁNH GIÁ SÁNG KIẾN KINH NGHIỆM Năm học:2016 - 2017 ––––––––––––––––– Tên sáng kiến kinh nghiệm: NGUYÊN LÍ CỰC HẠN TRONG CÁC BÀI TOÁN TỔ HỢP ............................................................................................................................................... Họ và tên tác giả: Phạm Doãn Lê Bình Chức vụ: Giáo viên Đơn vị: THPT chuyên Lương Thế Vinh. Lĩnh vực: (Đánh dấu X vào các ô tương ứng, ghi rõ tên bộ môn hoặc lĩnh vực khác) - Quản lý giáo dục  - Phương pháp dạy học bộ môn: ...............................  - Phương pháp giáo dục  - Lĩnh vực khác: ........................................................  Sáng kiến kinh nghiệm đã được triển khai áp dụng: Tại đơn vị  Trong Ngành  1. Tính mới (Đánh dấu X vào 1 trong 2 ô dưới đây) - Có giải pháp hoàn toàn mới  - Có giải pháp cải tiến, đổi mới từ giải pháp đã có  2. Hiệu quả (Đánh dấu X vào 1 trong 4 ô dưới đây) - Hoàn toàn mới và đã triển khai áp dụng trong toàn ngành có hiệu quả cao  - Có tính cải tiến hoặc đổi mới từ những giải pháp đã có và đã triển khai áp dụng trong toàn ngành có hiệu quả cao  - Hoàn toàn mới và đã triển khai áp dụng tại đơn vị có hiệu quả cao  - Có tính cải tiến hoặc đổi mới từ những giải pháp đã có và đã triển khai áp dụng tại đơn vị có hiệu quả  3. Khả năng áp dụng (Đánh dấu X vào 1 trong 3 ô mỗi dòng dưới đây) - Cung cấp được các luận cứ khoa học cho việc hoạch định đường lối, chính sách: Tốt  Khá  Đạt  - Đưa ra các giải pháp khuyến nghị có khả năng ứng dụng thực tiễn, dễ thực hiện và dễ đi vào cuộc sống: Tốt  Khá  Đạt  - Đã được áp dụng trong thực tế đạt hiệu quả hoặc có khả năng áp dụng đạt hiệu quả trong phạm vi rộng: Tốt  Khá  Đạt  Phiếu này được đánh dấu X đầy đủ các ô tương ứng, có ký tên xác nhận của người có thẩm quyền, đóng dấu của đơn vị và đóng kèm vào cuối mỗi bản sáng kiến kinh nghiệm. XÁC NHẬN CỦA TỔ CHUYÊN MÔN (Ký tên và ghi rõ họ tên) THỦ TRƯỞNG ĐƠN VỊ (Ký tên, ghi rõ họ tên và đóng dấu)