[obm-l] Um de combinatória.

["Domingos Jr." <dopikas@xxxxxxxxxx>]

Seja ct : {0,1}^(2n) -> [n] definida como segue.
Para todo x != y em {0,1}^n temos ct(x, x) = n e ct(x, y) = min{j | x_j 
!= y_j}.

Prove que para todo A contido em {0,1}^n temos |ct(A, A)| >= lg |A|,
onde lg é o logaritmo na base 2.

Abraços.
=========================================================================
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
=========================================================================