Re: [obm-l] Re: [obm-l] Problema Combinatória

[MauZ]

Então Fernando,

eu concordo com você nesse aspecto,
mas a questão é que a formula funcionou para os casos pequenos que testei

no caso de 24 e 5 livros seriam n=24 e p=5
No caso de 5 livros e 3 para escolher a formula traz resposta = 1, o que é
verdade.
Testei alguns outros e deu OK.

Mas justamente tem essa falha q vc enunciou.

Abraços

Em 30/03/08, fernandobarcel <[EMAIL PROTECTED]> escreveu:
>
>
> > (sendo o primeiro binomio como pelo menos 2 consecutivos, o segundo com
> pelo
> > menos 3, etc...
>
>
>
> Não entendi o que você fez, mas acho que isso aí tá errado, pois PELO
> MENOS 2 CONSECUTIVOS engloba o
> PELO MENOS 3 CONSECUTIVOS.
>
> No problema original (tirar 5 de 24 livros), quanto valem N e P na sua
> fórmula?
> E que valor você conseguiu pra resposta?
>
>
>
> =
> 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] Problema Combinatória

[MauZ]

Olá pessoal

eu montei um esquema usando binomio de newton.

Ficou da seguinte forma a resposta:
Vou usar (a//b) como binomio a!/b!(a-b)!

temos todas as combinações como: (n//p)
e as que tem consecutivos como: (n-1//p-1)+(n-2//p-2)...(n-p+1//n-p),
somando pela regra da diagonal: (n//p-1)-1
(sendo o primeiro binomio como pelo menos 2 consecutivos, o segundo com pelo
menos 3, etc... Da segunte forma. a primeira escolha pego 1 livro e
imediatamente o seu da direita. Num grupo de 24 livros por ex, tenho 23
maneiras de fazer isso, pelo fato do ultimo livro nao ter nada à sua
direita)

logo a solução é:

(n//p)-(n//p-1) + 1

testei para alguns valores e tá OK,,

O que vocês acham?

[]'s
Maurizio

Em 27/03/08, Rogerio Ponce <[EMAIL PROTECTED]> escreveu:
>
> Ola' Mauricio e colegas da lista,
> os 5 livros retirados determinam 6 intervalos , dos quais o mais 'a
> esquerda e o mais 'a direita podem ter o valor minimo de 0, e os
> outros quatro valem no minimo 1.
>
> Para uniformizar tudo, podemos imaginar que exista um livro a mais do
> lado direito, e outro do lado esquerdo da estante, de forma que agora
> precisamos determinar 6 intervalos, todos maiores que zero, somando um
> total de 24+2-5 = 21.
>
> Em outras palavras, o que procuramos e' o numero de solucoes inteiras
> positivas para
>   a+b+c+d+e+f=21
> que vale C(21-1, 6-1) = C(20,5)
> Ou seja, (20*19*18*17*16) /  (5*4*3*2*1) =  15504
>
> []'s
>
> Rogerio Ponce
>
>
>
>
> Em 26/03/08, MauZ<[EMAIL PROTECTED]> escreveu:
>
> > Olá a todos!
> >
> > Numa estante com 24 livros, de quantas maneiras posso retirar 5 livros
> sem
> > ter nenhum consecutivo? E no caso de n livros, quantas maneiras retiro p
> > livros sem ter nenhum consecutivo?
> >
> >
> >
> > Pra completar vou colocar parte da minha tentativa de solução, preciso
> de
> > ajuda pra saber se está certo até onde fiz e como finalizar pois
> empaquei.
> >
> > Fiz dessa forma: Todas Combinações - Combinações c/ Consecutivos
> >
> > Todas: 24!/5!19!
> > Consecutivos: 23!/4!19! + 22!/3!19! + 21!/2!19! + 20!/1!19!
> >
> > Fiz uma formula geral com n e p e deu o seguinte:
> >
> >  n!/p!(n-p!) - [(n-1)!/(p-1)!(n-p)! +
> > (n-2)!/(p-2)!(n-p)!+...+(n-p+1)!/(n-p)!]
> >
> > Fatorando deu:
> >
> > (1/(n-p)!)[n!/p!-(n-1)!/(p-1)!-(n-2)!/(p-2)-...-(n-p+1)!/(n-p)!]
> >
> > Dae empaquei de vez... Não consegui continuar!
> >  Quem souber fazer por favor me dê a luz! Ou simplesmente indique o erro
> no
> > meu raciocínio.
> >
> > Agradeço antecipadamente,
> > Maurizio
> >
> >
>
>
> =
> 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] Problema Combinatória

[Rogerio Ponce]

Ola' Mauricio e colegas da lista,
os 5 livros retirados determinam 6 intervalos , dos quais o mais 'a
esquerda e o mais 'a direita podem ter o valor minimo de 0, e os
outros quatro valem no minimo 1.

Para uniformizar tudo, podemos imaginar que exista um livro a mais do
lado direito, e outro do lado esquerdo da estante, de forma que agora
precisamos determinar 6 intervalos, todos maiores que zero, somando um
total de 24+2-5 = 21.

Em outras palavras, o que procuramos e' o numero de solucoes inteiras
positivas para
 a+b+c+d+e+f=21
que vale C(21-1, 6-1) = C(20,5)
Ou seja, (20*19*18*17*16) /  (5*4*3*2*1) =  15504

[]'s
Rogerio Ponce



Em 26/03/08, MauZ<[EMAIL PROTECTED]> escreveu:
> Olá a todos!
>
> Numa estante com 24 livros, de quantas maneiras posso retirar 5 livros sem
> ter nenhum consecutivo? E no caso de n livros, quantas maneiras retiro p
> livros sem ter nenhum consecutivo?
>
>
>
> Pra completar vou colocar parte da minha tentativa de solução, preciso de
> ajuda pra saber se está certo até onde fiz e como finalizar pois empaquei.
>
> Fiz dessa forma: Todas Combinações - Combinações c/ Consecutivos
>
> Todas: 24!/5!19!
> Consecutivos: 23!/4!19! + 22!/3!19! + 21!/2!19! + 20!/1!19!
>
> Fiz uma formula geral com n e p e deu o seguinte:
>
>  n!/p!(n-p!) - [(n-1)!/(p-1)!(n-p)! +
> (n-2)!/(p-2)!(n-p)!+...+(n-p+1)!/(n-p)!]
>
> Fatorando deu:
>
> (1/(n-p)!)[n!/p!-(n-1)!/(p-1)!-(n-2)!/(p-2)-...-(n-p+1)!/(n-p)!]
>
> Dae empaquei de vez... Não consegui continuar!
>  Quem souber fazer por favor me dê a luz! Ou simplesmente indique o erro no
> meu raciocínio.
>
> Agradeço antecipadamente,
> Maurizio
>
>

=
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] Problema Combinatória

[Ralph Teixeira]

Seja G(m,n) o número de maneiras de escolher m livros não consecutivos
a partir de um conjunto com n livros (supomos que eles são todos
diferentes e estão em fila na estante). onde m,n>=1.

Condições de contorno: G(1,n)=n (pois há n maneiras de escolher 1
livro dentre n deles); por outro lado, para m>1, temos G(m,1)=G(m,2)=0
(não dá para escolher 2 ou mais livros não-consecutivos num conjunto
com apenas 1 ou 2 livros).

A partir daí, tenho uma recorrência: para escolher m livros de n, você
tem duas opções:
a) Incluir o livro 1; então você não pode incluir o livro 2, e, assim,
ainda tem que escolher m-1 dos n-2 livros restantes. Assim, há aqui
G(m-1,n-2) maneiras de fazer isto.
b) Não incluir  o livro 1; então você tem que escolher m dos n-1
restantes; há G(m,n-1) maneiras de fazer isto.
Como as maneiras em (a) e (b) são disjuntas, temos a recorrência:
G(m,n)=G(m,n-1)+G(m-1,n-2)

Então juntando tudo:
G(m,n)=G(m,n-1)+G(m-1,n-2) para m>=2 e n>=3
G(1,n)=n para n>=1
G(m,1)=G(m,2)=0 para m>=1

Bom, joguei isto no Calc do OpenOffice... e estou vendo uma espécie de
Triângulo de Pascal deformado... H...

Ah, já sei. Seja f(x,y)=G(m,n) onde m=x-y e n=2x-y-1 (ou, se você
preferir, x=n-m+1 e y=n-2m+1). A recorrência e as condiçõaes de
contorno acima tranformam-se em condições em f que são idênticas
àquelas que definem o triângulo de Pascal, isto é, f(x,y)=C(x,y).
Então a resposta é que G(m,n)=C(n-m+1,n-2m+1). Ou, se você preferir,
mostre por indução que esta última fórmula vale...

Desculpa o final curto e meio grosso, mas acabou meu tempo. :)   Eu
ainda queria ver se tinha alguma solução verdadeiramente combinatória
que levasse à reposta, mas fica para depois.

Ah, e, se eu não errei nada, a resposta à pergunta original é
G(5,24)=C(20,15)=15504 -- há 15504 maneiras de escolher 5 livros não
consecutivos a partir de uma fila com 24. Perdão, sem tempo de checar
tudo, espero não ter escrito besteiras homéricas.

Abraço,
 Ralph

2008/3/27 Johann Peter Gustav Lejeune Dirichlet <[EMAIL PROTECTED]>:
> São 24 livros de assuntos distintos? E os livros estão grudados na
> estante (se o de Teoria da Computação está do lado de Linguagens
> Formais, eles sempre estarão lado a lado?)
> Bem, seria algo como escolher cinco números não-consecutivos do conjunto
> {1,2,3,4\ldots,24}.
> Acho que dá pra usar alguma recursão.
> Vou pensar um pouco antes de continuar...
>
> Em 26/03/08, MauZ<[EMAIL PROTECTED]> escreveu:
> > Olá a todos!
> >
> > Numa estante com 24 livros, de quantas maneiras posso retirar 5 livros sem
> > ter nenhum consecutivo? E no caso de n livros, quantas maneiras retiro p
> > livros sem ter nenhum consecutivo?
> >
> >
> >
> > Pra completar vou colocar parte da minha tentativa de solução, preciso de
> > ajuda pra saber se está certo até onde fiz e como finalizar pois empaquei.
> >
> > Fiz dessa forma: Todas Combinações - Combinações c/ Consecutivos
> >
> > Todas: 24!/5!19!
> > Consecutivos: 23!/4!19! + 22!/3!19! + 21!/2!19! + 20!/1!19!
> >
> > Fiz uma formula geral com n e p e deu o seguinte:
> >
> >  n!/p!(n-p!) - [(n-1)!/(p-1)!(n-p)! +
> > (n-2)!/(p-2)!(n-p)!+...+(n-p+1)!/(n-p)!]
> >
> > Fatorando deu:
> >
> > (1/(n-p)!)[n!/p!-(n-1)!/(p-1)!-(n-2)!/(p-2)-...-(n-p+1)!/(n-p)!]
> >
> > Dae empaquei de vez... Não consegui continuar!
> >  Quem souber fazer por favor me dê a luz! Ou simplesmente indique o erro no
> > meu raciocínio.
> >
> > Agradeço antecipadamente,
> > Maurizio
> >
> >
>
>
> --
> Ideas are bulletproof.
>
> V
>
> =
> Instruções para entrar na lista, sair da lista e usar a lista em
> http://www.mat.puc-rio.br/~obmlistas/obm-l.html
> =
>

=
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] Problema Combinatória

[Johann Peter Gustav Lejeune Dirichlet]

São 24 livros de assuntos distintos? E os livros estão grudados na
estante (se o de Teoria da Computação está do lado de Linguagens
Formais, eles sempre estarão lado a lado?)
Bem, seria algo como escolher cinco números não-consecutivos do conjunto
{1,2,3,4\ldots,24}.
Acho que dá pra usar alguma recursão.
Vou pensar um pouco antes de continuar...

Em 26/03/08, MauZ<[EMAIL PROTECTED]> escreveu:
> Olá a todos!
>
> Numa estante com 24 livros, de quantas maneiras posso retirar 5 livros sem
> ter nenhum consecutivo? E no caso de n livros, quantas maneiras retiro p
> livros sem ter nenhum consecutivo?
>
>
>
> Pra completar vou colocar parte da minha tentativa de solução, preciso de
> ajuda pra saber se está certo até onde fiz e como finalizar pois empaquei.
>
> Fiz dessa forma: Todas Combinações - Combinações c/ Consecutivos
>
> Todas: 24!/5!19!
> Consecutivos: 23!/4!19! + 22!/3!19! + 21!/2!19! + 20!/1!19!
>
> Fiz uma formula geral com n e p e deu o seguinte:
>
>  n!/p!(n-p!) - [(n-1)!/(p-1)!(n-p)! +
> (n-2)!/(p-2)!(n-p)!+...+(n-p+1)!/(n-p)!]
>
> Fatorando deu:
>
> (1/(n-p)!)[n!/p!-(n-1)!/(p-1)!-(n-2)!/(p-2)-...-(n-p+1)!/(n-p)!]
>
> Dae empaquei de vez... Não consegui continuar!
>  Quem souber fazer por favor me dê a luz! Ou simplesmente indique o erro no
> meu raciocínio.
>
> Agradeço antecipadamente,
> Maurizio
>
>


-- 
Ideas are bulletproof.

V

=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=

[obm-l] Problema Combinatória

[MauZ]

Olá a todos!

Numa estante com 24 livros, de quantas maneiras posso retirar 5 livros sem
ter nenhum consecutivo? E no caso de n livros, quantas maneiras retiro p
livros sem ter nenhum consecutivo?



Pra completar vou colocar parte da minha tentativa de solução, preciso de
ajuda pra saber se está certo até onde fiz e como finalizar pois empaquei.

Fiz dessa forma: Todas Combinações - Combinações c/ Consecutivos

Todas: 24!/5!19!
Consecutivos: 23!/4!19! + 22!/3!19! + 21!/2!19! + 20!/1!19!

Fiz uma formula geral com n e p e deu o seguinte:

n!/p!(n-p!) - [(n-1)!/(p-1)!(n-p)! +
(n-2)!/(p-2)!(n-p)!+...+(n-p+1)!/(n-p)!]

Fatorando deu:

(1/(n-p)!)[n!/p!-(n-1)!/(p-1)!-(n-2)!/(p-2)-...-(n-p+1)!/(n-p)!]

Dae empaquei de vez... Não consegui continuar!
Quem souber fazer por favor me dê a luz! Ou simplesmente indique o erro no
meu raciocínio.

Agradeço antecipadamente,
Maurizio

[obm-l] RE: [obm-l] Re: [obm-l] Problema - Combinatória

[David M. Cardoso]

Obrigado a todos pelas respostas...

Só corrigindo o fim da tabela:

 

 
20 75186    353   576

  


  20
55111    167   223

 

 
1
41020     3556
56     56

 

  1 3
6 10 15   
21   

 


 
1 2
3 4 
 5  6 

 

 
1 1 1
1   1  1

 






=
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
=

Re: [obm-l] Re: [obm-l] Problema - Combinatória

[Faelccmm]

O interessante nesta questao eh o conceito de triangulo de Pascal implicito. Observemos bem e veremos o surgimento dos coeficientes dos termos da expansao (x+a)^n.


  20 55    146   293   496
   
  20 35    91    147    203
 
  1 4    10    20 35    56 56 56
 
  1 3 6 10 15    21   
  
  1 2 3 4   5  6 
 
  1 1 1 1   1  1





Em uma mensagem de 7/12/2003 02:22:52 Hor. de verão leste da Am. Sul, [EMAIL PROTECTED] escreveu:


 
   
  20 55    146   293   496
   
  20 35    91    147    203
 
  1 4    10    20 35    56 56 56
 
  1 3 6 10 15    21   
  
  1 2 3 4   5  6 
 
  1 1 1 1   1  1
 
 
  
 É importante destacar que de qualquer maneira que voce caminhe de A ate B (sempre indo para a direita e para cima),voce estara andando ao equivalente a 12 arestas.Mais se voce
caminhar ao menos uma vez para baixo ou para a esquerda, voce percorrera  W > 12 arestas,
ou seja, o minimo está para quando voce caminha para a direita e para cima apenas.Nessas condiçoes, cada numero do quadriculado acima representa o numero de maneiras de se chegar ao vertice sobre o qual esta escrito.
 O numero de cada vertice é a soma do numero do vertice abaixo com o numero do vertice 
a esquerda, logo o numero de maneiras de ir de A a B é 496 (que é o numero que esta sobre o vertice B), Soma(496)= 4 + 9 + 6 = 19.
 
 
 
    Até mais!
 
  Felipe Mendonça.

[obm-l] Re: [obm-l] Problema - Combinatória

[felipe mendona]

 
 
   
  20 55146   293   496
   
  20 3591    147    203
 
  1 41020     3556 56     56
 
  1 3 6 10 15    21   
  
  1 2 3 4   5  6 
 
  1 1 1 1   1  1
 
 
  
 É importante destacar que de qualquer maneira que voce caminhe de A ate B (sempre indo para a direita e para cima),voce estara andando ao equivalente a 12 arestas.Mais se voce
caminhar ao menos uma vez para baixo ou para a esquerda, voce percorrera  W > 12 arestas,
ou seja, o minimo está para quando voce caminha para a direita e para cima apenas.Nessas condiçoes, cada numero do quadriculado acima representa o numero de maneiras de se chegar
ao vertice sobre o qual esta escrito.
 O numero de cada vertice é a soma do numero do vertice abaixo com o numero do vertice 
a esquerda, logo o numero de maneiras de ir de A a B é 496 (que é o numero que esta sobre o vertice B), Soma(496)= 4 + 9 + 6 = 19.
 
 
 
    Até mais!
 
  Felipe Mendonça.
 
 
 
 
  
  
 
 
 
 
 MSN Messenger: converse com os seus amigos online.  Instale grátis. Clique aqui.  
=
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
=

Re: [obm-l] Problema - Combinatória

[Guilherme Carlos Moreira e Silva]

vc deve percorrer ruas e nao quadrados.
pra ir de (1,1) a (2,2) vc deve ir a (1,2) ou a (2,1) __menor caminho.
 
E caminhos de 6 unidades podem ser feitos de outro modos.
Se nao me engano, ha 6!/4!*2! = 15 __ se pensar como vc.
[EMAIL PROTECTED] wrote:
Ola Claudio e demais colegas... Uma duvida quanto a esta questao: O menor caminho de A ateh B nao seria (1,1)-(2,2)-(3,3)-(4,4)-(5,5)-(6,5)-(7,5) ? Ou seja, distancia = 7 unid. ? Em uma mensagem de 6/12/2003 23:43:22 Hor. de verão leste da Am. Sul, [EMAIL PROTECTED] escreveu: 
on 06.12.03 22:27, David M. Cardoso at [EMAIL PROTECTED] wrote: > > Gostaria da ajuda de vcs: > http://www.suati.com.br/david/questao15.gif > Usando coordenadas cartesianas, podemos colocar A = (0,0) e B = (7,5). Para ir de A a B percorrendo a menor distancia possivel (igual a 12 -> 7 quadras pra direita e 5 pra cima) soh podemos ir pra cima ou pra direita. Consideremos os segmentos: s(1): de (3,3) a (3,4); s(2): de (4,3) a (4,4); s(3): de (5,3) a (5,4); s(4): de (5,3) a (6,3). Para ir de A a B percorrendo a distancia minima, temos que passar por exatamente um desses 4 segmentos. Passando por s(1): Binom(6,3)*Binom(5,1) = 100 Passando por s(2): Binom(7,3)*Binom(4,1) = 140 Passando por s(3): Binom(8,3)*Binom(3,1) = 168 Passando por s(4): Binom(8,3)*Binom(3,2) = 168
 Logo, N = 100 + 140 + 168 + 168 = 576 e a soma dos algarismos de N eh 18. Um abraco, Claudio. Yahoo! Mail - 6MB, anti-spam e antivírus gratuito. Crie sua conta agora!

Re: [obm-l] Problema - Combinatória

[Faelccmm]

Ola Claudio e demais colegas...

Uma duvida quanto a esta questao:

O menor caminho de A ateh B nao seria (1,1)-(2,2)-(3,3)-(4,4)-(5,5)-(6,5)-(7,5) ? Ou seja, distancia = 7 unid. ?


Em uma mensagem de 6/12/2003 23:43:22 Hor. de verão leste da Am. Sul, [EMAIL PROTECTED] escreveu:


on 06.12.03 22:27, David M. Cardoso at [EMAIL PROTECTED] wrote:

> 
> Gostaria da ajuda de vcs:
> http://www.suati.com.br/david/questao15.gif
> 
Usando coordenadas cartesianas, podemos colocar A = (0,0) e B = (7,5).
Para ir de A a B percorrendo a menor distancia possivel (igual a 12 -> 7
quadras pra direita e 5 pra cima) soh podemos ir pra cima ou pra direita.

Consideremos os segmentos:
s(1): de (3,3) a (3,4);
s(2): de (4,3) a (4,4);
s(3): de (5,3) a (5,4);
s(4): de (5,3) a (6,3).

Para ir de A a B percorrendo a distancia minima, temos que passar por
exatamente um desses 4 segmentos.

Passando por s(1): Binom(6,3)*Binom(5,1) = 100
Passando por s(2): Binom(7,3)*Binom(4,1) = 140
Passando por s(3): Binom(8,3)*Binom(3,1) = 168
Passando por s(4): Binom(8,3)*Binom(3,2) = 168

Logo, N = 100 + 140 + 168 + 168 = 576 e a soma dos algarismos de N eh 18.

Um abraco,
Claudio. 

Re: [obm-l] Problema - Combinatória

[Claudio Buffara]

on 06.12.03 22:27, David M. Cardoso at [EMAIL PROTECTED] wrote:

> 
> Gostaria da ajuda de vcs:
> http://www.suati.com.br/david/questao15.gif
> 
Usando coordenadas cartesianas, podemos colocar A = (0,0) e B = (7,5).
Para ir de A a B percorrendo a menor distancia possivel (igual a 12 -> 7
quadras pra direita e 5 pra cima) soh podemos ir pra cima ou pra direita.

Consideremos os segmentos:
s(1): de (3,3) a (3,4);
s(2): de (4,3) a (4,4);
s(3): de (5,3) a (5,4);
s(4): de (5,3) a (6,3).

Para ir de A a B percorrendo a distancia minima, temos que passar por
exatamente um desses 4 segmentos.

Passando por s(1): Binom(6,3)*Binom(5,1) = 100
Passando por s(2): Binom(7,3)*Binom(4,1) = 140
Passando por s(3): Binom(8,3)*Binom(3,1) = 168
Passando por s(4): Binom(8,3)*Binom(3,2) = 168

Logo, N = 100 + 140 + 168 + 168 = 576 e a soma dos algarismos de N eh 18.

Um abraco,
Claudio. 

=
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
=

[obm-l] Problema - Combinatória

[David M. Cardoso]

Gostaria da ajuda de vcs:
http://www.suati.com.br/david/questao15.gif

=
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
=