Ứng Dụng Nguyên Lí Cực Hạn Và Nguyên Lí Lân Cận Giải Một Số Bài ...

Tải bản đầy đủ (.docx) (83 trang)

1. Trang chủ
>>
2. Sư phạm
>>
3. Quản lý giáo dục

Ứng dụng nguyên lí cực hạn và nguyên lí lân cận giải một số bài toán hình học 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.09 MB, 83 trang )

TRƯỜNG ĐẠI HỌC SƯ PHẠM---NGÔ THỊ CHỨNG DỤNG NGUYÊN LÍ CỰC HẠN VÀ NGUYÊN LÍ LÂNKHOÁ LUẬN TỐT NGChuyên ngành: Hình họcHÀ NỘI 20TRƯỜNG ĐẠI HỌC SƯ PHẠM---NGÔ THỊ CHỨNG DỤNG NGUYÊN LÍ CỰC HẠN VÀ NGUYÊN LÍ LÂNKHOÁ LUẬN TỐT NGChuyên ngành:Người hướng dẫnTh.S - GVC PHAN HỒHÀ NỘI 20LỜI CẢM ƠNEm xin chân thành cảm ơn các thầy, giáo cô giáo và các bạn sinh viênkhoa Toán trường đại học sư phạm Hà Nội 2 đã động viên, giúp đỡ để em cóđiều kiện tốt nhất trong suốt quá trình thực hiện khoá luận tốt nghiệp. Đặcbiệt, em xin bày tỏ lòng cảm ơn sâu sắc tới thầy Phan Hồng Trường đã địnhhướng chọn đề tài và tận tình chỉ bảo, giúp đỡ em hoàn thành tốt khoá luậnnày.Do thời gian và kiến thức có hạn nên khoá luận không tránh khỏinhững hạn chế và còn có những thiếu sót nhất định. Em xin chân thànhcảm ơn và tiếp thu ý kiến đóng góp của các thầy giáo, cô giáo và các bạn sinhviên.Hà Nội, tháng 05 năm 2012Sinh viênNgô Thị ChâuLỜI CAM ĐOANKhóa luận được hoàn thành với sự chỉ bảo tận tình của các thầy cô giáotrong khoa Toán trường Đại học sư phạm Hà Nội 2, đặc biệt là sự hướng dẫntận tình của thầy giáo Phan Hồng Trường.Trong khóa luận có tham khảo các kết quả nghiên cứu của các nhà khoahọc với sự trân trọng và biết ơn. Em xin khẳng định kết quả của đề tài nàykhông có sự trùng lặp với kết quả của các đề tài khác. Nếu sai em xin chịuhoàn toàn trách nhiệm.Hà Nội, tháng 05 năm 2012Sinh viênNgô Thị ChâuMỤC LỤCMỞ ĐẦU........................................................................................................... 1CHƯƠNG 1: NGUYÊN LÍ CỰC HẠN VỚI CÁC BÀI TOÁN HÌNHHỌC TỔ HỢP.................................................................................................. 21. NGUYÊN LÍ...................................................................................................... 21.1 Nội dung nguyên lí.......................................................................................21.1.1 Nguyên lí 1................................................................................................21.1.2 Nguyên lí 2................................................................................................21.2 Ứng dụng.....................................................................................................21.2.1 Tổng quát..................................................................................................21.2.2 Ứng dụng giải bài toán hình học tổ hợp...................................................22. ỨNG DỤNG NGUYÊN LÍ CỰC HẠN VÀO GIẢI CÁC BÀI TOÁNHÌNH HỌC TỔ HỢP......................................................................................... 32.1 Bài toán và lời giải......................................................................................32.2 Một số bài toán tham khảo........................................................................21CHƯƠNG 2 : NGUYÊN LÍ LÂN CẬN GIẢI CÁC BÀI TOÁN HÌNHHỌC TỔ HỢP................................................................................................ 231. NGUYÊN LÍ.................................................................................................... 231.1 Các khái niệm............................................................................................231.1.1Định nghĩa 1........................................................................................231.1.2Định nghĩa 2........................................................................................231.2 Nguyên lí...................................................................................................251.2.1 Nguyên lí 1..............................................................................................251.2.2 Nguyên lí 2..............................................................................................252. ỨNG DỤNG NGUYÊN LÍ LÂN CẬN VÀO GIẢI CÁC BÀI TOÁNHÌNH HỌC TỔ HỢP....................................................................................... 25KẾT LUẬN..................................................................................................... 47TÀI LIỆU THAM KHẢO............................................................................. 48MỞ ĐẦU1. Lí do chọn đề tàiNguyên lí cực hạn và nguyên lí lân cận là hai nguyên lí rất hữu ích vàthường được vận dụng cho nhiều lớp bài toán khác nhau, đặc biệt nó có íchkhi giải các bài toán tổ hợp nói chung và hình học tổ hợp nói riêng. Vận dụngnguyên lí cực hạn và nguyên lí lân cận vào giải các bài toán tố hợp khiến chobài toán trở nên đơn giản hơn, đặc biệt là việc giảm bớt số lượng đối tượngkhổng lồ trong các bài toán tổ hợp. Nhờ tính chất riêng của nó mà nguyên lícực hạn và nguyên lí lân cận đặc biệt hữu ích khi áp dụng giải các bài toánhình học tổ hợp, mà đặc biệt đây lại là nhóm kiến thức mới rất quan trọngtrong trương trình toán ở bậc trung học phổ thông. Để tiếp cận với kiến thứcnày, được sự định hướng của người hướng dẫn, tôi chọn đề tài “Ứng dụngnguyên lí cực hạn và nguyên lí lân cận vào giải các bài toán hình học tổhợp” để hoàn thành khoá luận Tốt nghiệp Đại học chuyên ngành Hình học.2. Mục đích nghiên cứu- Tìm hiểu nguyên lí cực hạn và nguyên lí lân cận.- Làm rõ tính ưu việt của việc ứng dụng nguyên lí cực hạn và nguyên lí lân cậngiải một số bài toán hình học tổ hợp.3. Đối tượng, phạm vi nghiên cứu- Đối tượng nghiên cứu: nguyên lí cực hạn và nguyên lí lân cận.- Phạm vi nghiên cứu: một số bài toán hình học tổ hợp giải bằng phươngpháp sử dụng nguyên lí cực hạn và nguyên lí lân cận.4. Nhiệm vụ nghiên cứu- Trình bày các khái niệm cơ bản về nguyên lí cực hạn và nguyên lí lân cận.- Đề xuất một số phương pháp giải bài toán hình học tổ hợp giải bằng phươngpháp sử dụng nguyên lí cực hạn và nguyên lí lân cận.5. Các phương pháp nghiên cứu- Nghiên cứu sử dụng các lí luận, các công cụ toán học.- Nghiên cứu sách tham khảo, các tài liệu liên quan.6CHƯƠNG 1: NGUYÊN LÍ CỰC HẠN VỚI CÁC BÀI TOÁNHÌNH HỌC TỔ HỢP1. NGUYÊN LÍ1.1 Nội dung nguyên lí1.1.1 Nguyên lí 1Trong 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.1.1.2 Nguyên lí 2Trong 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.1.2 Ứng dụng1.2.1 Tổng quátSử dụng nguyên lí cực hạn là một phương pháp được vận dụng trongnhiều lớp bài toán khác nhau, đặc biệt nó có ích khi giải các bài toán tổ hợpnói chung và Hình học tổ hợp nói riêng.Nguyên tắc này dùng để giải những 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 thường được sử dụng kết hơp với các phương phápkhác, đặc biệt là phương pháp phản chứng. Nguyên lí này được vận dụngtrong trường hợp những tập giá trị cần khảo sát chỉ là tập hợp hữu hạn(nguyên lí 1) hoặc có thể là vô hạn nhưng tồn tại một phần tử lớn nhất hoặcnhỏ nhất (nguyên lí 2).1.2.2 Ứng dụng giải bài toán hình học tổhợp Lược đồ giải- Đư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ị nhỏ nhất (hoặc lớn nhất)này.- Chỉ ra một mâu thuẫn, hoặc đưa ra một giá trị còn nhỏ hơn (hoặc lớnhơn) giá trị nhỏ nhất (hoặc lớn nhất) mà ta đang khảo sát.Theo nguyên lí của phương pháp phản chứng ta suy ra điều phải chứngminh.2. ỨNG DỤNG NGUYÊN LÍ CỰC HẠN VÀO GIẢI CÁC BÀI TOÁNHÌNH HỌC TỔ HỢPÁp dụng nguyên lí cực hạn vào giải các bài toán hình học tổ hợp.2.1 Bài toán và lời giảiBài1: Chứng minh bốn đường tròn có bốn đường kính là bốn cạnh củatứ giác lồi thì phủ kín tứ giác đã cho.GiảiLấy M là một điểm tuỳ ý của tứ giác lồi ABCD. Có hai khả năng xảy ra:1. Nếu M nằm trên biên của đa giác (tức M nằm trên một cạnh của tứgiác ABCD). Khi đó M phải nằm trong hình tròn có đường kính là cạnh ấy.Trong trường hợp này kết luận của bài toán hiển nhiên đúng.CDBMA2. Nếu M nằm bên trong tứ giác lồi ABCD. Khi đó ta có:□AMB + B□MC + C□MD + D□MA = 3600Theo nguyên lí cực hạn, tồn tạimax{ □AMB, B□MC,C□MD, D□MA} = B□MCKhi ấy :B□MC ≥090(1)Từ (1) suy ra M nằm trong (hoặc cùng lắm là nằm trên) đường trònđường kính BC. Vậy đương nhiên M bị phủ bởi đường tròn này.Như thế do M là điểm tuỳ ý của tứ giác ABCD, ta suy ra bốn hình trònnói trên phủ kín tứ giác lồi đã cho. Đó là điều phải chứng minh.Bài2: Cho đa giác lồi A1A2 . . . 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.GiảiTheo nguyên lý cực hạn thì tồn tại cạnh đa giác AiAj sao cho :Ai Aj = min Ak+Ak1≤k ≤n1(ở đây quy ước n+1 là 1, tức là AnAn+1 ≡ AnA1) . Khi đó, với mọi j ≠ i,j ≠ i+1,thì □Ai A j ≤ (nói riêng □Ai A j > 00 ).0Ai+160 Ai+1Như vậy tập hợp bộ ba đỉnh trong đó có hai đỉnh kề nhau, còn đoạnthẳng nối hai đỉnh này được nhìn từ đỉnh thứ ba dưới một góc không quá 900là tập hợp không rỗng. Rõ ràng tập hợp này hữu hạn, vì thế lại theo nguyên lícực hạn, tồn tại đường tròn (Ω) sao cho nó đi qua tập hợp bộ ba đỉnh nhưtrên và có bán kính lớn nhất R .Giả sử (Ω) là đường tròn đi qua ba đỉnh kề nhau A1, A2 và đỉnh Anàođó của đa giác mà □A1AA20≤ 90 .Ta chứng minh rằng mọi đỉnh của đa giác lồi đều nằm trong hình tròn (Ω).Chú ý rằng từ tính lồi của đa giác suy ra toàn bộ đa giác nằm về mộtphía củaA1 A2 (về phía có đỉnh A).AB(Ω)A2A1Giả thiết phản chứng kết luận trên không tức là tồn tại B∉ (Ω). Do vậyB phải ở ngoài hình tròn (Ω).Suy ra :□A BA < □A AA⇒ 0 < sin □A BA < sin □A AA120 12≤ 901⇒212A1 A2A□1 A2□>= R2sin A1BA2 2sin A1AA 2Như vậy bán kính đường tròn ngoại tiếp tam giác A1BA2 lớn hơn R.Điều này mâu thuẫn với việc chọn (Ω). Vậy giả thiết phản chứnglà sai,tức là mọi đỉnh của đa giác lồi (tức là toàn bộ đa giác lồi) bị phủ bởiđường tròn (Ω).Có hai trường hợp sau xảy ra :1. Nếu A ≡ A3, khi đó A1, A2, A3 là ba đỉnh liên tiếp cần tìm.2. Nếu A không trùng với A3, khi đó gọi A3 là đỉnh kề với A2 (A3≠ A1).Ta chứng minh rằng A3 ∈ (Ω).AA(Ω)(Ω)A3A1A2AA31A2Giả sử trái lại A3 ∉ (Ω). Do A3 là đỉnh của đa giác lồi, nênA3 thuộc vào hình viên phân giới hạn bởi □A2 A (xem hình vẽ). Từ đótheo tính chất của0□A A A . Từ đó suy ra bánđường tròn ta có ngay 2□A3 A A > 1802 1−kính đường tròn ngoại tiếp tam giác A2A3A lớn hơn bán kính đường trònngoạitiếp tam giác AA1A2. Điều này cũng vô lí. Vậy A3 phải thuộc(Ω). Lúc này A1A2A3 có đường tròn ngoại tiếp chính là (Ω), và dođó đường tròn qua A1, A2, A3 phủ đa giác lồi. Đó là điều phải chứng minh.Bài3 : Trên một đường thẳng đánh dấu n điểm khác nhau A1, A2, . . . Antheo thứ tự từ trái qua phải (n ≥ 4). Mỗi điểm được tô bằng một trongbốn màu khác nhau và cả bốn màu đều được dùng. Chứng minh rằng tồn tạimột đoạn thẳng chứa đúng hai điểm của hai màu và ít nhất hai điểm của haimàu còn lạiGiảiXét tập hợp sau :A = {k | 1 ≤ k ≤ n và giữa các điểm A1, A2,...An có mặt đủ bốnmàu}.Tập A ≠ ∅ (vì theo giả thiết dùng cả bốn màu), và A hữuhạn nên theo nguyên lý cực hạn, tồn tại chỉ số i nhỏ nhất mà i ∈ A.Theo định nghĩa của tập hợp A, vì lý do i là chỉ số bé nhất thuộc A, nênmàu của điểm Ai sẽ khác với màu của tất cả các điểm A1, A2, ...Ai-1.Chú ý rằng bây giờ trong dãy A1, A2, …Ai lại có đủ bốn màu.Xét tiếp tập hợp sau :B = {k | 1≤ k ≤ i và giữa các điểm Ak , Ak+1, ...Ai có mặt đủ bốnmàu}.Tập B ≠ ∅ (vì dãy A1, A2, ...Ai có đủ bốn màu), và B hữuhạn nên theo nguyên lý cực hạn, tồn tại chỉ số j lớn nhất mà j ∈ B.Theo định nghĩa của tập hợp B, và do j là chỉ số lớn nhất thuộc B, nênmàu của điểm Aj sẽ khác với tất cả các điểm Aj+1, ...Aj.Aj••Aj+1•Ai+1Ai•Xét đoạn [AjAi]. Khi đó đoạn thẳng này chứa đúng hai điểm của haimàu (đó là Aj và Ai) và ít nhất hai điểm của hai màu còn lại Aj+1,...., Ai-1. bàitoán được giải hoàn toàn.Bài4 : 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ố tuỳ ý luôn bằng trung bình cộng củabốn số tự nhiên trong bốn ô vuông có chung cạnh với nó. Chứng minh rằngkhi đó tất cả các số được điền đều bằng nhau.GiảiXé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.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ôngphải là bằng nhau tất cả. Như vậy sẽ có một ô chứa a mà trong bốn ô có cạnhchung với nó sẽ có ít nhất một số b ≠ a.cbadeGiả sử ba ô còn lại có cạnh chung với ô chứa số a này là c, d, e. Theocách xác định số a, ta có b > a, c≥ a, d ≥ a, e ≥ a.Từ đó đi đến :b+ ca d (K , A3 A2 ) = d ( A1, A3 A2 ) .Từ đó ta đi đến :SA A A> SA A A1 321 232. Nếu Aj thuộc miền 4, khi đó :d ( A j , A3 A2 ) > d ( A1, A3 A2 )> SASA ATừ đó :AAA1 3Aj2A3(4)212311K2AA2 6H3A14M5Từ (3) hoặc (4) đi đến mâu thuẫn vớiK6A33H3AjA1 4M 5S A A A = max SA A A1ijk1j≤i ≠ j ≠kVậy giả thiết phản chứng là sai,tức là cả bộ n điểm đã cho nằm trọntrong tam giác KHM, mà SKHM ≤ 4.Đó chính là điều phải chứng minh.Bài 9: Chứng minh rằng trongmặt phẳng toạ độ, 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 toạ độ được gọi là “điểmnguyên”, nếu hai toạ độ x, y của nóđều là những số nguyên).GiảiGiả 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ànhững “điểm nguyên”. Ta xét tập hợpsau :2Ω = { a a là cạnh của ngũgiácđều có năm đỉnh là các “điểmnguyên” }Dễ thấy, do a là cạnh của ngũ2giác đều. Với các đỉnh nguyên, nên a làsố nguyên dương.Thật vậy, giả sử A1A2A3A4A5 làđa giác đều thuộc Ω. Giả sửAi (xi, yj),i = 1,5thì nếu gọia làcạnhcủangũ giác đều này,ta có:22a = A1A2 = (x2 22x1) + ( y2- y1)BAD’E’CA’’CB’EDDoxi,yj∈Ζ,∀i=1,5suy từ giảthiết phảnchứng.nênaơng.T2 ậl pà Ωsố ≠ng∅u,yê điềund nàyưTập Ω các số tự nhiên, khác rỗng, nên theo nguyên lý cực hạnsuy ra tồn tại phần tử nhỏ nhất, tức là tồn tại ngũ giác đều ABCDE sao2a*là số nhỏ nhất, ở đây a* là cạnh của ngũ giác đều này. Dễ thấy’’’’ABCB , BCDC , DEAE , và EABA đều là các hình bình hành với BD’’’’∩ CE=A , AD ∩ BE=C , AC ∩ BE=D , AC ∩ BD=E .’Từ hình bình hành EABA suy ra: x A' = xB + xE − x A yA' = yB'+ yE − y A(1)Do A, B, C, D, E là các “điểm nguyên” nên xA, xE, xB , yA, yE, yB đều làcác số nguyên. Vì thế từ (1) suy ra x ' , y ' cũng là các số nguyên. Như thế AAA’’’là “điểm nguyên”. Rõ ràng B’, C’, D , E cũng là các “điểm nguyên”. Rõ’ ’’’ ’ràng A B C D E là ngũ giác đều với các đỉnh của nó đều là các điểm’’’’’’nguyên, tức là A B C D E ∈ Ω. Mặt khác, nếu gọi a là cạnh củangũ giác đều, thì rõ là :’a < a* ⇒’22a