Este problema é do The Probabilistic Method - N. Alon e J. Spencer. Eu passei pra uma galera e nem eu nem a galera conseguiu resolver...
O máximo que eu consegui foi provar o resultado para uma constante um pouco maior que 1 usando algumas cotas exponenciais.


[ ]'s

Olá!

Tentem fazer este daqui:
Sejam n >= 1 e a_1, ..., a_n reais tais que a_1^2 + ... + a_n^2 = 1.
Sejam e_1, ..., e_n elementos de {-1, 1} escolhidos aleatoriamente de forma uniforme e indendente.
Mostre que Pr[|e_1*a_1 + ... + e_n*a_n| <= 1] >= c para uma constante absoluta c > 0.


Obs: note que c não depende de n e a escolha dos a_i's é arbitrária.

Eu consigo provar que Pr[|e_1*a_1 + ... + e_n*a_n| <= 1] > 0 para todo n >= 1 e toda escolha de a_i's, mas a asserção é mais forte que isso.

[ ]'s

========================================================================= Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =========================================================================

Responder a