Re: [obm-l] segunda fase - nível universitário 2007
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
> > =
> >
> >
>
>
Re: [obm-l] segunda fase - nível universitário 2007
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
> =
>
Res: [obm-l] boa de combinatoria
Ok, Ralph,
Respondi dizendo que atentei para minha distração logo que enviei a resposta
anterior. Mas não conhecia essa solução que você apresentou. De fato, muito
interessante.
Um abraço,
Eduardo
- Mensagem original
De: Ralph Teixeira <[EMAIL PROTECTED]>
Para: obm-l@mat.puc-rio.br
Enviadas: Sexta-feira, 7 de Dezembro de 2007 17:01:06
Assunto: Re: [obm-l] boa de combinatoria
Hmmm... infelizmente, uma função "não-decrescente" não é o mesmo que "uma
função que não é decrescente" -- é, eu concordo que é uma péssima péssima
péssima denominação, mas foi assim que os matemáticos convencionaram...
Uma função decrescente é uma que satisfaz f(x)>f(y) sempre que x wrote:
Olá, Vitório,
Me parece que a resolução é a seguinte:
a) Funções crescentes;
Basta que, do contradomínio com m elementos, selecionem-se n. A cada seleção,
associa-se uma única função crescente, e vice-versa. Asim, a resposta é Cm,n.
Observe que, quando m
Para: obm-l
Enviadas: Quinta-feira, 6 de Dezembro de 2007 17:01:58
Assunto: [obm-l] boa de combinatoria
Caros colegas...
Seja In = {1,2,...,n}, analogamente Im, determinar o número de funções f: In
--> Im tais que:
a) f seja crescente
b) f seja não-decrescente
desde já grato
Abra sua conta no Yahoo! Mail, o único sem limite de espaço para armazenamento!
Abra sua conta no Yahoo! Mail, o único sem limite de espaço para
armazenamento!
http://br.mail.yahoo.com/
Res: Res: [obm-l] boa de combinatoria
Olá, Vitório,
Sinto dizer, mas foi só clicar em enviar, ontem, que percebi que minha resposta
estava errada! Para o número de funções crescentes e decrescentes, de fato o
resultado é Cm,n. Mas para a contagem de funções não decrescentes, o resultado
que exibi não está correto. De fato, isso ocorre porque uma função não
decrescente não é uma função que não é decrescente. Na verdade, uma função é
dita não decrescente se, de um termo para outro (maior), obtemos uma imagem
igual ou maior. Ainda não consegui pensar numa solução, mas consegui pensar
numa relação com contagem de seqüências:
Seja f : {1,2,3,...,n} -> {1,2,3,...,m}. Contar o número de funções não
decrescentes f equivale a contar o número de n-seqüências (seqüências de n
dígitos) formadas por algarismos compreendidos entre 1 e m, tais que o
algarismo de uma dada posição da seqüência é sempre maior do que ou igual aos
algarismos das posições precedentes. Por exemplo, se m=2 e n=3, podemos pensar
na seqüência 122, que leva 1 em 1, 2 em 2 e 3 em 2. Além desta, temos: 111, 112
e 222, ou seja, 4 funções, nesse caso. E isso não bate com a fórmula exibida.
Abraço,
Eduardo
- Mensagem original
De: vitoriogauss <[EMAIL PROTECTED]>
Para: obm-l
Enviadas: Sexta-feira, 7 de Dezembro de 2007 15:17:56
Assunto: Re:Res: [obm-l] boa de combinatoria
Tão simples asimm !
Eu pensei nisso... mas não acreditei...
Obrigado
Olá, Vitório,
>
> Me parece que a resolução é a seguinte:
>
> a) Funções crescentes;
>
> Basta que, do contradomínio com m elementos, selecionem-se n. A cada seleção,
> associa-se uma única função crescente, e vice-versa. Asim, a resposta é Cm,n.
> Observe que, quando m
>
> b) Funções não decrescentes;
>
> Analogamente, o total de funções decrescentes é Cm,n (de fato, observe que, a
> cada função crescente, associa-se uma única função decrescente, e
> vice-versa). Como o total de funções (de qualquer tipo) é m^n, temos que o
> valor procurado é m^n - Cm,n.
>
> Espero ter ajudado, um abraço!
> Eduardo L. Estrada
>
> - Mensagem original
> De: vitoriogauss
> Para: obm-l
> Enviadas: Quinta-feira, 6 de Dezembro de 2007 17:01:58
> Assunto: [obm-l] boa de combinatoria
>
> Caros colegas...
>
>
>
>
>
> Seja In = {1,2,...,n}, analogamente Im, determinar o número de funções f: In
> --> Im tais que:
>
>
>
>
>
> a) f seja crescente
>
>
>
> b) f seja não-decrescente
>
>
>
> desde já grato
>
>
>
>
>
>
>
> Abra sua conta no Yahoo! Mail, o único sem limite de espaço para
> armazenamento!
> http://br.mail.yahoo.com/
Vitório Gauss
Abra sua conta no Yahoo! Mail, o único sem limite de espaço para
armazenamento!
http://br.mail.yahoo.com/
