Skkn Nguyên Lý Cực Hạn Trong Các Bài Toán Tổ Hợp - Tài Liệu Text

Tải bản đầy đủ (.pdf) (14 trang)

1. Trang chủ
>>
2. Giáo Dục - Đào Tạo
>>
3. Trung học cơ sở - phổ thông

skkn nguyên lý cực hạn trong các bài toán tổ hợp

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (1.35 MB, 14 trang )

BM 01-Bia SKKNSỞ GIÁO DỤC VÀ ĐÀO TẠO ĐỒNG NAIĐơn vị THPT chuyên Lương Thế VinhMã số: ................................(Do HĐKH Sở GD&ĐT ghi)SÁNG KIẾN KINH NGHIỆMNGUYÊN LÍ CỰC HẠNTRONG CÁC BÀI TOÁN TỔ HỢPNgười thực hiện: Phạm Doãn Lê BìnhLĩ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ácNăm học: 2016 - 2017BM02-LLKHSKKNSƠ LƯỢC LÝ LỊCH KHOA HỌCI. THÔNG TIN CHUNG VỀ CÁ NHÂN1. Họ và tên: Phạm Doãn Lê Bình2. Ngày tháng năm sinh: 23/04/19863. Nam, nữ: Nam4. Địa chỉ: 1123, KP7, P. Long Bình, TP. Biên Hòa, Đồng Nai5. Điện thoại: 0613930245 (nhà riêng) ; ĐTDĐ: 016835311006. Fax:E-mail: 7. Chức vụ: Giáo viên8. Đơ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ánSố 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ẠNTRONG CÁC BÀI TOÁN TỔ HỢPPhạm Doãn Lê BìnhGiáo viên trường THPT chuyên Lương Thế VinhTháng 4 năm 2017Mục lục1 Lý do chọn đề tài22 Nội2.12.22.32229dung đề tàiNêu vấn đề . . . . . . . . . . . . . . . . . . . . . . . . . . . .Một số ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . .Bài tập tự luyện . . . . . . . . . . . . . . . . . . . . . . . . . .3 Hiệu quả của đề tài104 Tài liệu tham khảo11Trang 11Lý do chọn đề tàiNguyê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ụngkhé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ácbà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ácphương pháp khác, đặc biệt là phương pháp phản chứng. Nó giúp chúng tagiả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ánthì 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ệugiả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ếpcận các bài toán tổ hợp.2Nội dung đề tài2.1Nê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 tathườ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ênlí 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ánphả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ảichứng minh.Ta xét một số ví dụ sau:2.2Mộ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 2Lờ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ủamộ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ăngxả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ìnhtrò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ằmtrong 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ìnhtròn nào đó có đường kính là một cạnh của tứ giác ABCD nên tứ giác ABCDsẽ 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ộngcủ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ácrỗ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ệulà a.Trang 3Giả 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ảitất cả đều bằng nhau. Như vậy sẽ có một ô chứa số a mà trong bốn ô cạnhchung với nó sẽ có ít nhất một số b = a. Giả sử ba ô còn lại có cạnh chungvớ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 raa 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ựchạn thì A có phần tử nhỏ nhất h◦ . Giả sử h◦Mlà khoảng cách từ M đến đường thẳng đi quaEB, C (M, B, C ∈ S). Theo giả thiết phản chứngthì tồn tại D ∈ S và D nằm trên đường thẳngFBC. Kẻ M H⊥BC thì M H = h◦ . Rõ ràng trong3 điểm B, C, D thì theo nguyên lí Dirichlet phảicó ít nhất 2 điểm nằm cùng phía so với H trênBHCDđườ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 trong5 học sinh thi cùng một môn thì có hai học sinh cùng tuổi. Chứng minh rằngtrong 65 học sinh có ít nhất 3 học sinh đến từ một trường, thi cùng một mônvà 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ộttrườ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ùngtuổi, ta giả sử đó là hai học sinh A1 , B1 . Ta loại hai học sinh này còn lại 7trong học sinh và trong 7 học sinh nay ta tìm được hai học sinh cùng tuổiA2 , 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ệulà A5 ). Khi đó A5 sẽ cùng tuổi với 1 trong 4 học sinh A1 , A2 , A3 , A4 . Chẳnghạn A5 , A1 cùng tuổi. Khi đó A1 , B1 , A5 thoả yêu cầu bài toán . Điều nàymâ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ànhphố. Ban đầu giữa các thành phố chưa có đường. Người ta muốn xây dựngmột số con đường một chiều nối giữa các thành phố sao cho: Nếu có đườngTrang 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ấtphá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ácthành phố loại II không có đường đi. Số các đường đi liên quan đến các thànhphố 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ơn2102(m + n + p + 1)2=.mn + (p + 1)m + (p + 1)n ≤33Dấu bằng xảy ra với đồ thị 3 phe, mỗi phe có 70 thành phố, thành phố phe1 có đường đi đến thành phố phe 2, thành phố phe 2 có đường đi đến thànhphố 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ứngminh rằng có thể chia quốc hội thành 2 viện sao cho trong mỗi viện, mỗi mộtnghị 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ỗiviệ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ànhviê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ỏamã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ộtnghị sĩ nào đó có nhiều hơn 1 kẻ thù trong viện của mình. Không mất tínhtổng quát, giả sử nghị sĩ x thuộc A0 có ít nhất 2 kẻ thù trong A0 . Khi đó tathực hiện phép biến đổi sau: chuyển x từ A0 sang B0 để được cách chia mớilà A = A0 \ {x} và B = B0 \ {x}. Vì x có ít nhất 2 kẻ thù trong A0 và Akhông cón chứa x nên ta có s(A ) ≤ s(A0 ) − 4 (trong tổng mất đi ít nhất 2Trang 7củ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ủas(A0 ) + s(B0 ). Vậy điều giả sử là sai, tức là cách chia (A0 , B0 ) thỏa mãn yêucầ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 đượcnă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ặtphẳ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 A22 = (x1 − x2 )2 + (y1 − y2 )2 .Do xi , yi ∈ Z, ∀i = 1, 5 nên a2 là số nguyên dương. Tập Ω = ∅, điều này suyra 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ồntại phần tử nhỏ nhất, tức là tồn tại ngũ giác đều ABCDE sao cho a20 là số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ìnhbình hành EABA suy raxA = xB + xE − xAyA = 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 ETrang 8là 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 < a20 (mâu thuẫn với việc a20 là giá trị nhỏ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.3Bài tập tự luyệnBà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ạnthẳ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ổngtrọ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 + b2là số nguyên thì k = 5.ab − 1Bà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ộtcủ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ượtnối một cặp điểm chưa được nối bằng một vector với một tronghai 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ònvẽ đượ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 đỉnhliên tiếp sao cho hình tròn qua ba đỉnh này chứa toàn bộ đa giácđã cho.Trang 9Bài tập 9 Trên một đường thẳng đánh dấu n điểm khác nhau A−1, A2 , . . . , Antheo thứ tự từ trái qua phải (n ≥ 4). Mỗi điểm được tô bằng mộttrong bốn màu khác nhau và cả bốn màu đều được dùng. Chứngminh rằng tồn tại một đoạn thẳng chứa đúng hai điểm của haimà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 đườngvuông góc xuống các cạnh của đa giác. Chứng minh rằng tồn tạimột cạnh của đa giác mà chân đường vuông góc hạ từ M xuốngcạ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ồntại ít nhất 1991 trung điểm khác nhau từ các cặp điểm này. Khinà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ênmộ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áccó đỉnh tại các điểm đã cho và diện tích S của nó thỏa mãn bất1.đẳng thức: S