Olá Rodrigo,
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.
|AUB| = |A| + |B| - |AinterB|
|A inter {m+1, m+2, ..., m+k}| = |A| + |{m+1, m+2, ..., m+k}| - |A uniao
{m+1, m+2, ..., m+k}|
|A inter {m+1, m+2, ..., m+k}| = |A| + k - |A uniao {m+1, m+2, ..., m+k}|
On Dec 6, 2007 6:19 PM, Rodrigo Cientista <[EMAIL PROTECTED]>
wrote:
> 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<http://www.mat.puc-rio.br/%7Eobmlistas/obm-l.html>
> =========================================================================
>
