eita... desculpe! tava pensando e sem querer apertei um atalho e enviou... hehe ;)
abraços, Salhab On Dec 9, 2007 2:50 AM, Marcelo Salhab Brogliato <[EMAIL PROTECTED]> wrote: > 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> > > ========================================================================= > > > > > >