7. Cực trị trên tập rời rạc
7.1 Phương pháp xây dựng cấu trúc của điểm mà tại đó đạt Min, Max
Dự đoán Min, Max của biểu thức \(f(x)\) đạt tại \(x^*\) nào đó và chứng minh dự đoán đó.
Trong phương pháp này thường ta phải sử dụng các kiến thức của Số học, Tổ hợp và Toán rời rạc. Việc dự đoán thường được thực hiện bởi phép quy nạp dựa vào một số tính toán ban đầu.
7.2 Ví dụ minh hoạ
Hãy xác định \(\operatorname{Max} f(n)\).
Lời giải. Gọi \(f(n)\) là số các đường chéo có thể kẻ được thoả mãn yêu cầu bài ra. Xét một số trường hợp ban đầu của \(n\). Bằng cách vẽ hình cụ thể ta được:
| \(n =\) | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|
| \(f(n) \le\) | 2 | 3 | 5 | 6 | 8 | 9 | 11 |
Từ đó ta có dự đoán:
\[ f(n) \le \left[\frac{3n}{2}\right] - 4 \quad (*) \]Trong đó ta ký hiệu \([x]\) là số nguyên lớn nhất không vượt quá \(x\). Để chứng minh \((*)\) trước hết ta chứng minh bổ đề sau:
Bổ đề: Nếu tập \(S\) các đường chéo của một \(n\)-giác lồi (\(n \ge 5\)) chia \(n\)-giác đó thành các tam giác thì có ít nhất một đường chéo \(\in S\) không cắt tất cả các đường chéo khác \(\in S\) tại điểm trong của \(n\)-giác đã cho.
Chứng minh: Xét các hình vẽ cấu trúc.
Từ các hình vẽ trên ta có các nhận xét hiển nhiên sau:
1) Không có đường chéo nào \(\in S\) cắt \(\ge 2\) đường chéo \(\in S\) khác (xem Hình 1). Do hai góc \(\alpha; \beta\) có \(\alpha + \beta \ge 180^\circ\).
2) Giả sử mọi đường chéo \(\in S\) đều cắt đúng một đường chéo \(\in S\). Xét hai đường chéo \(\in S\) là \(AC; BD\) cắt nhau tại \(O\) (xem Hình 2). Do \(n \ge 5\) nên có ít nhất một cạnh của tứ giác \(ABCD\) là đường chéo của \(n\)-giác đã cho. Giả sử đó là cạnh \(AB\). Ta có \(AB \in S\) vì nếu không thì phần \(n\)-giác với biên chứa đường gấp khúc \(AOB\) sẽ không là tam giác nên sẽ có một đường chéo \(\in S\) cắt \(AB\), khi đó đường chéo đó còn cắt hoặc \(AC\), hoặc \(BD\). Điều đó trái với nhận xét 1) (Có một đường chéo \(\in S\) cắt hai đường chéo \(\in S\)).
Từ hai nhận xét trên suy ra kết luận của bổ đề.
Trở lại bài toán đang xét. Hiển nhiên, \((*)\) đã đúng với \(n = 4; 5; 6\). Giả sử \((*)\) đúng với mọi \(k, 5 \le k < n, n \ge 6\). Theo bổ đề, tồn tại một đường chéo \(\in S\) không cắt các đường chéo khác \(\in S\) và chia \(n\)-giác đã cho thành hai phần rời nhau. Giả sử đường chéo đó là \(A_1A_q\) (xem Hình 3) và nó chia \(n\)-giác đã cho thành \(p\)-giác và \(q\)-giác (với \(3 \le p, q < n; p + q = n + 2\)).
Khi đó, số \(f(n)\) các đường chéo kẻ được thoả mãn yêu cầu bài ra là:
\[ f(n) = 1 + f(p) + f(q) \]Theo giả thiết quy nạp ta có:
\[ 1 + f(p) + f(q) \le 1 + \left[\frac{3p}{2}\right] - 4 + \left[\frac{3q}{2}\right] - 4 \]\[ = \left[\frac{3p}{2}\right] + \left[\frac{3q}{2}\right] - 7 \]\[ \le \left[\frac{3(p+q)}{2}\right] - 7 \]\[ = \left[\frac{3n}{2} + 3\right] - 7 = \left[\frac{3n}{2}\right] - 4 \]\[ \Rightarrow f(n) \le \left[\frac{3n}{2}\right] - 4. \]Vậy \((*)\) cũng đúng với \(n\).
Do đó, theo nguyên lý quy nạp, \((*)\) đúng với mọi \(n \in \mathbb{N}; n \ge 4\). Vậy số lớn nhất các đường chéo kẻ được thoả mãn yêu cầu bài ra là \(\left[\frac{3n}{2}\right] - 4\).