Tương đương với nguyên lý qui nạp là nguyên lý cực hạn, trong dó cụ thể bằng một số tính chất sau:
Tính chất (tiên đề)
- Một tập con hữu hạn khác rỗng của tập số thực luôn tồn tại phần tử nhỏ nhất và phần tử lớn nhất.
- Mọi tập con khác rỗng của $\mathbb{R}$ bị chặn trên đều tồn tại chặn trên nhỏ nhất.
- Mọi tập con khác rỗng của $\mathbb{R}$ bị chặn dưới đều tồn tại chặn dưới lớn nhất.
Trong nhiều bài toán, việc chọn đối tượng cực hạn (lớn nhất hoặc nhỏ nhất) giúp ta thuận lợi trong suy luận. \
Cũng như quy nạp, cực hạn cũng có nhiều ứng dụng rộng rãi trong các việc giải quyết các bài toán tổ hợp.
Ví dụ 1. Tìm $n$ lớn nhất sao cho tồn tại $n$ điểm mà 3 điểm bất kì đều tạo thành tam giác vuông.
Lời giải
Ta thấy $n=3, n=4$ đều tồn tại. Ta chứng minh $n\geq 5$ thì không tồn tại. \\
Giả sử ngược lại, tồn tại 5 điểm, sao cho 3 điểm bất kì đều tạo thành tam giác vuông. Khi đó ta chọn hai điểm sao cho có độ dài lớn nhất. Khi đó các điểm còn lại đều nằm trên đường tròn đường kính là đoạn thẳng này. Khi đó 3 điểm thuộc 2 nửa đường tròn, khi đó có ít nhất 2 điểm cùng thuộc một nửa, từ đó tồn tại một tam giác khác vuông có đỉnh là 2 điểm này cùng một điểm thuộc đường kính. Do đó không thỏa đề bài.
Bài toán này có nhiều các để tiếp cận, việc tìm ra $n=5$ không có gì khó, khi chứng minh $n=5$ không thỏa cũng có nhiều cách suy luận, tuy vậy việc chọn đoạn thẳng có độ dài lớn nhất giúp ta dễ dàng suy ra mâu thuẫn.
Ví dụ 2. Trên một mặt bàn đặt một số các đồng xu với kích cỡ không giống nhau đôi một (các đồng xu không được đè lên nhau và phải nằm sấp hoặc ngửa trên bàn). Chứng minh rằng dù ta đặt như thế nào đi nữa, cũng luôn tồn tại một đồng xu chỉ tiếp xúc được với nhiều nhất 5 đồng xu khác.
Lời giải
Chọn đồng xu có bán kính nhỏ nhất, thì đồng xu này chỉ tiếp xúc không quá 5 đồng xu khác. Giả sử nó có thể tiếp xúc với 6 đồng xu khác. Khi đó $A$ là tâm đường tròn, tâm các đường tròn còn lại là $A_1, \cdots, A_6$. Khi đó tồn tại $A_iA_{i+1} \leq 60^\circ$, suy ra $A_iA_{i+1} < AA_i$ vô lý, vì bán kính của $(A)$ là nhỏ nhất.
Ví dụ 3. Cho $n$ điểm trong mặt phẳng biết rằng cứ 3 điểm bất kì tạo thành một tam giác có diện tích không lớn hơn 1. Chứng minh rằng $n$ điểm thuộc một hình tam giác có diện tích không lớn hơn 4.
Lời giải
Gọi $A, B, C$ là 3 điểm tạo thành tam giác sao cho $ABC$ có diện tích lớn nhất. Từ $A, B, C$ vẽ các đường song song với các cạnh đối diện, các đường thẳng cắt nhau tại $A’, B’, C’$ ta chứng minh các điểm thuộc cạnh hoặc miền trong tam giác $A’B’C’$.
Thật vậy, nếu có điểm nào nằm ngoài tam giác $A’B’C’$ thì điểm đó kết hợp với hai trong 3 điểm $A, B, C$ sẽ có diện tích lớn hơn diện tích tam giác $ABC$, vô lý.
Do $S_{A’B’C’} = 4S_{ABC} \leq 4$.
Ví dụ 4. (Sylvester) Trong mặt phẳng cho $n$ điểm phân biệt, sao cho mỗi đường thẳng đi qua hai điểm thì đi qua ít nhất một điểm khác. Chứng minh rằng $n$ điểm này cùng thuộc một đường thẳng.
Lời giải
Giả sử không phải tất cả các điểm cùng thuộc một đường thẳng. Khi đó ta xét khoảng cách từ một điểm đến đường thẳng qua ít nhất 3 điểm, trong các khoảng cách này có khoảng cách nhỏ nhất. Giả sử $P$ là điểm có khoảng cách từ $P$ đến $d$ là nhỏ nhất, với $d$ là đường thẳng qua các điểm $A, B, C$ theo thứ tự. \\
Gọi $H$ là hình chiếu của $P$ trên $d$, $D, E$ là hình chiếu của $A, B$ trên $B$ trên $PA, PC$. Nếu $H$ thuộc tia $BA$ thì $BE < PH$, nếu $H$ thuộc đoạn $BC$ thì $BD < PH$. Mâu thuẫn với $PH$ là nhỏ nhất. \\
Vậy tất cả các điểm cùng thuộc một đường thẳng.
Trên đây là một định lý kinh điển với lời giải cực hạn cũng đi vào các sách giáo khoa về tổ hợp, việc chọn khoảng cách nhỏ nhất đó là một ý tưởng khá độc đáo, giúp giải quyết bài toán rất nhanh.
Việc chọn đối tượng cực hạn phụ thuộc vào bài toán và hướng đi kế tiếp, có được điều này cần rèn luyện thêm trong việc giải toán.
Ví dụ 5. Cho 3 trường, mỗi trường có $n$ học sinh, biết rằng cứ mỗi học sinh thì quen ít nhất $n + 1$ học sinh của hai trường khác. Chứng minh rằng có thể chọn được từ mỗi trường một bạn sao cho 3 bạn này đôi một quen nhau.
Lời giải
Giả sử 3 trường là $X, Y, Z$. Tồn tại một người có số người quen ở cùng một trường khác là nhiều nhất, giả sử $A$ thuộc $X$ có số người quen ở trường $Y$ nhiều nhất là $k$. Khi đó số người quen của $A$ ở $Z$ ít nhất là $n+1-k$. Nếu nhóm người quen $A$ ở $Z$ quen với số người quen $A$ ở $X$ có hai người quen nhau thì ta có điều chứng minh.\\
Ngược lại xét người quen $A$ ở $Z$, đặt là $B$ quen số người ở $Y$ tối đa là $n-k$, khi đó $B$ quen ở $X$ ít nhất là $n+1 – (n-k) = k+1$, mâu thuẫn với cách chọn $A$. (Mâu thuẫn).
Ví dụ 6. Một bữa tiệc có 10 học sinh tham gia, biết rằng mỗi học sinh quen với ít nhất là 5 người. Chứng minh rằng có thể sắp xếp 10 học sinh ngồi vào một bàn tròn sao cho hai người kế nhau thì quen nhau.
Lời giải
Giả sử chuỗi người quen dài nhất có độ dài là $k$, $A_1A_2…A_k$, ta thấy các người còn lại không ai quen $A_1, A_k$ nên suy ra $k \geq 6$. \\
Nếu $k = 6$, suy ra $A_1$ và $A_6$ quen nhau, khi đó trong các người còn lại $A_7$ quen một trong cái người giả sử là $A_i$, khi đó ta có chuỗi $A_7A_iA_{i-1}A_1A_6A_{i+1}$ có độ dài hơn 6, vô lý.\\
Nếu $k =7$, khi đó $A_1$ quen từ $A_2$ đến $A_6$ và $A_7$ quen $A_2$ tới $A_6$, khi đó có một vòng $A_2A_7A_6A_5A_4A_3A_1A_2$. Khi đó sẽ có một người trong nhóm còn lại thì ta sẽ có chuỗi dài hơn, mâu thuẫn.\\
Nếu $k=8,9$ xét tương tự, ta sẽ có $k=10$. Giả sử có chuỗi $A_1\cdots A_{10}$. Khi đó tồn tại $k>i$ sao cho $A_1$ quen $A_k$ và $A_{10}$ quen $A_i$, khi đó có cách xếp thỏa đề bài là $A_1A_k\cdot A_iA_{10}A_9…A_k$.
Ví dụ 7. Một bảng $2n \times 2n$ ô, người ta đánh dấu bất kì $3n$ ô trong bảng. Chứng minh rằng tồn tại $n$ dòng và $n$ cột sao cho $3n$ ô được đánh dấu thuộc $n$ dòng và $n$ cột này.
Lời giải
Chọn $n$ dòng sao cho số ô được tô là lớn nhất, ta chứng minh rằng số ô được tô trong $n$ dòng này là không ít hơn $2n$ ô. \\
Thực vậy giả sử số ô được tô là ít hơn $2n$, khi đó $n$ dòng còn lại có nhiều hơn $n$ ô được tô, nên có ít nhất một một dòng có 2 ô được tô. Do đó $n$ dòng đã chọn, mỗi dòng ít nhất 2 ô được tô nên tổng số ô hơn hoặc bằng $2n$ (mâu thuẫn).\\
Vậy ta chỉ cần chọn $n$ cột chứa các ô được tô màu nhưng chưa được chọn trong $n$ dòng trên thì sẽ có điều cần chứng minh.
Bài tập rèn luyện
Bài 1. Có $(2n + 1)$ người đứng trên cùng một mặt phẳng, khoảng cách giữa họ không giống nhau. Sau đó mỗi người bắn người gần họ nhất. Chứng minh rằng:
a) Có ít nhất một người còn sống.
b) Không ai bị bắn quá năm viên đạn.
c) Các đường đạn không cắt nhau.
Bài 2. Một hành tinh có 20 quốc gia. Trong ba nước bất kỳ, luôn có hai nước không thiết lập quan hệ ngoại giao với nhau. Chứng minh rằng, hành tình này có tối đa 200 đại sứ quán.
Bài 3. Với $2n + 3$ điểm trong mặt phẳng, ba điểm bất kỳ không thẳng hàng và bốn điểm bất kỳ không cùng nằm trên một đường tròn. Chứng minh rằng ta có thể chọn ba điểm và vẽ được một đường tròn qua ba điểm đó. Trong $2n$ còn lại, có $n$ điểm nằm trong đường tròn và $n$ điểm nằm ngoài đường tròn.
Bài 4. Điền các số từ 1 đến $n^2$ vào bảng vuông $n \times n$. Chứng minh rằng có hai ô kề nhau (kề cạnh hoặc kề đỉnh) mà hiệu của chúng không nhỏ hơn $n + 1$.
Bài 5. Có $N(N \geq 3)$ chơi tenis vòng tròn một lượt. Cuối giải người ta thấy rằng không có ai thắng tất cả các trận thi đấu. Chứng minh rằng có thể tìm được 3 người A, B, C sao cho A thắng B, B thắng C và C thắng A.
Bài 6. Cho $a, b$ là hai số tự nhiên nguyên tố cùng nhau.
Gọi $d=(a,b)$. Khi đó tồn tại các số nguyên $x, y$ sao cho $$xa+yb=d$$
Like this:
Like Loading...