Olimpíadas ⇒ (POTI) Álgebra

[GabrielOBM]

Sejam [tex3]n\gt1[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]n\gt1[/tex3]

inteiro e [tex3]a_1,a_2,...,a_n,b_1,b_2,...,b_n[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]a_1,a_2,...,a_n,b_1,b_2,...,b_n[/tex3]

reais dados com [tex3]a_n\ge a_{n-1}\ge...\ge a_1[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]a_n\ge a_{n-1}\ge...\ge a_1[/tex3]

e [tex3]b_n\ge b_{n-1}\ge ... \ge b_1[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]b_n\ge b_{n-1}\ge ... \ge b_1[/tex3]

. Se [tex3]c_n\ge c_{n-1} \ge ... \ge c_1[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]c_n\ge c_{n-1} \ge ... \ge c_1[/tex3]

são reais positivos com soma 1, prove que:
[tex3]\(\sum c_i a_i\)\(\sum c_ib_i\)\leq \sum c_ia_ib_i[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]\(\sum c_i a_i\)\(\sum c_ib_i\)\leq \sum c_ia_ib_i[/tex3]

.

[mcarvalho]

Boa tarde.

Vou tentar. Gostaria que alguém avaliasse se está correto: não tenho certeza se a resolução valeria para [tex3]a_i,b_i[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]a_i,b_i[/tex3]

negativos.

Inicialmente temos que [tex3]c_1+c_2+...+c_n=1[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]c_1+c_2+...+c_n=1[/tex3]

. Se são todos reais positivos, a conclusão é que: [tex3]0\le c_1\le c_2 \le ...\le c_n \le1[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]0\le c_1\le c_2 \le ...\le c_n \le1[/tex3]

Vamos chamar [tex3]A_i=c_i\cdot a_i[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]A_i=c_i\cdot a_i[/tex3]

e [tex3]B_i=c_i\cdot b_i[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]B_i=c_i\cdot b_i[/tex3]

Queremos provar: [tex3]\sum A_i\ \sum B_i\le \sum \(\frac{A_iB_i}{c_i}\)[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]\sum A_i\ \sum B_i\le \sum \(\frac{A_iB_i}{c_i}\)[/tex3]

Como [tex3]0\le c_i\le 1[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]0\le c_i\le 1[/tex3]

, é razoável assumir que [tex3]\(\frac{A_iB_i}{c_i}\)\ge A_i\cdot B_i[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]\(\frac{A_iB_i}{c_i}\)\ge A_i\cdot B_i[/tex3]

Assim, [tex3]A_i B_i\le \(\frac{A_iB_i}{c_i}\)[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]A_i B_i\le \(\frac{A_iB_i}{c_i}\)[/tex3]

, de onde concluímos, de fato: [tex3]\boxed{\sum A_i\ \sum B_i\le \sum \(\frac{A_iB_i}{c_i}\)}[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]\boxed{\sum A_i\ \sum B_i\le \sum \(\frac{A_iB_i}{c_i}\)}[/tex3]

[Auto Excluído (ID:24303)]

Boa tarde.

Vou tentar. Gostaria que alguém avaliasse se está correto:

Assim, [tex3]A_i B_i\le \(\frac{A_iB_i}{c_i}\)[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]A_i B_i\le \(\frac{A_iB_i}{c_i}\)[/tex3]

, de onde concluímos, de fato: [tex3]\boxed{\sum A_i\ \sum B_i\le \sum \(\frac{A_iB_i}{c_i}\)}[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]\boxed{\sum A_i\ \sum B_i\le \sum \(\frac{A_iB_i}{c_i}\)}[/tex3]

Tá errado.
Não é verdade essa passagem: [tex3]A_i B_i\le \(\frac{A_iB_i}{c_i}\) \implies \sum A_i\ \sum B_i\le \sum \frac{A_iB_i}{c_i}[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]A_i B_i\le \(\frac{A_iB_i}{c_i}\) \implies \sum A_i\ \sum B_i\le \sum \frac{A_iB_i}{c_i}[/tex3]

Seria verdade se fosse:
[tex3]A_i B_i\le \(\frac{A_iB_i}{c_i}\) \implies \sum A_iB_i\le \sum \frac{A_iB_i}{c_i}[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]A_i B_i\le \(\frac{A_iB_i}{c_i}\) \implies \sum A_iB_i\le \sum \frac{A_iB_i}{c_i}[/tex3]

Mas [tex3]\sum A_i \cdot \sum B_i > \sum A_iB_i[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]\sum A_i \cdot \sum B_i > \sum A_iB_i[/tex3]

[mcarvalho]

Verdade, RenetGuenon, obrigado!

[Auto Excluído (ID:24303)]

Essa é a desigualdade generalizada da soma de Chebyshev. É dificílimo encontrar a prova (simples) dela.
https://olimpedia.fandom.com/pt-br/wiki ... _Chebyshev

A ideia é que:
[tex3]\sum_i c_i \cdot (\sum_j c_ja_jb_j) = \frac12 \sum_{i,j} c_ic_j(a_jb_j + a_ib_i) \geq \frac12 \sum_{i,j} c_ic_j(a_ib_j + a_jb_i) = (\sum c_ia_i)(\sum c_j b_j)[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]\sum_i c_i \cdot (\sum_j c_ja_jb_j) = \frac12 \sum_{i,j} c_ic_j(a_jb_j + a_ib_i) \geq \frac12 \sum_{i,j} c_ic_j(a_ib_j + a_jb_i) = (\sum c_ia_i)(\sum c_j b_j)[/tex3]

onde o passo do meio é consequência da deisgualdade: [tex3]a_jb_i + a_ib_j - a_jb_j - a_ib_i = (a_j - a_i)(b_i-b_j) \leq 0[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]a_jb_i + a_ib_j - a_jb_j - a_ib_i = (a_j - a_i)(b_i-b_j) \leq 0[/tex3]

por conta da ordem das sequências.

existe outra prova neste artigo em inglês.

A prova do artigo se faz por "indução" (na real que ela só separa o caso n=1).
[tex3]\sum_{k=1} ^n c_ka_kb_k \geq (\sum_{k=1}^n c_ka_k)(\sum_{k=1}^n c_kb_k)[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]\sum_{k=1} ^n c_ka_kb_k \geq (\sum_{k=1}^n c_ka_k)(\sum_{k=1}^n c_kb_k)[/tex3]

para [tex3]n=1[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]n=1[/tex3]

devemos ter [tex3]c_1 =1[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]c_1 =1[/tex3]

e ficamos com [tex3]ab = a \cdot b[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]ab = a \cdot b[/tex3]

o que é verdade.
Para [tex3]n \ge 2[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]n \ge 2[/tex3]

definimos [tex3]A = \sum_{i=1}^n c_ia_i[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]A = \sum_{i=1}^n c_ia_i[/tex3]

.
Então existe um [tex3]k \in \{1,2,...,n-1\}[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]k \in \{1,2,...,n-1\}[/tex3]

tal que [tex3]a_{k+1} \geq A \geq a_{k}[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]a_{k+1} \geq A \geq a_{k}[/tex3]

(pois do contrário teríamos [tex3]a_n < A[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]a_n < A[/tex3]

mas [tex3]a_n = a_n \sum_{k=1}^{n} c_k = \sum_{k=1}^n a_n c_k \geq \sum_{k=1}^n a_kc_k = A[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]a_n = a_n \sum_{k=1}^{n} c_k = \sum_{k=1}^n a_n c_k \geq \sum_{k=1}^n a_kc_k = A[/tex3]

absurdo).
Então [tex3](a_i-A)(b_i - b_k) \geq 0[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3](a_i-A)(b_i - b_k) \geq 0[/tex3]

para todo [tex3]i \in \{1,2,...,n\}[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]i \in \{1,2,...,n\}[/tex3]

.
Obtemos então [tex3]a_ib_i + Ab_k \geq a_ib_k + Ab_i \iff c_ia_ib_i + Ac_ib_k \geq a_ic_ib_k + Ac_ib_i[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]a_ib_i + Ab_k \geq a_ib_k + Ab_i \iff c_ia_ib_i + Ac_ib_k \geq a_ic_ib_k + Ac_ib_i[/tex3]

e somamos [tex3]i[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]i[/tex3]

indo de [tex3]1[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]1[/tex3]

até [tex3]n[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]n[/tex3]

[tex3]\sum_{i=1}^nc_ia_ib_i + A b_k\sum_{i=1}^nc_i \geq b_k \sum_{i=1}^na_ic_i + A\sum_{i=1}^nc_ib_i[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]\sum_{i=1}^nc_ia_ib_i + A b_k\sum_{i=1}^nc_i \geq b_k \sum_{i=1}^na_ic_i + A\sum_{i=1}^nc_ib_i[/tex3]

ou seja:
[tex3]\sum_{i=1}^nc_ia_ib_i + A b_k \geq b_k A + A\sum_{i=1}^nc_ib_i[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]\sum_{i=1}^nc_ia_ib_i + A b_k \geq b_k A + A\sum_{i=1}^nc_ib_i[/tex3]

[tex3]\sum_{i=1}^n c_ia_ib_i \geq (\sum_{i=1}^n c_ia_i)(\sum_{i=1}^n c_ib_i)[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]\sum_{i=1}^n c_ia_ib_i \geq (\sum_{i=1}^n c_ia_i)(\sum_{i=1}^n c_ib_i)[/tex3]