Nguyên lý cực hạn

Nguyên lý cực hạn hay còn gọi là nguyên lý khởi đầu cực hạn hay điểm cực hạn, là nguyên lý mà tại điểm mà tại đó một đặc trưng nào đó của đối tượng đang khủng hoảng, hay là có thay đổi về vật chất. Tùy theo trường hợp mà điểm cực hạn có các tên gọi khác nhau. Chẳng hạn "điểm chuyển pha" trong Vật lý; điểm kì dị trong lý thuyết hàm phức; "điểm tới hạn", điểm dừng"khi xét sự biến thiên của hàm số; "điểm gián đoạn" khi xét tính liên tục của hàm số... Các điểm cực hạn của một hệ thống có vai trò quan trọng trong việc khảo sát hệ thống đó. Nguyên lý này đơn giản nhưng có ích rất nhiều trong việc chứng minh, "Hãy xét những trường hợp đặc biệt" là tiêu chí của phương pháp này.

Để khảo sát tính chất nào đó của các phần tử của tập A ta có thể xét tính chất đó tại điểm cực hạn x ∈ A. Do x là điểm cực hạn nên ta có thêm những dữ kiện phụ với x. Từ các kết quả của việc khảo sát tại những điểm cực hạn ta có thể dự đoán chung cho các phần tử của A.

Trong tập gồm hữu hạn phần tử là các số luôn tồn tại phần tử lớn nhất và phần tử nhỏ nhất.

Định lý trên là trường hợp đặc biệt của

Xét tập A gồm hữu hạn phần tử. Mỗi phần tử x A {displaystyle x_{A}} được đặt tương ứng với một trạng thái f ( x ) {displaystyle f(x)} nào đó của nó. Khi đó, nếu mỗi trạng thái f ( x ) {displaystyle f(x)} có một đặc trưng f ( x ) {displaystyle f(x)} và tập các đặc trưng { T ( f ( x ) ) ∣ x A } {displaystyle {T(f(x))mid x_{A}}} có thể sắp xếp thứ tự thì tồn tại M i n ( f ( x ) ) {displaystyle Min(f(x))} và M a x ( f ( x ) ) {displaystyle Max(f(x))}

Nếu vai trò của các chỉ số trong tập gồm n số x 1 , x 2 , x 3 , . . . , x n {displaystyle x_{1},x_{2},x_{3},...,x_{n}} là như nhau thì có thể giả sử x 1 ≤ x 2 ≤ . . . ≤ x n {displaystyle x_{1}leq x_{2}leq ...leq x_{n}}

Một trong những ứng dụng của nguyên lý cực hạn nổi tiếng của Potriagin: "Nếu tồn tại minf(x); maxf(x) thì các giá trị min; max đó thường đạt tại những điểm cực hạn của A."

Nguyên lý cực hạn thường được áp dụng một cách hiệu quả trong các bất đẳng thức có tính tổ hợp, dạng chứng minh tồn tại k số từ n số thỏa mãn một điều kiện này đó.

Ví dụ:

(Moscow MO 1984) Trên vòng tròn người ta xếp ít nhất 4 số thực không âm có tổng bằng 1. Chứng minh rằng tổng tất cả các tích các cặp số kề nhau không lớn hơn 1/4.

Giải.

Ta cần chứng minh rằng với mọi n ≥ 4 {displaystyle ngeq 4} số thực không âm a 1 , a 2 , . . . , a n {displaystyle a_{1},a_{2},...,a_{n}} , có tổng bằng 1, ta có bất đẳng thức:

a 1 a 2 + a 2 a 3 + . . . + a n − 1 a n + a n a n + 1 {displaystyle a_{1}a_{2}+a_{2}a_{3}+...+a_{n-1}a_{n}+a_{n}a_{n+1}} ≤ 1/4.

Với n chẵn ( n = 2 m ) {displaystyle (n=2m)} điều này có thể chứng minh dễ dàng: Đặt a 1 + a 3 + . . . + a 2 m − 1 = a {displaystyle a_{1}+a_{3}+...+a_{2m-1}=a} ; khi đó, rõ ràng,

a 1 a 2 + a 2 a 3 + . . . + a n − 1 a n + a n a n + 1 {displaystyle a_{1}a_{2}+a_{2}a_{3}+...+a_{n-1}a_{n}+a_{n}a_{n+1}} ≤ ( a 1 + a 3 + . . . + a 2 m − 1 ) {displaystyle (a_{1}+a_{3}+...+a_{2m-1})} ( a 2 + a 4 + . . . + a 2 m ) {displaystyle (a_{2}+a_{4}+...+a_{2m})} = a ( 1 − a ) ≤ 1 4 {displaystyle a(1-a)leq {frac {1}{4}}} (1).

Giả sử n lẻ và a k {displaystyle a_{k}} là số nhỏ nhất trong các số đã cho.

(Để thuận tiện, ta giả sử 1 < k < n − 1 {displaystyle 1<k<n-1} - điều này không làm mất tính tổng quát khi n ≥ 4 {displaystyle ngeq 4} .)

Đặt b i = a i {displaystyle b_{i}=a_{i}} , với i = 1, 2,...,k - 1, b k = a k + a k + 1 {displaystyle b_{k}=a_{k}+a_{k+1}} và b k = a k + 1 {displaystyle b_{k}=a_{k+1}} với i = k + 1,k + 2,..., n − 1. Áp dụng bất đẳng thức (1) cho các số b 1 , b 2 , . . . , b n {displaystyle b_{1},b_{2},...,b_{n}} , ta được:

a 1 a 2 + . . . + a k − 2 a k − 1 + ( a k − 1 + a k + 2 ) b k + a k + 2 a k + 3 + . . . + a n − 1 a n + a n a 1 ≤ 1 4 {displaystyle a_{1}a_{2}+...+a_{k-2}a_{k-1}+(a_{k-1}+a_{k+2})b_{k}+a_{k+2}a_{k+3}+...+a_{n-1}a_{n}+a_{n}a_{1}leq {frac {1}{4}}}

Cuối cùng, ta sử dụng bất đẳng thức:

a k − 1 a k + a k a k + 1 + a k + 1 a k + 2 ≤ a k − 1 a k + a k − 1 a k + 1 + a k + 1 a k + 2 ≤ ( a k − 1 + a k + 2 ) b k {displaystyle a_{k-1}a_{k}+a_{k}a_{k+1}+a_{k+1}a_{k+2}leq a_{k-1}a_{k}+a_{k-1}a_{k+1}+a_{k+1}a_{k+2}leq (a_{k-1}+a_{k+2})b_{k}}

Vì vậy: a 1 a 2 + . . . + a k − 2 a k − 1 + a k − 1 a k + a k a k + 1 + a k + 1 a k + 2 + a k + 2 a k + 3 + . . . + a n − 1 a n + a n a 1 ≤ {displaystyle a_{1}a_{2}+...+a_{k-2}a_{k-1}+a_{k-1}a_{k}+a_{k}a_{k+1}+a_{k+1}a_{k+2}+a_{k+2}a_{k+3}+...+a_{n-1}a_{n}+a_{n}a_{1}leq }

a 1 a 2 + . . . + a k − 2 a k − 1 + ( a k − 1 + a k + 2 ) b k + a k + 2 a k + 3 + . . . + a n − 1 a n + a n a 1 ≤ 1 4 {displaystyle a_{1}a_{2}+...+a_{k-2}a_{k-1}+(a_{k-1}+a_{k+2})b_{k}+a_{k+2}a_{k+3}+...+a_{n-1}a_{n}+a_{n}a_{1}leq {frac {1}{4}}} (theo (1)).

Ta có điều phải chứng minh.

Trên đây chúng ta đã xem xét các ví dụ áp dụng của nguyên lý cực hạn trong Mảnh đất màu mỡ nhất dành cho nguyên lý cực hạn. Nguyên lý cực hạn có thể được ứng dụng để chứng minh một quá trình là dừng (trong bài toán liên quan đến biến đổi trạng thái), trong bài toán về đồ thị, hay trong các tình huống tổ hợp đa dạng khác. Các đối tượng thường được đem ra để xét cực hạn thường là: đoạn thẳng ngắn nhất, tam giác có diện tích lớn nhất, góc lớn nhất, đỉnh có bậc lớn nhất, chu trình có độ dài ngắn nhất ...

Ví dụ 14. 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ù.

Có nhiều cách giải khác nhau nhưng ở đây chúng ta sẽ trình bày một cách giải sử dụng nguyên lý cực hạn. Ý tưởng tuy đơn giản nhưng có rất nhiều ứng dụng (trong nhiều bài toán phức tạp hơn).

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 ( A 0 , B 0 ) {displaystyle (A_{0},B_{0})} sao cho s ( A 0 ) + s ( B 0 ) {displaystyle s(A_{0})+s(B_{0})} 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 A 0 {displaystyle A_{0}} có ít nhất 2 kẻ thù trong A 0 {displaystyle A_{0}} . Khi đó ta thực hiện phép biến đổi sau: Chuyển x từ A 0 {displaystyle A_{0}} sang B 0 {displaystyle B_{0}} để được cách chia mới là A' = A0 {x} và B' = B0 {x}. Vì x có ít nhất 2 kẻ thù trong A 0 {displaystyle A_{0}} và A' không còn chứa x nên ta có:

s ( A ′ ) {displaystyle s(A')} £ s ( A 0 ) − 4 {displaystyle s(A_{0})-4} (trong tổng mất đi ít nhất 2 của s(x) và 2 của các kẻ thù của x trong A 0 {displaystyle A_{0}} )

Vì x có không quá 3 kẻ thù và có ít nhất 2 kẻ thù trong A 0 {displaystyle A_{0}} nên x có nhiều nhất 1 kẻ thù trong B 0 {displaystyle B_{0}} (hay B ′ {displaystyle B'} ), cho nên

s ( B ′ ) {displaystyle s(B')} £ s ( B 0 ) + 2 {displaystyle s(B_{0})+2}

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 P0 không có 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 P0 không có tính chất A, ta còn có mọi cấu hình P với f(P) < f(P0) đều có tính chất A.

Ví dụ 3. Cho ngũ giác lồi ABCDE trên mặt phẳng toạ độ có toạ độ các đỉnh đều nguyên.

a) Chứng minh rằng tồn tại ít nhất 1 điểm nằm trong hoặc nằm trên cạnh của ngũ giác (khác với A, B, C, D, E) có toạ độ nguyên.

b) Chứng minh rằng tồn tại ít nhất 1 điểm nằm trong ngũ giác có toạ độ nguyên.

c) Các đường chéo của ngũ giác lồi cắt nhau tạo ra một ngũ giác lồi nhỏ A1B1C1D1E1 bên trong. Chứng minh rằng tồn tại ít nhất 1 điểm nằm trong hoặc trên biên ngũ giác lồi A1B1C1D1E1.

Câu a) có thể giải quyết dễ dàng nhờ nguyên lý Dirichlet: Vì có 5 điểm nên tồn tại ít nhất 2 điểm X, Y mà cặp toạ độ (x, y) của chúng có cùng tính chẵn lẻ (ta chỉ có 4 trường hợp (chẵn, chẵn), (chẵn, lẻ), (lẻ, chẵn) và (lẻ, lẻ)). Trung điểm Z của XY chính là điểm cần tìm.

Sang câu b) lý luận trên đây chưa đủ, vì nếu XY không phải là đường chéo mà là cạnh thì Z có thể sẽ nằm trên biên. Ta xử lý tình huống này như sau. Để ý rằng nếu XY là một cạnh, chẳng hạn là cạnh AB thì ZBCDE cũng là một ngũ giác lồi có các đỉnh có toạ độ đều nguyên và ta có thể lặp lại lý luận nêu trên đối với ngũ giác ZBCDE, ... Ta có thể dùng đơn biến để chứng minh quá trình này không thể kéo dài mãi, và đến một lúc nào đó sẽ có 1 ngũ giác có điểm nguyên nằm trong.

Tuy nhiên, ta có thể trình bày lại lý luận này một cách gọn gàng như sau: Giả sử tồn tại một ngũ giác nguyên mà bên trong không chứa một điểm nguyên nào (phản ví dụ). Trong tất cả các ngũ giác như vậy, chọn ngũ giác ABCDE có diện tích nhỏ nhất (phản ví dụ nhỏ nhất). Nếu có nhiều ngũ giác như vậy thì ta chọn một trong số chúng. Theo lý luận đã trình bày ở câu a), tồn tại hai đỉnh X, Y có cặp toạ độ cùng tính chẵn lẻ. Trung điểm Z của XY sẽ có toạ độ nguyên. Vì bên trong ngũ giác ABCDE không có điểm nguyên nào nên XY phải là một cạnh nào đó. Không mất tính tổng quát, giả sử đó là AB. Khi đó ngũ giác ZBCDE có toạ độ các đỉnh đều nguyên và có diện tích nhỏ hơn diện tích ngũ giác ABCDE. Do tính nhỏ nhất của ABCDE (phản ví dụ nhỏ nhất phát huy tác dụng!) nên bên trong ngũ giác ZBCDE có 1 điểm nguyên T. Điều này mâu thuẫn vì T cũng nằm trong ngũ giác ABCDE.

Phản ví dụ nhỏ nhất cũng là cách rất tốt để trình bày một chứng minh quy nạp (ở đây thường là quy nạp mạnh), để tránh những lý luận dài dòng và thiếu chặt chẽ.

Tài liệu giáo khoa chuyên toán Đại số 10 -Đoàn Quỳnh [1]

Nguyên lý cực hạn -Trần Nam Dũng[2]

Một số chuyên đề Đại số bồi dưỡng học sinh giỏi THPT -Võ Đại Mau[3]

1. ^ "Tài liệu chuyên toán 10 Đại số".
2. ^ [vie.math.ac.vn/~mathclub/TranNamDung_Nguyen_Ly_Cuc_Han.pdf "Nguyên lý cực hạn - Viện Toán học"] (PDF). {{Chú thích web}}: Kiểm tra giá trị |url= (trợ giúp)
3. ^ "CÁC CHUYÊN ĐỀ TOÁN HỌC BỒI DƯỠNG HỌC SINH GIỎI" (PDF).