Sejam a 1   , , . . . ,   a n , não todos iguais a 0, tais que ∑ i = 1 n a i = 0   . Mostre que existe uma permutação i 1   , , . . . ,   i n ,   tal que ∑ i = 1 n a i a i j a i j + 1   < 0 . Dica: Use o método probabilístico (é interessante notar que não é necessário que exista uma permutação cuja soma de produtos de pares sucessivos é positiva. Por exemplo, se n   =   3 ,   a 1   =   a 2   =   -   1 ,   e   a 3 ,   =   2 , não existe tal permutação).

Passo 1

Fala galeraaa!

Vamos que vamos!

Defina I j como a variável aleatória que marca o índice na posição $j$ após aplicar uma permutação.

Nós vamos mostrar que

E ∑ j = 1 n a l j   a l j   a l j + 1 - ∑ j = 1 n E ( a l j a _ ( l j + 1 ) < 0

Usando a lei da esperança total, temos que:

E ( a I j   a I j + 1 = ∑ k + l E a I j   a I j + 1   I j = k ,   I J + 1 = l P I j = k ,   I j + 1 = l =           ( * )

Nós sabemos que:

P I j - k ,   I j + 1 = l = 1 n n - 1  

e essa

E a l j   a l j + 1 I j = k ,   I j + 1 = l = E a k a l = a k a l

Portanto,

* = 1 n n - 1 ∑ k + l a k a l = 1 n n - 1 ∑ k   = 1 n a k ∑ l + k a l

Como sabemos que ∑ l - 1 n a l = 0 , temos que ∑ l ≠   k   a l = a k , o que implica em:

1 n n - 1 ∑ k = 1 n a k ∑ l + k a l = 1 n n -   1 ∑ k - 1 n - a k 2   < 0

Isso implica que:

E ∑ j - 1 n a i j a i j + 1 = ∑ j - 1 n E ( a I j a I j + 1 ) < 0

então tem que existir uma permutação tal que ∑ i - 1 n a i + a i + 1 < 0 já que o valor esperado dessa expressão é menor que 0 se considerarmos permutação como aleatório com probabilidades iguais.

Resposta

Seja a permutação aleatória e mostre que o valor esperado da expressão requerida é menor que 0.