Sejam não todos iguais a 0, tais que . Mostre que existe uma permutação tal que . 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ão existe tal permutação).
Passo 1
Fala galeraaa!
Vamos que vamos!
Defina 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
Usando a lei da esperança total, temos que:
Nós sabemos que:
e essa
Portanto,
Como sabemos que , temos que , o que implica em:
Isso implica que:
então tem que existir uma permutação tal que 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.