Combinatória POTI
Página 1 de 1
Combinatória POTI
por roxasjls Sex 13 Set 2019, 16:47
Ache o maior valor possível da express ̃ao
Ache o maior valor possível da expressão x1x2+x2x3+· · ·+xnx1 para n≥3, onde x1, x2, ..., xn é uma permutação arbitrária dos inteiros 1,2, ..., n.
Solução.Seja Sn(x1, ..., xn) =x1x2+x2x3+· · ·+xnx1 a função acima e Mn seu valor máximo. Como Sn é invariante por permutações cíclicas, podemos escolher aquela em que x1=n. Observe que
Sn(n, x2, ..., xn) =Sn−1(x2, ..., xn)−x2xn+nx2+nxn=Sn−1(x2, ..., xn) +n2−(n−x2)(n−xn) ≤ Mn−1+n2−1·2
em que na primeira igualdade usamos a definição de Sn, na segunda apenas reescremos x2xn+nx2+nxn e na terceira maxizamos o termo−(n−x2)(n−xn) e usamos a definição de Mn−1.Fazendo uma soma telescópica, temos Mn≤M3+ (42−2) + (52−2) +· · ·+ (n2−2)= 11 + (42+ 52+· · ·+n2)−2(n−3) =16(2n3+ 3n2−11n+ 18). Deixaremos a cargo do aluno a comprovação de que a cota obtida é realmente ótima.
Então sábios forumeiros, a 2a fase da OBMEP ta chegando e eu estou passando muitas dificuldades com os PDFs do POTI, o pior é que eu nem tenho um professor que me dê suporte (escola pública). Venho então pedir a ajuda de vocês com esse problema que vem sendo um inconveniente para mim continuar os estudos. Eu não entendi porquê Sn seria invariante por permutações cíclicas, nem o porquê de surgirem tantos termos após trocarmos o Sn por Sn-1. Se alguém puder me passar um bom material de estudo para invariância eu ficaria muito grato, ou até mesmo explicar como chegaram nisso...
Ache o maior valor possível da expressão x1x2+x2x3+· · ·+xnx1 para n≥3, onde x1, x2, ..., xn é uma permutação arbitrária dos inteiros 1,2, ..., n.
Solução.Seja Sn(x1, ..., xn) =x1x2+x2x3+· · ·+xnx1 a função acima e Mn seu valor máximo. Como Sn é invariante por permutações cíclicas, podemos escolher aquela em que x1=n. Observe que
Sn(n, x2, ..., xn) =Sn−1(x2, ..., xn)−x2xn+nx2+nxn=Sn−1(x2, ..., xn) +n2−(n−x2)(n−xn) ≤ Mn−1+n2−1·2
em que na primeira igualdade usamos a definição de Sn, na segunda apenas reescremos x2xn+nx2+nxn e na terceira maxizamos o termo−(n−x2)(n−xn) e usamos a definição de Mn−1.Fazendo uma soma telescópica, temos Mn≤M3+ (42−2) + (52−2) +· · ·+ (n2−2)= 11 + (42+ 52+· · ·+n2)−2(n−3) =16(2n3+ 3n2−11n+ 18). Deixaremos a cargo do aluno a comprovação de que a cota obtida é realmente ótima.
Então sábios forumeiros, a 2a fase da OBMEP ta chegando e eu estou passando muitas dificuldades com os PDFs do POTI, o pior é que eu nem tenho um professor que me dê suporte (escola pública). Venho então pedir a ajuda de vocês com esse problema que vem sendo um inconveniente para mim continuar os estudos. Eu não entendi porquê Sn seria invariante por permutações cíclicas, nem o porquê de surgirem tantos termos após trocarmos o Sn por Sn-1. Se alguém puder me passar um bom material de estudo para invariância eu ficaria muito grato, ou até mesmo explicar como chegaram nisso...
roxasjls- Iniciante
- Mensagens : 1
Data de inscrição : 13/09/2019
Idade : 19
Localização : BH
Página 1 de 1
Permissões neste sub-fórum
Não podes responder a tópicos|
|
|
