PROBLEMA 2:
Dado um inteiro positivo n, mostre que existe um inteiro positivo N com a
seguinte propriedade: se A é um subconjunto de {1,2,...,N} com pelo menos N/2
elementos, então existe um inteiro positivo m<= N - n tal que |A interseção
com {m+1, m+2,..., m+k}|>=k/2
para todo k = 1, 2, …, n.
**************************************************************************************************************************
(gostaria de comentários sobre esta demonstração, falhas, se conhecem alguma
demonstração pra esse problema, pois ainda não tem o gabarito)
suponha existir x > N - n tal que |A interseção com {x+1, x+2,..., x+k}|>=k/2
como x + n > N, pelo menos um elemento de {x+1, x+2,..., x+k} será maior que
qualquer elemento de A; escolhendo-se um n = 1, a afirmação acima é falsa
assim, se |A interseção com {m+1, m+2,..., m+k}|>=k/2 ==> existe m <= N - n
chamemos S = {m+1, m+2,..., m+k}
m + n <= N ==> m + k <= N para todo k = 1, 2, …, n ==>
==> S é subconjunto de {1,2,...,N}, ou é o próprio conjunto {1,2,...,N} na
hipótese em que N = n
quando N = n é trivial que |A interseção com {m+1, m+2,..., m+k}|>=k/2 (= k/2
na verdade)
suponha N > n ==> N/2 > n/2 ==> |{1,2,...,N}| > |S| ==> |A| > |S|/2 = n/2
como S está contido em {1,2,...,N} ==> é sempre possível tomar-se um
subconjunto A de {1,2,...,N} tal que S/2 esteja contido em A
Abra sua conta no Yahoo! Mail, o único sem limite de espaço para
armazenamento!
http://br.mail.yahoo.com/
=========================================================================
Instru��es para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=========================================================================
