Khóa luận tốt nghiệp đại học ngành Sư phạm Toán: Vận dụng nguyên lí khởi đầu cực trị và nguyên lí Dirichlet để giải các bài toán thi học sinh giỏi Trung học phổ thông

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:52

Thêm vào BST

Báo xấu

9
lượt xem 5
download

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

Khóa luận tốt nghiệp đại học ngành Sư phạm Toán "Vận dụng nguyên lí khởi đầu cực trị và nguyên lí Dirichlet để giải các bài toán thi học sinh giỏi Trung học phổ thông" trình bày các nội dung: Kiến thức chuẩn bị; Ứng dụng nguyên lí khởi đầu cực trị và nguyên lí Dirichlet.

Chủ đề:

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

Lưu

Nội dung Text: Khóa luận tốt nghiệp đại học ngành Sư phạm Toán: Vận dụng nguyên lí khởi đầu cực trị và nguyên lí Dirichlet để giải các bài toán thi học sinh giỏi Trung học phổ thông

UBND TỈNH QUẢNG NAM TRƯỜNG ĐẠI HỌC QUẢNG NAM KHOA: TOÁN ---------- PƠLOONG THỊ NEO VẬN DỤNG NGUYÊN LÍ KHỞI ĐẦU CỰC TRỊ VÀ NGUYÊN LÍ DIRICHLET ĐỂ GIẢI CÁC BÀI TOÁN THI HỌC SINH GIỎI TRUNG HỌC PHỔ THÔNG KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Quảng Nam, tháng 6 năm 2021
UBND TỈNH QUẢNG NAM TRƯỜNG ĐẠI HỌC QUẢNG NAM KHOA: TOÁN ---------- KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Tên đề tài: VẬN DỤNG NGUYÊN LÍ KHỞI ĐẦU CỰC TRỊ VÀ NGUYÊN LÍ DIRICHLET ĐỂ GIẢI CÁC BÀI TOÁN THI HỌC SINH GIỎI TRUNG HỌC PHỔ THÔNG Sinh viên thực hiện PƠLOONG THỊ NEO MSSV: 2117010115 CHUYÊN NGÀNH: SƯ PHẠM TOÁN KHÓA: 2017 – 2021 Cán bộ hướng dẫn TS. TRẦN VĂN SỰ MSCB: Quảng Nam, tháng 6 năm 2021
LỜI CẢM ƠN Trước khi trình bày nội dung chính của khoá luận, tôi xin bày tỏ lòng kính trọng và biết ơn sâu sắc đến thầy giáo TS. Trần Văn Sự, người đã dành thời gian trực tiếp hướng dẫn, tận tình, chu đáo và giúp đỡ tôi thực hiện đề tài của mình. Bên cạnh đó tôi cũng xin chân thành cảm ơn các thầy cô giáo trong khoa Toán đã giúp đỡ và tạo điều kiện cho tôi trong suốt quá trình học tập cũng như hoàn thành khoá luận tốt nghiệp của mình. Cuối cùng, tôi xin gửi đến những người thân yêu và bạn bè một lời cảm ơn chân thành vì mọi người đã luôn khích lệ, động viên tôi trong suốt quá trình thực hiện đề tài này. Mặc dù đã cố gắng và nỗ lực hết mình nhưng không thể tránh khỏi những thiếu sót cần bổ sung và chỉnh sửa. Kính mong nhận được các lời nhận xét, góp ý của quý thầy cô giáo và các bạn để khoá luận được hoàn thiện hơn. Tôi xin chân thành cảm ơn! Quảng Nam, tháng 06 năm 2021 Sinh viên thực hiện Pơloong Thị Neo
MỤC LỤC MỞ ĐẦU .................................................................................................................... 2 1.Lý do chọn đề tài ..................................................................................................... 2 2. Mục tiêu nghiên cứu .............................................................................................. 2 3. Đối tượng và phạm vi nghiên cứu ......................................................................... 2 3.1. Đối tượng nghiên cứu .......................................................................................... 2 3.2. Phạm vi nghiên cứu ............................................................................................. 2 4. Phương pháp nghiên cứu ...................................................................................... 2 . 5. Đóng góp của đề tài ............................................................................................... 3 . 6. Cấu trúc đề tài........................................................................................................ 3 CHƯƠNG 1: KIẾN THỨC CHUẨN BỊ ................................................................... 4 1.1. Lý thuyết tập hợp ................................................................................................ 4 1.1.1. Cách biểu diễn tập hợp ..................................................................................... 4 1.1.2. Các kiểu quan hệ tập hợp ................................................................................. 5 1.2. Phương pháp chứng minh phản chứng ............................................................. 7 . 1.3. Một số tính chất của phép chia hết .................................................................... 8 . 1.4. Một số tính chất của đồng dư thức ..................................................................... 8 1.5. Một số kiến thức liên quan đến bất đẳng thức .................................................. 9 1.5.1. Bất đẳng thức trung bình cộng - trung bình nhân ........................................... 9 1.5.2. Bất đẳng thức Bunyakovsky ........................................................................... 10 . 1.6. Nguyên lý bù trừ ............................................................................................... 11 1.7. Nguyên lí khởi đầu cực trị ................................................................................ 13 1.8. Nguyên lí Dirichlet ............................................................................................ 13 1.8.1. Nội dung nguyên lí Dirichlet .......................................................................... 13 . 1.8.2. Nguyên lí Dirichlet mở rộng ........................................................................... 13 1.8.3. Nguyên lí Dirichlet dạng tập hợp .................................................................... 14 1.8.4. Nguyên lí Dirichlet dạng tập hợp mở rộng ..................................................... 14 1.8.5. Nguyên lí Dirichlet cho diện tích .................................................................... 15 CHƯƠNG 2: ỨNG DỤNG NGUYÊN LÍ KHỞI ĐẦU CỰC TRỊ VÀ NGUYÊN LÍ DIRICHLET VÀO BÀI TOÁN............................................................................... 16 2.1. Nguyên lí khởi đầu cực trị ................................................................................ 16 2.1.1. Ứng dụng vào giải bài toán hình học tổ hợp .................................................. 16
2.1.2. Ứng dụng vào giải bài toán tổ hợp .................................................................. 22 2.1.3. Ứng dụng vào giải bài toán số học ................................................................. 24 . 2.2. Nguyên lí Dirichlet ............................................................................................ 26 2.2.1. Ứng dụng vào giải bài toán hình học tổ hợp .................................................. 26 2.2.2. Ứng dụng vào giải bài toán tổ hợp .................................................................. 31 2.2.3. Ứng dụng vào giải bài toán số học ................................................................. 33 . 2.2.4. Ứng dụng vào giải bất đẳng thức .................................................................... 35 2.3. Mối liên hệ giữa hai nguyên lí khởi đầu cực trị và nguyên lí Dirichlet........... 42 KẾT LUẬN .............................................................................................................. 46 TÀI LIỆU THAM KHẢO ....................................................................................... 47
MỞ ĐẦU 1. Lý do chọn đề tài Trong Toán học, có một số bài toán mà chúng ta dùng nhiều phương pháp khác nhau để đưa ra một lời giải đúng. Chẳng hạn như phương pháp giải trực tiếp, phương pháp phản chứng, phương pháp quy nạp toán học, … để tìm ra lời giải cho các bài toán khá hóc búa. Trong các bài toán về lý thuyết tập hợp nói chung, lý thuyết tổ hợp nói riêng, nguyên lí khởi đầu cực trị và nguyên lí Dirichlet là hai nguyên lí có nội dung khá đơn giản nhưng cũng là phương pháp rất hiệu quả dùng để chứng minh nhiều kết quả sâu sắc trong toán học. Đặc biệt, hai nguyên lí này có thể áp dụng rộng rãi trong việc chứng minh các bài toán tổ hợp thường xuất hiện trong các kỳ thi học sinh giỏi quốc gia cũng như kỳ thi Olympic toán học quốc tế cho học sinh, sinh viên. Để thấy được tính ứng dụng thực tế cũng như tính hiệu quả của hai nguyên lí trên trong việc vận dụng vào giải các bài tập tổ hợp, hình học tổ hợp, số học,…cùng với sự giúp đỡ của giảng viên hướng dẫn khóa luận, tôi mạnh dạn chọn đề tài “Vận dụng nguyên lí khởi đầu cực trị và nguyên lí Dirichlet để giải các bài toán thi học sinh giỏi Trung học phổ thông” làm đề tài khoá luận tốt nghiệp cuối khóa của mình. 2. Mục tiêu nghiên cứu Khoá luận được hoàn thành với mục tiêu nghiên cứu vận dụng nguyên lí khởi đầu cực trị và nguyên lí Dirichlet để giải các bài toán thi học sinh giỏi Trung học phổ thông. 3. Đối tượng và phạm vi nghiên cứu 3.1. Đối tượng nghiên cứu Vận dụng nguyên lí khởi đầu cực trị và nguyên lí Dirichlet để giải các bài toán thi học sinh giỏi Trung học phổ thông. 3.2. Phạm vi nghiên cứu Đề tài tập trung nghiên cứu trong phạm vi vận dụng nguyên lí khởi đầu cực trị và nguyên lí Dirichlet để giải bài toán tổ hợp, hình học tổ hợp, số học. 4. Phương pháp nghiên cứu Để thực hiện đề tài nghiên cứu này, tôi sử dụng các phương pháp: - Phương pháp đọc tài liệu tham khảo kết hợp phân tích-tổng hợp tài liệu. - Phương pháp tham khảo ý kiến chuyên gia. - Hệ thống hoá, giải quyết vấn đề và sưu tầm giải quyết bài toán. 2
5. Đóng góp của đề tài Đề tài đưa ra phương pháp giải toán mới trong chương trình toán THPT ở các dạng toán nâng cao. Đề tài sẽ là một trong những tài liệu tham khảo cho những bạn quan tâm đến nguyên lí khởi đầu cực trị và nguyên lí Dirichlet. 6. Cấu trúc đề tài Ngoài phần mở đầu, kết luận và tài liệu tham khảo, khoá luận trình bày theo hai chương: Chương 1: Kiến thức chuẩn bị. Chương 2: Ứng dụng nguyên lí khởi đầu cực trị và nguyên lí Dirichlet. 3
CHƯƠNG 1: KIẾN THỨC CHUẨN BỊ 1.1. Lý thuyết tập hợp Tuy mới có hơn 100 năm kể từ khi ra đời nhưng lý thuyết tập hợp đã trở thành cơ sở của toán học hiện đại. Trong thời đại hiện nay, lý thuyết tập hợp cũng đã thâm nhập sâu vào trong toán học phổ thông và trở thành một phần không thể thiếu trong chương trình giảng dạy toán học của nhà trường. Lý thuyết tập hợp được nhà toán học Đức G.Cantor (1845-1918) sáng lập và phát triển nhằm miêu tả các quan hệ toán học của các tập hợp. Trong lý thuyết tập hợp, ông chỉ nghiên cứu những tính chất toán học không phụ thuộc vào nguồn gốc xuất thân của các phần tử mà thôi. Trong cuộc sống ta có rất nhiều ví dụ về tập hợp: Tập hợp các em học sinh của một lớp học, tập hợp các số tự nhiên, tập hợp các tam giác… 1.1.1. Cách biểu diễn tập hợp Thông thường người ta hay biểu diễn một tập hợp M như một phần mặt phẳng được giới hạn bởi một đường cong khép kín. Phần mặt phẳng này được tô màu hoặc đánh dấu để nhận biết được. Mỗi phần tử x của một tập M được kí hiệu bởi x  M và được biểu diễn như một điểm trong phần mặt phẳng được giới hạn đó. Còn khi x không phải là phần tử của tập hợp M thì ta viết x  M. Lợi ích của sự biểu diễn này cho ta hình ảnh trực quan hơn về giao của hai tập hợp cũng như hợp của hai tập hợp. Giao của hai tập hợp A và B cho trước, được kí hiệu là A  B là miền giao của hai phần biểu diễn tương ứng (xem hình bên phải) và hợp của hai tập hợp A và B này, được kí hiệu là A  B là toàn bộ miền mặt phẳng dùng để biểu diễn hai tập hợp này (xem hình bên trái) Về mặt hình thức, ta hay dùng một trong 3 cách sau để biểu diễn tập hợp: a. Liệt kê tất cả các phần tử 4
Chẳng hạn tập hợp tất cả các chữ số trong hệ thập phân: 0,1, 2, 3, 4, 5, 6, 7,8,9 . b. Thông qua quy tắc nhận biết đơn giản Trong phương pháp biểu diễn tập hợp này, người ta chỉ liệt kê vài phần tử đầu tiên của tập hợp để người đọc có thể nhận ra ngay quy tắc nhận biết chúng và dùng dấu “…” để dễ hiểu là còn các phần tử khác nối tiếp theo quy luật đó. Chẳng hạn tập hợp tất cả các số tự nhiên được biểu diễn như sau: N  1, 2, 3, ... . Tập hợp tất cả các số tự nhiên chẵn được biểu diễn như sau: A  2 , 4 , 6 , ... . Đôi khi người ta cũng biểu diễn thông qua quy tắc nhận biết đơn giản như sau: Ví dụ biểu diễn tập các số nguyên: Z  ...,  3,  2,  1, 0,1, 2, 3, ... . c. Thông qua quy luật chung nhận biết các phần tử Chẳng hạn để biểu diễn tập hợp tất cả các số chính phương, ta có thể viết: M : n 2 : n  N  . Thậm chí ta cũng có thể viết đơn giản như sau: M: = { n  N : n là số chính phương}. Trong cách biểu diễn này, quy tắc nhận biết rất có thể đơn giản về hình thức, nhưng khi vận dụng để nhận biết một phần tử có thuộc tâp hợp được biểu diễn hay không là một vấn đề khó khăn. Chẳng hạn tập hợp các số nguyên tố được biểu diễn như sau: P = {p  N: p là số nguyên tố}. Ví dụ 1: Hãy biểu diễn tập hợp tất cả các số thực trên mặt phẳng toạ độ Đề Các. Giải: Tập hợp các số thực trong mặt phẳng là R 2 :  x , y  : x, y  R . 1.1.2. Các kiểu quan hệ tập hợp a. Tập hợp rỗng Tập hợp không có phần tử nào được gọi là tập hợp rỗng và được kí hiệu bởi  . 5
b. Tập hợp hữu hạn Tập hợp có hữu hạn phần tử được gọi là tập hợp hữu hạn.   Ví dụ 2: Tập hợp n số tự nhiên đầu tiên A  1,2,3,...n là tập hợp hữu hạn. c. Tập hợp vô hạn Tập hợp có vô hạn phần tử được gọi là tập hợp vô hạn. Ví dụ 3: Tập hợp các số tự nhiên, các số hữu tỉ, các số thực là các tập hợp vô hạn. d. Tập hợp con Tập hợp A được gọi là tập hợp con của tập hơp B nếu mọi phần tử của A đều là phần tử của B và được kí hiệu A B. Ví dụ 4: Tập hợp tất cả các tập con của tập hợp 1, 2,3 là các tập hợp  , 1 , 2 , 3 , 1,2 , 1,3 , 2, 3 , 1, 2,3 . Nếu A≠B và A B, thì ta nói A là tập con thật sự của B. Tập rỗng là tập con của tất cả các tập hợp. e. Hai tập hợp bằng nhau Hai tập hợp được gọi là bằng nhau nếu mỗi phần tử của tập hợp này là phần tử của tập hợp kia và ngược lại và kí hiệu A=B. Rõ ràng nếu A B và B  A thì A=B f. Hiệu của hai tập hợp Hiệu của hai tập hợp A và B là tập hợp chứa những phần tử thuộc A mà không thuộc B và được kí hiệu là A\ B. Trong biểu diễn bởi các miền mặt phẳng của chúng thì A\ B được tô bởi các đường gạch chéo. Như thường lệ, ta kí hiệu tập hợp tất cả các tập con của một tập hợp A bởi P(A). Ví dụ 5: Cho trước hai tập hợp A và B. Chứng minh rẳng tổng số phần tử của A  B và A  B bằng tổng số phần tử của A và B. Giải: Ta biểu diễn các tập hợp A và B như hình bởi các phần của mặt phẳng bao bởi các đường đóng kín. Giả sử rằng A có n phần tử và B có m phần tử. Nếu A  B có a phần tử thì số phần tử A \ B là n  a phần tử và số phần tử B \ A là m  a phần tử. Tập hợp A  B có:  n  a   a   m  a   n  m  a phần tử. 6
Suy ra tổng số phần tử của A  B và A  B đúng bằng  n  m  a   a  m  n . 1.2. Phương pháp chứng minh phản chứng Phương pháp chứng minh phản chứng là một phương pháp chứng minh khá cổ điển. Phương pháp chứng minh phản chứng được tiến hành các bước như sau: Bước 1: Ta giả sử rằng kết luận của bài toán là sai và mệnh đề ngược lại của kết luận bài toán là đúng. Bước 2: Từ mệnh đề ngược lại kết luận của bài toán, ta suy diễn dựa trên giả thiết cho sẵn của bài toán đi đến một khẳng định rõ ràng là sai hoặc mâu thuẫn với giả thiết ban đầu của bài toán. Bước 3: Kết luận là khẳng định của bài toán là đúng. Rất nhiều bài toán chứng minh trực tiếp có thể dài, nhưng bằng phương pháp chứng minh phản chứng nhiều khi ta có được một chút chứng minh ngắn gọn. Trong chứng minh phản chứng, ta có thêm một giả thiết làm chỗ tựa cho chứng minh (đó là mệnh đề ngược lại với kết luận của bài toán). Đôi khi xuất phát từ giả thiết được tạo thêm này chúng ta dễ suy luận hơn. Ví dụ 6: Biết rằng số  là một số vô tỉ. Chứng minh rằng trong khai triển thập phân của số   3,1415... sẽ có một chữ số xuất hiện vô hạn lần. Giải: Giả sử ngược lại là kết luận của bài toán sai. Khi đó, mỗi chữ số i  0,1, 2,...9 chỉ xuất hiện hữu hạn lần. Giả sử ai là số lần xuất hiện của chữ số i sau dấu phẩy trong khai triển thập phân của số  . 9 Như vậy số  có đúng ai chữ số sau dấu phẩy trong khai triển thập phân của i0 nó. Vậy  phải là một số hữu tỉ (vô lí) vì ta biết rằng số  là một số vô tỉ. Nhận xét: Mặc dù biết rằng trong khai triển thập phân của số  luôn có một chữ số xuất hiện vô hạn lần nhưng cho đến bây giờ các nhà toán học vẫn không biết chính 7
xác đó là chữ số gì. Vì sự tồn tại một chữ số có tính chất như vậy trong khai triển thập phân của số  chỉ được chứng tỏ bằng chứng minh phản chứng mà thôi. Còn khi a là một số hữu tỉ có vô hạn chữ số sau dấu phẩy trong biểu diễn thập phân của nó, thì ta dễ dàng tìm tất cả chữ số xuất hiện vô hạn lần sau dấu phẩy trong biểu diễn thập phân của a . Trong việc chứng minh một số tính chất bằng phương pháp phản chứng, ta có thể có thêm một số thông tin bổ sung quan trọng nếu sử dụng phản ví dụ nhỏ nhất. Ý tưởng là để chứng minh một tính chất A cho một cấu hình P, ta xét một đặc trưng f  P  của P là một hàm có giá trị nguyên dương. Bây giờ giả sử tồn tại một cấu hình P không có tính chất A, khi đó sẽ tồn tại một cấu hình P không có 0 tính chất A với f  P0  nhỏ nhất. Ta sẽ tìm cách suy ra điều mâu thuẫn. Lúc này, ngoài việc chúng ta có cấu hình P không có tính chất A, ta còn có mọi 0 cấu hình P với f  P   f  P0  đều có tính chất A. 1.3. Một số tính chất của phép chia hết Định nhĩa 1.1 phép chia hết: Gải sử a , b là hai số nguyên và b  0 , ta nói b chia hết a hay a chia hết cho b nếu như có một số nguyên q sao cho a  bq . Khi ấy ta còn nói b là ước của a hay a là bội của b và viết a  b . Một số tính chất: i) Nếu a  b và b c thì a  c . ii) Nếu a  b , a  c và  b, c   1 thì a bc . iii) Nếu ab c và  b, c   1 thì a  c . 1.4. Một số tính chất của đồng dư thức Định nghĩa 1.2 đồng dư thức: Cho m là một số nguyên dương, ta nói hai số nguyên a và b đồng dư với nhau theo môđun m nếu trong các phép chia a và b cho m ta được cùng một số dư, nghĩa là có các số q1 , q2 , r  với 0  r  m , sao cho: a  mq1  r . b  mq2  r . Khi a và b đồng dư với nhau theo môđun m ta viết a  b (mod m ). 8
Hệ thức a  b (mod m ) được gọi là đồng dư thức. Một số tính chất: i) a  b (mod m )   a  b  m .  a  b  mod m   a  c  b  d  mod m   ii) Nếu  thì   c  d  mod m    ac  bd  mod m  . 1.5. Một số kiến thức liên quan đến bất đẳng thức 1.5.1. Bất đẳng thức trung bình cộng - trung bình nhân Cho n số thực dương a1 , a2 ,..., an thì trung bình cộng của n số đó lớn hơn hoặc bằng trung bình nhân của chúng, nghĩa là: a1  a2  ...  an n  a1a2 ...an . n Dấu “=” xảy ra khi và chỉ khi a1  a2  ...  an . Chứng minh: Ta dùng phương pháp quy nạp theo n: Với n  2 , ta có chứng minh : a1  a2  a1a2 2  a1  a2  2 a1a2  0 2   a1  a2   0. Bất đẳng thức trên luôn đúng. Để chứng minh bất đẳng thức tổng quát ta xét bất đẳng thức phụ: Nếu x1 , x2    thì x1  x2  x1n1  x2n 1 . Vậy x1 , x2   thì ta luôn có: x 1 n1  x2n1   x1  x2   0  x1n  x2n  x1 x2 n1  x2 x1n 1 . Lấy n số thực không âm x1, x2 ,..., xn  , Viết các bất đẳng thức tương ứng rồi cộng lại ta được: x 1 n  x2    x1n  x3n   ...   x1n  xn    x2n  x3n   ...   x2n  xn   ...   xn1  xnn  n n n n   x1 x2 1  x2 x1n1    x1x3n1  x3 x1n1   ...   x1xn 1  xn x1n1   ...   xn1xn 1  xn xn1  n n n n1 9
 x1  x2 1  x3 1  ...  xn 1   x2  x1n1  x3 1  ...  xn 1   ...  xn  x1n1  x2 1  ...  xn1  n n n n n n n1 Từ đó:  n 1  x1n  x2n  ...  xnn   x1  x2n1  x3n1  ...  xnn1   x2  x1n1  x3n1  ...  xnn1  ...  xn  x1  x2  ...  xn1  (*). n1 n1 n1 Theo giả thiết quy nạp, ta thừa nhận rằng đối với n  1 số thực không âm bất kì, trung bình cộng không nhỏ hơn trung bình nhân của chúng. x2n1  x3n1  ...  xnn 1   n  1 x2 x3...xn . x1n1  x3n1  ...  xnn 1   n  1 x1 x3...xn . …. x1n1  x2n1  ...  xnn11   n  1 x1 x2 ...xn1 .  Sử dụng bất đẳng thức này, (*) tương đương:  n 1  x1n  x2n  ...  xnn   n  n 1 x1x2...xn x1n  x2n  ...  xnn   x1 x2 ...xn . n Ta đặt x1n  a1 , x2n  a2 , ..., xnn  an . Ta được a1  a2  ...  an n  a1a2 ...an . n 1.5.2. Bất đẳng thức Bunyakovsky  Cho n số thực bất kỳ, ai , bi  , i  1, n , ta có:  2  a1b1  a2b2  ...  anbn    a12  a22  ...  an2  b12  b22  ...  bn2  . Dấu “=” xảy ra khi và chỉ khi tồn tại k   sao cho: b1  ka1 , b2  ka2 ,..., bn  kan . Chứng minh : Với  x   , ta có : 2  a1x  b1   0 . 2  a2 x  b2   0 . 10
… 2  an x  bn   0 . Từ đó suy ra: a12 x 2  2a1b1 x  b12  0 . a2 x 2  2a2b2 x  b22  0 . 2 …. an x 2  2anbn x  bn2  0 . 2 Cộng vế theo vế ta đươc: a 2 1  a2  ...  an  x 2  2  a1b1  a2b2  ...  anbn  x   b12  b22  ...  bn2   0 . 2 2 Ta thấy vế trái là một tam thức bậc hai. Đặt: f ( x)   a12  a2  ...  an  x 2  2  a1b1  a2b2  ...  anbn  x   b12  b22  ...  bn2  . 2 2 Với a12  a2  ...  an  0 và f ( x )  0, x   nên nếu a12  a2  ...  an  0 thì: 2 2 2 2 2  '   a1b1  a2b2  ...  anbn    a12  a2  ...  an  b12  b22  ...  bn   0 . 2 2 2 Và thu được bất đẳng thức cần chứng minh. Nếu a12  a2  ...  an  0 thì a1  a2  ...  an  0 khi đó bất đẳng thức cần chứng 2 2 minh luôn đúng. Cuối cùng ta thấy dấu “=” của bất đẳng thức xảy ra khi và chỉ khi:  '  0  a1 x  b1  a2 x  b2  ...  an x  bn  0  b1  ka1  b2  ka2  ...  bn  kan , k  . 1.6. Nguyên lý bù trừ Cho tập X và n tập con X1 , X 2 ,..., X n . Ta có n k 1 X 1  X 2  ...  X n    1 X  n, k  . k 1 Trong đó: X  n, 0   X X  n, k    X i1  X i2  ...  X ik . 1 i1 ... ik  n Chứng minh : Với n  2 , ta có : X 1  X 2  X 1  X 2  X 1  X 2 . 11
Giả sử đúng đến n tức là : n 2 1 X 1  X 2  ...  X n   X k   1  X i  X j  ... k 1 1i  j  n k 1   1  X i1  X i2  ...  X ik  ...  X 1  X 2  ...  X n . 1i1 ...ik  n Ta chứng minh đúng với n  1 , ta có : X 1  X 2  ...  X n  X n 1   X1  X 2  ...  X n   X n 1  X1  X 2  ...  X n  X n1   X1  X 2  ...  X n   X n1 . Ta có: X 1  X 2  ...  X n n k 1 n 1   X k  ...   1  X i1  X i2  ...  X ik  ...   1 X1  X 2  ...  X n k 1 1i1 ...ik  n Và   X 1  X n1    X 2  X n1   ...   X n  X n1  n k 1   X k  X n1  ...   1  X i1  X i2  ...  X ik  X n1  ... k 1 1i1 ...ik  n n 1   1 X1  X 2  ...  X n  X n1 . Khi đó: n n 1  X k  X n1   X k ; k 1 k 1 n   1i  j  n X i  X j   X k  X n1   k 1  1i  j  n 1 Xi  X j ; k 1 k   1  X i1  X i2  ...  X ik  X n1   1  X i1  X i2  ...  X ik ; 1i1 ...ik  n 1i1 ...ik  n 1 n 1 n   1 X1  X 2  ...  X n  X n 1   1 X1  X 2  ...  X n  X n 1 . n k 1 Vậy ta có: X 1  X 2  ...  X n    1 X  n, k  . k 1 Với X  n, k    X i1  X i2  ...  X ik . 1 i1 ... ik  n 12
1.7. Nguyên lí khởi đầu cực trị Nguyên lý khởi đầu cực trị có dạng đơn giản như sau: Nguyên lí 1: Trong một tập hợp hữu hạn 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. Những tập hợp hữu hạn cụ thể hay được xét tới là các tập hợp hữu hạn đoạn thẳng, tập hợp hữu hạn góc, tập hợp diện tích của một số hữu hạn các đa giác, khoảng cách từ một điểm cho trước tới các đoạn thẳng,... 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. Nguyên tắc này dùng để chứng minh những bài toán mà trong tập hợp những giá trị phải xét tồn tại giá trị nhỏ nhất hoặc giá trị lớn nhất. Thông thường nguyên lí khởi đầu cực trị được sử dụng cùng với phương pháp chứng minh phản chứng. Nguyên lí khởi đầu cực trị được vận dụng trong trường hợp tập những giá trị cần phải khảo sát chỉ là một tập hợp hữu hạn (nguyên lí 1) hoặc có thể vô hạn (nguyên lí 2) nhưng tồn tại một phần tử nhỏ nhất (hoặc lớn nhất). Trong khi vận dụng nguyên lí này người ta tiến hành các bước sau Bước 1: Chứng tỏ rằng trong tất cả các giá trị cần khảo sát phải có một giá trị nhỏ nhất hoặc giá trị lớn nhất. Bước 2: Xét bài toán trong trường hợp riêng khi nó nhận giá trị nhỏ nhất (hoặc lớn nhất) này. Bước 3: Chỉ ra một mâu thuẫn hoặc chỉ ra một giá trị còn nhỏ hơn (hoặc lớn hơn) giá trị ta đang khảo sát. 1.8. Nguyên lí Dirichlet 1.8.1. Nội dung nguyên lí Dirichlet Nếu nhốt n  1 con thỏ vào n cái chuồng thì luôn tồn tại một chuồng chứa ít nhất hai con thỏ. 1.8.2. Nguyên lí Dirichlet mở rộng Cũng tương tự như vậy, nguyên lí Dirichlet mở rộng được phát biểu như sau: “Nếu nhốt n con thỏ vào m ( m  2) chuồng thì tồn tại một chuồng có ít nhất  n  m 1  m  con thỏ”.   (  a được dùng để kí hiệu số nguyên lớn nhất không vượt quá số thực a cho trước). 13
Chứng minh: Nguyên lí Dirichlet bằng phản chứng.  n  m 1 Thật vậy, nếu không tồn tại chuồng nào nhốt được   con thỏ.  m   n  m 1   n 1  m   n 1 Nếu     m   m  1 con thỏ thì số thỏ trong mỗi chuồng  m      n  1 luôn nhỏ hơn hoặc bằng   con.  m   n 1 Suy ra tổng số thỏ không vượt quá m.    n 1 con thỏ (mâu thuẫn).  m   n  m 1 Do đó, phải có một chuồng chứa ít nhất   con thỏ.  m  1.8.3. Nguyên lí Dirichlet dạng tập hợp Cho A và B là hai tập hợp khác rỗng có số phần tử hữu hạn, trong đó số lượng phần tử A lớn hơn số lượng phần tử B . Nếu với một quy tắc nào đó, mỗi phần tử của A cho tương ứng với một phần tử của B thì tồn tại ít nhất hai phần tử khác nhau của A mà chúng tương ứng với một phần tử của B . Nguyên lí Dirichlet dạng tập hợp được minh hoạ dưới dạng hình vẽ sau: 1.8.4. Nguyên lí Dirichlet dạng tập hợp mở rộng Giả sử A , B là hai tập hợp hữu hạn và A , B tương ứng kí hiệu là các số lượng phần tử của A và B . Giả sử có một số tự nhiên k nào đó mà A  k . B và ta có quy tắc với mỗi phần tử của A cho tương ứng với một phần tử của B . Khi đó, tồn tại ít nhất k  1 phần tử của A mà chúng ứng với cùng một phần tử của B . 14
1.8.5. Nguyên lí Dirichlet cho diện tích Nếu K là một hình phẳng, còn K1 , K 2 , K3 ,..., K n là các hình phẳng sao cho K i  K , i  1, n và K  K1  K 2  ...  K n (Với K là diện tích hình phẳng K , còn K i là diện tích của hình phẳng K i , i  1, n ) thì tồn tại ít nhất hai hình phẳng Ki , K j với 1  i  j  n  sao cho Ki , K j có điểm trong chung. 15
CHƯƠNG 2: ỨNG DỤNG NGUYÊN LÍ KHỞI ĐẦU CỰC TRỊ VÀ NGUYÊN LÍ DIRICHLET VÀO BÀI TOÁN. 2.1. Nguyên lí khởi đầu cực trị 2.1.1. Ứng dụng vào giải bài toán hình học tổ hợp Bài toán 1: Cho ABC là tam giác nhọn. Lấy một điểm P bất kì trong tam giác. Chứng minh rằng khoảng cách lớn nhất trong các khoảng cách từ P tới ba đỉnh A, B, C không nhỏ hơn hai lần khoảng cách bé nhất trong các khoảng cách từ P tới ba cạnh của tam giác đó. Giải: A C1 B1 P B C A1 Gọi A1 , B1 , C1 tương ứng là hình chiếu của P xuống các cạnh BC , AC , AB . Ta có:   C PB  BPA    CPB  B PA  360 0 . (1) APC1   A1 PC   1 1 1 1 Theo nguyên lý khởi đầu cực trị, tồn tại: max APC1 , C1 PB, BPA1 ,  , CPB1 , B1PA .    A PC    1  Không mất tổng quát, ta giả sử: max  , C1PB, BPA1 ,  , CPB1 , B1PA  BPA1 . (2) APC1   A1PC       Từ (1) và (2) dễ dàng suy ra: BPA1  60 0 . (3)  PA 1 Từ (3) ta đi đến cos  BPA1   1  hay PB  2PA1 . (4) PB 2 Từ (4) suy ra: max  PA, PB, PC  PB  2 PA1  2 min PA1 , PB1 , PC1 (điều phải chứng minh). Bài toán 2: Chứng minh rằng trên mặt phẳng toạ độ Đề Các không thể tìm được năm điểm nguyên là đỉnh của một ngũ giác đều (Điểm nguyên là điểm có cả tung độ lẫn hoành độ đều là các số nguyên). 16