Vui lòng bật JavaScript để tiếp tục sử dụng Website!

Kỹ thuật phân tách Chebyshev

  1. Chia sẻ trang này

    Tác giả: LTTK CTV28
    Đăng lúc: 10/6/19
    Trong nhiều trường hợp, ta cần đưa các BDT về một dạng chuẩn để việc sử dụng BDT chebyshev đạt hiệu quả tối đa. Xin giới thiệu với mọi người các cách phân tích BDT về dạng "chebyshev” thường được dùng:
    Ta sẽ cố gắng đưa bài toán BDT về các dạng :
    $C_1x+C_2y+C_3z \geq 0$
    Trong đó:
    $x=a-b, y=b-c, z=c-a $và các hoán vị(1)
    $x=ka+mb-nc, y=kb+mc-na, z=kc+ma-nb$ và các hoán vị với $x+y+z=t(a+b+c)$ và $t \geq 0$.(2)
    $x=a^2-bc, y=b^2-ca, z=c^2-ab$ và các hoán vị.(3)
    $x=(a-b)(a-c), y=(b-c)(b-a), z=(c-a)(c-b)$ và các hoán vị.(4)
    $x=(a-b)^2, y=(b-c)^2, z=(c-a)^2$(5)

    Các biểu thức $C_1, C_2, C_3$ phụ thuộc vào việc phân tách thành $x,y,z$.
    Ý nghĩa của việc phân tách:
    Ta thường sử dụng các cách phân tách (1), (4) và (5) vì khi đó sau khi đã áp dụng BDT chebyshev thì ta được BDT về dạng: $(C_1+C_2+C_3)(x+y+z)$ lớn hoặc bé hơn 0. Do đó, với các $x,y,z$ như trên thì ta có thể yên tâm về điều kiện dấu bằng xảy ra tại $a=b=c$ tức ba biến bằng nhau.
    Vậy phân tách như thế nào cho hợp lí và gọn nhẹ? Ta có thể trả lời câu hỏi trên một cách dễ dàng vì thực ra, với PP SOS thì việc phân tách thành (1), (5) đã được chứng thực là rất dễ thực hiện (dẫu vậy vẫn nên lưu ý rằng, cách phân tích (1) có thể khác rất xa cách phân tích (5), không đơn thuần là ta phân tích (5) rồi lấy ra hạng tử $(a-b), (b-c), (c-a)$ để nhân vào $C_1, C_2, C_3$). Còn với kiểu phân tích (4) thì hẳn các bạn cũng nhận ra đó chính là dạng quen thuộc của BDT schur. Tóm lại, việc phân tích này là có thể thực hiện được không mấy khó khăn. Nhưng quan trọng là ta phân tích thế nào và ra sao để có thể sắp thứ tự các biến một cách dễ dàng. Đây chính là mấu chốt của tất cả các kĩ thuật.
    Ví dụ vể việc phân tách chebyshev:

    Bài toán 1:
    (Old and New Inequalities)

    Cho $x+y+z=1$ và $0 \leq x,y,z \leq 1$. CMR:
    $\dfrac{1}{1+x^2}+\dfrac{1}{1+y^2}+\dfrac{1}{z^2+1} \leq \dfrac{27}{10}$
    Lời giải:Không mất tính tổng quát giả sử: $x \geq y \geq z$
    BDT tương đương:
    $\sum (\dfrac{9}{10}-\dfrac{1}{1+x^2}) \geq 0$
    $\leftrightarrow \sum \dfrac{3x-1}{10} . (\dfrac{3x+1}{1+x^2}) \geq 0$
    Nhìn vào BDT bên trên, các bạn cũng có thể thấy ngay dạng quen thuộc của chebysev.
    Bây giờ chúng ta sẽ thực hiện bước sắp xếp thứ tự các biến:
    Ta có: $x=3x-1 \geq y=3y-1 \geq z=3z-1$ và:
    $C_1=\dfrac{3x+1}{1+x^2} \geq C_2=\dfrac{3y+1}{1+y^2} \geq C_3=\dfrac{3z+1}{1+z^2}$
    Thật vậy:
    $\dfrac{3x+1}{1+x^2} - \dfrac{3y+1}{1+y^2}$
    $=\dfrac{(3x+1)(1+y^2)-(3x+1)(x^2+1)}{(1+x^2)(1+y^2)}$
    $=\dfrac{(x-y)(3-3xy-x-y)}{(1+x^2)(1+y^2)}$
    $=\dfrac{(x-y)(2x+2y+3z-3xy)}{(1+x^2)(1+y^2)}$
    Mà $x-y \geq 0$ (cách sắp thứ tự ban đầu) và:
    $2x+2y+3z > x+x+y \geq 3 \sqrt[3]{x^2y} \geq 3xy$ (do $x,y \leq 1$)
    Vậy: $\dfrac{3x+1}{1+x^2} \geq \dfrac{3y+1}{1+y^2}$
    Tương tự:
    $C_1=\dfrac{3x+1}{1+x^2} \geq C_2=\dfrac{3y+1}{1+y^2} \geq C_3=\dfrac{3z+1}{1+z^2}$
    Đến đây thì ta có thể sử dụng BDT chebysev:
    $C_1.x+C_2.y+C_3.z \geq \dfrac{1}{3}.(x+y+z)(C_1+C_2+C_3)=0$
    Vậy ta có điều phải chứng minh.

    Bài toán 2: (Tatami)

    Cho $x_1, .. , x_n$ là các số thực không âm, $ max(x_i+x_j) \leq n-1$ và $\sum x_i + \sum (x_i)^2 \leq 2n$. CMR:
    $\sum \dfrac{1}{n+1-x_i} \leq 1$
    Lời giải:
    Phân tích bài toán về dạng chebysev:
    $\sum (\dfrac{1}{n} - \dfrac{1}{n+1-x_i}) \geq 0$
    $\leftrightarrow (1-x_i)(x_i+2). (\dfrac{1}{(x_i+2)(n+1-x_i)}) \geq 0$
    Sắp thứ tự các biến:
    $x_1 \geq x_2 \geq .. \geq x_n$
    $(1-x_1)(x_1+2) \leq (1-x_2)(x_2+2) \leq .. \leq (1-x_n) (x_n+2) \\ \dfrac{1}{(x_1+2)(n+1-x_1)} \leq ..\leq \dfrac{1}{(x_n+2)(n+1-x_n)} $
    Áp dụng BDT chebysev, ta có:
    $VT \geq ( 2n - \sum x_i + \sum (x_i)^2)(A) \geq 0$
    (Do điều kiện và $A \geq 0$)
    Ta có DPCM.

    Bài toán 3: (posted by manilo-mathlinks.ro)

    Cho $a,b,c >0$. CMR:
    $\sum \dfrac{a^2+2bc}{b^2+c^2} \geq 3$
    Lời giải:
    BDT về dạng chebysev:
    $ (a+c-b). \dfrac{a+b-c}{b^2+c^2} + (b+c-a). \dfrac{a+b-c}{c^2+a^2} + (c+b-a). \dfrac{c+a-b}{a^2+b^2} \geq 0$
    Sắp thứ tự các biến: giả sử: $a \geq b \geq c$
    $\rightarrow \dfrac{a+b-c}{b^2+c^2} \geq \dfrac{a+b-c}{c^2+a^2} \geq \dfrac{c+a-b}{a^2+b^2}\\{a+c-b \geq b+c-a \geq c+b-a}$
    Áp dụng BDT chebysev, có ngay điều phải chứng minh!

    Ngoài các cách phân tích và áp dụng trực tiếp BDT chebyshev như trên, lắm lúc, ta phải biến đổi để các lượng $C_1, C_2, C_3$ hoặc $x,y,z$ phù hợp hơn. Việc đó được thực hiện bằng cách nhân và chia một lượng phù hợp. Mời các bạn theo dõi một số ví dụ sau:

    Bài toán 4:

    Cho $ a+b+c=3$. CMR:
    $ \dfrac{1}{9-ab}+\dfrac{1}{9-bc}+\dfrac{1}{9-ca} \leq \dfrac{3}{8}$
    Lời giải : (Phạm Kim Hùng)
    BĐT về dạng Chebyshev:
    $ \sum \dfrac{1-ab}{9-ab} \geq 0$
    Đặt $ x=bc, y=ac, z=ab$
    BĐT tương đương:
    $ \sum \dfrac{(1-x)(6+x)}{(6+x)(9-x)} \geq 0$
    Sắp thứ tự các biến: Gỉa sử: $ x \geq y \geq z$ ta có:
    $(1-x)(6+x) \leq (1-y)(6+y) \leq (1-z)(6+z)$
    và $ \dfrac{1}{(6+x)(9-x)} \leq \dfrac{1}{(6+y)(9-y)} \leq \dfrac{1}{(6+z)(9-z)}$
    Theo BĐT Chebyshev, ta có:
    $VT \geq \dfrac{1}{3}.(3-x^2-y^2-z^2)(\sum \dfrac{1}{(6+x)(9-x)})$
    Theo đk ban đầu: $ x^2+y^2+z^2=(ab)^2+(bc)^2+(ca)^2 \leq a+b+c=3$
    Vậy muốn: $VT \geq \dfrac{1}{3}.(3-x^2-y^2-z^2)(\sum \dfrac{1}{(6+x)(9-x)}) \geq 0$ ta cần chứng minh:
    $\sum \dfrac{1}{(6+x)(9-x)} \geq 0$
    BĐT trên có thể dễ dàng chứng minh!

    Bài toán 5: Cho $a,b,c>0 .$
    CMR:
    $\dfrac{a}{a^{2}+bc}+\dfrac{b}{b^{2}+ca}+\dfrac{c}{c^{2}+ab}\leq \dfrac{3(a+b+c)}{2(ab+bc+ca)}$

    BDT tương đương với

    $\sum(\dfrac{a(ab+bc+ca)}{a^2+bc}-a) \le \dfrac{a+b+c}{2}$
    Hay
    $\sum\dfrac{a^2(b+c-a)}{a^2+bc} \le \dfrac{a+b+c}{2}$
    Hay
    $\sum(\dfrac{2a^2}{a^2+bc}-1)(b+c-a) \le 0$
    Hay
    $\sum\dfrac{bc-a^2}{a^2+bc}(b+c-a)\ge 0$
    Hay
    $\sum(bc-a^2)(b+c)\dfrac{(b+c-a)}{(b+c)(a^2+bc)}\ge 0$
    Áp dụng BDT chebyshev, ta có DPCM

    Hai ví dụ trên thật đặc sắc. Nếu biết áp dụng đúng lúc thì kĩ thuật này sẽ hỗ trợ rất nhiều cho chúng ta.

    Mặc dù có trong tay các công cụ phân tích mạnh mẽ như vậy, ta vẫn dễ dàng nhận ra rằng với các bai toán hoán vị thì chỉ đơn thuần áp dụng các dạng phân tích sẽ chẳng thể làm được gì. Bởi lẽ vấn đề mấu chốt trong việc áp dụng BDT chebyshev là sắp thứ tự các đại lượng. Nếu như sắp được thứ tự các đại lượng rồi mà chúng lại ko có dạng $C_1x+C_2y+C_3z$ thì sao? Để khỏa lấp chỗ trống đó, chúng ta củng thử xem một ý tưởng đơn giản sau:

    I.Các tiêu chuẩn bổ sung của BDT chebysev:

    Ta sẽ xét tất cả các mối quan hệ của các bộ hoán vị, cùng với DK của chúng, giúp cho việc sử dụng dễ dàng hơn. Xét các bộ hoán vị sau:
    $ C_1x+C_2y+C_3z(1)$
    $ C_1x+C_2z+C_3y(2)$
    $ C_1y+C_2x+C_3z(3)$
    $ C_1y+C_2z+C_3x(4)$
    $ C_1z+C_2x+C_3y(5)$
    $ C_1z+C_2y+C_3x(6)$
    Và so sánh chúng với: $S=\dfrac{(a+b+c)(x+y+z)}{3}$

    Lẽ dĩ nhiên là ta không thể so sánh trực tiếp các bộ hoán vị ở trên với S mà phải thông qua một số điều kiện. Nhưng thật thú vị vì các điều kiện ấy không hề làm cản trở ta trong việc chứng minh, nếu có chỉ là một chút phức tạp hóa trong cách trình bày bài toán. Để minh chứng cho điều đó, tôi sẽ trình bày ngay các điều kiện đó ra đây:

    Cho 2 dãy tăng:
    $C_1 \geq C_2 \geq C_3 $
    và $x \geq y \geq z$, ta có được:
    $1/ C_1x+C_2y+C_3z \geq S$ với mọi $a,b,c,x,y,z$
    $2/ C_1x+C_2z+C_3y \geq S \leftrightarrow \begin{cases} C_1+C_3 \geq 2C_2 \\x+z \geq 2y \end{cases}$
    $3/ C_1y+C_2x+C_3z \geq S \leftrightarrow \begin{cases}2C_2 \geq C_1+C_3 \\2y \geq x+z \end{cases} $
    $4/ C_1y+C_2z+C_3x \leq S \leftrightarrow \begin{cases}2C_2 \geq C_1+C_3 \\x+z \geq 2y \end{cases}$
    $5/ C_1z+C_2x+C_3y \leq S \leftrightarrow \begin{cases} C_1+C_3 \geq 2C_2 \\2y \geq x+z\end{cases}$
    $6/ C_1z+C_2y+C_3x \leq S$ với mọi $C_1,C_2,C_3,x,y,z$

    Nhìn qua điều kiện cho phép các bổ đề $2, 3, 4 , 5$ hoạt động, ta thấy ngay rằng chỉ cần một trong $2$ điều kiện đúng là bài toán được thỏa mãn.
    Vậy ta đã xử lí xong một vấn đề khá quan trọng trong các điểm yếu của BDT chebyshev: Với mọi bài toán sau khi đã phân tích và sắp thứ tự các biểu thức: $C_1, C_2, C_3$ và x,y,z thì ta hoàn toàn có thể áp dụng cheby để xử lí (với lưu ý là có nhiều hơn một cách phân tích về dạng chuẩn tắc)

    Vấn đề cuối cùng của BDT chebyshev: sắp thứ tự các biến. Đây là một vấn đề khó và hóc búa nhất khi muốn áp dụng BDT cheby. Mình xin nêu ra một số kĩ thuật nữa, trong tầm hạn chế để giải quyết vấn đề này.
    1/ Kĩ thuật chia trường hợp giao miền:
    Ý tưởng của kĩ thuật này có thể phát biểu đơn giản như sau: Nhiều khi ta chia bài toán thành hai hoặc nhiều trường hợp nhỏ để xử lí, những trường hợp đó không nhất thiết phải nằm trên hai miền khác nhau của bài toán mà có thể trùng lên nhau, nhưng phải đảm bảo là hội của hai trường hợp đó bao quát hết toàn bộ bài toán.

    Ví dụ: Thay vì chia bài toán thành hai trường hợp là: $ a+c \geq 2b$ và $ 2b \geq a+c$ thì ta có thể chia thành $ ac \geq b^2$ và $ 2b \geq a+c$. Cách chia như trên vẫn đúng bởi hợp của hai trường hợp là toàn bộ tập xác định của a,b,c(tức với mọi a,b,c) nhưng nó còn cung cấp cho ta thêm dữ kiện bởi điều kiện $ ac \geq b^2$ mạnh hơn điều kiện $ a+c \geq 2b$
    Trước khi đến với các ví dụ của PP, ta hãy xem xét một làm mạnh của BDT chebyshev và suy ngẫm về nó nào:

    BDT chebyshev làm mạnh:
    Cho hai dãy:
    $ a \dfrac{a+b}{2} \geq \dfrac{a+b+c}{3}$ và $ x \geq\dfrac{x+y}{2} \geq \dfrac{x+y+z}{3}$ thì:
    $ 3(ax+by+cz) \geq (a+b+c)(x+y+z)$

    Chứng minh: Tương tự BDT chebyshev cổ điển.
    (Với bài toán tổng quát đã được giải quyết bằng tổng Abel, mình xin phép ko nêu ra ở đây)

    Sau đây là các ví dụ kinh điển cho PP này:

    Bài toán 6: (Old and New Inequalities)

    Cho $a,b,c >0$. CMR:
    $\sum \dfrac{a}{b} \geq \sum (\dfrac{c+a}{c+b})$
    Lời giải:
    Phân tích về dạng chebysev:
    $\sum (a-b). \dfrac{c}{c+b} \geq 0$
    Sắp thứ tự các biến:
    Xét $2TH$:
    $Th1: a \geq b \geq c $. Trong trường hợp này ta xét 2 trường hợp con:
    $a/ ac \geq b^2 \rightarrow a+c \geq 2b $
    $\rightarrow x=(a-b) \geq y=(b-c) \geq z=(c-a)$ và
    $C_1=\dfrac{a}{c+a} \geq C_2=\dfrac{c}{c+b} \geq C_3=\dfrac{b}{b+a}$
    BĐT có dạng:
    $C_1y+C_2x+C_3z \geq 0$
    Áp dụng tiêu chuẩn 3/ của phần một, ta có:
    $C_1y+C_2x+C_3z \geq \dfrac{(x+y+z)}{3}. (C_1+C_2+C_3)=0 (1_a)$
    v ới: $2y \geq x+z \leftrightarrow 2(b-c) \geq c-b$ (đ úng)
    V ậy $(1_a)$ đ úng.
    $b/ a+c \leq 2b \rightarrow ac \leq b^2$
    $\rightarrow x=(b-c) \geq y=(a-b) \geq z=(c-a)$ và
    $C_1=\dfrac{a}{c+a} \geq C_2=\dfrac{b}{b+a} \geq C_3=\dfrac{c}{c+b}$
    BĐT có dạng:
    $C_1x+C_2z+C_3y \geq 0$
    Áp dụng tiêu chuẩn $2/$ ở phần một, ta có:
    $C_1x+C_2z+C_3y \geq \dfrac{(x+y+z)}{3}. (C_1+C_2+C_3)=0 (1_b)$
    với: $C_1+C_3 \geq 2C_2 \leftrightarrow \dfrac{a}{c+a} + \dfrac{c}{c+b} - 2. \dfrac{b}{b+a} = \dfrac{(a-b)(ab+c^2+2c(a+b))}{(a+b)(b+c)(c+a)} \geq 0$.( đúng)
    Vậy $(1_b)$ đúng.
    Th2: $b \geq a \geq c$.
    Xét các trường hợp con như trên, ta cũng dễ dàng có DPCM.

    Bài toán 7: (Bùi Việt Anh-www.diendantoanhoc.net)

    $ \dfrac{a+b}{c}+\dfrac{b+c}{a}+\dfrac{c+a}{b} \geq 6(\dfrac{a^2+b^2+c^2}{ab+bc+ca})$ với $2b \geq a+c$
    Lời giải:
    Bất đẳng thức về dạng chebysev:
    $(a-b)^2(\dfrac{c(a+b)-2ab}{ab})+(b-c)^2(\dfrac{a(b+c)-2bc}{bc}+(c-a)^2(\dfrac{b(c+a)-2ca}{ac}) \geq 0$(1)
    Sắp thứ tự các biến: giả sử: $ a \geq b \geq c$
    $x=(a-c)^2, y=(b-c)^2, z= (a-b)^2$
    Dễ có: $C_1=\dfrac{a(b+c)-2bc}{bc}, C_2=\dfrac{b(a+c)-2ac}{ac}, C_3=\dfrac{c(a+b)-2ab}{ab}$
    Vậy BĐT cần chứng minh có dạng:
    $C_1y + C_2x + C_3z \geq 0$(2)
    Ta sẽ chứng minh BĐT sau:
    $C_1y + C_2x + C_3z \geq (x+y+z)(C_1+C_2+C_3)$(3)
    Theo tiêu chuẩn 3 phần một, ta có BĐT trên đúng khi và chỉ khi:
    $2y \geq x+z $
    $\leftrightarrow \dfrac{2(b(a+c)-2ac)}{ac}-\dfrac{a(b+c)-2bc}{bc}-\dfrac{c(a+b)-2ab}{ab} \geq 0$
    $ \leftrightarrow \dfrac{(2b-a-c)(ab+bc+ca)}{abc} \geq 0$
    BĐT trên đúng theo đk đề bài.
    Vậy (3) đúng.
    Ta tiếp tục chứng minh rằng:
    $(x+y+z)(C_1+C_2+C_3) \geq 0$
    Thật vậy: $x+y+z \geq 0$(do $x,y,z \geq 0$ và:
    $C_1+C_2+C_3=\dfrac{a^2b+b^2c+c^2a+b^2a+c^2b+a^2c -6abc}{abc}\geq 0$(Theo BĐT AM-GM)
    Từ trên ta có DPCM.