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.

Nội dung phương pháp cực hạn

Để 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.

Định lý và hệ quả liên quan

Định lý. (Về sự tồn tại điểm cực hạn của tập hợp)

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

Định luật.

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

Hệ quả.

Nếu vai trò của các chỉ số trong tập gồm n số x1, x2, x3,..., xn là như nhau thì có thể giả sử x1 ≤ x2 ≤... ≤ xn.

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 và bất đẳng thức

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 số thực không âm а1,..., аn, có tổng bằng 1, ta có bất đẳng thức

a1a2 + a2a3 +... + an - 1an + anan+1 ≤ 1/4.

Với n chẵn n (n = 2m) điều này có thể chứng minh dễ dàng: đặt a1 + a3 +... + a2m - 1 = a; khi đó, rõ ràng,

a1a2 + a2a3 +... + an - 1an + ana1 ≤ (a1 + a3 +... + a2m−1) × (a2 + a4 +... + a2m) = a(1 − a) ≤

1/4.

Giả sử n lẻ và ak – là số nhỏ nhất trong các số đã cho. (Để thuận tiện, ta giả sử 1 < k <  n

− 1 – điều này không làm mất tính tổng quát  khi n ≥ 4.) Đặt bi = аi, với i = 1,..., k − 1,  bk

= ak + ak + 1 và bi = ai + 1 với i = k + 1,..., n − 1. Áp dụng bất đẳng thức của chúng ta cho các số b1,..., bn - 1, ta được:

a1a2 +... + ak - 2ak - 1 + (ak - 1 + ak + 2) bk + ak + 2ak + 3 +... + an - 1an + ana1 ≤   1/4.

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

ak - 1ak + akak + 1 + ak + 1ak + 2 ≤ ak - 1ak + ak - 1ak + 1 + ak + 1ak + 2 ≤ (ak - 1 + ak + 2) bk.

Nguyên lý cực hạn trong tổ hợp

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ù.

Đây là một ví dụ mà tôi rất thích. 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 (A0, B0) sao cho s(A0) + 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 của s(x) và 2 của các kẻ thù của x trong A0)

Vì x có không 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  (đpcm).

Phương pháp phản ví dụ nhỏ nhất

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ẽ.

Tham khảo

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

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

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