Re: [obm-l] Problemas

["Cláudio \(Prática\)" <claudio@xxxxxxxxxxxxxxxxxxxxxxx>]

Caro JG:

O problema fala que um sapato só pode ser colocado se a meia já estiver lá.
Assim, no caso humano, as sequencias possíveis serão as seguintes:

M1 M2 S1 S2
M1 M2 S2 S1
M1 S1 M2 S2
M2 M1 S1 S2
M2 M1 S2 S1
M2 S2 M1 S1.

em número de 6, que bate com a minha análise.

(n!)^2 leva em conta situações onde você coloca o sapato antes da meia, o
que é proibido pelo enunciado.

Um abraço,
Claudio.

----- Original Message -----
From: "João Gilberto Ponciano Pereira" <jopereira@vesper.com.br>
To: <obm-l@mat.puc-rio.br>
Sent: Monday, March 10, 2003 5:57 PM
Subject: RE: [obm-l] Problemas


> Pessoal
>
> Não sei se foi eu que entendi errado, mas acho que o problema das aranhas
é
> mais simples:
>
> "1) Uma aranha tem uma meia e um sapato para cada uma de suas  8 pernas.
De
> quantas maneiras diferente a aranha pode colocar as meias e os sapatos,
> supondo  que , em cada perna, a meia tem de ser calçada antes do sapato?"
>
> As meias e os sapatos são eventos distintos, portanto basta multiplicar  o
> número de combinações possíveis de sapatos pelo número de combinações das
> meias, ou seja, (n!) ^2. Para o caso humano:
>
> Pé direito Pé esquerdo
> Sapato1 - Meia1 Sapato2 - Meia2
> Sapato1 - Meia2 Sapato2 - Meia1
> Sapato2 - Meia1 Sapato1 - Meia2
> Sapato2 - Meia2 Sapato1 - Meia1
>
> -----Original Message-----
> From: Cláudio (Prática) [mailto:claudio@praticacorretora.com.br]
> Sent: Monday, March 10, 2003 4:58 PM
> To: obm-l@mat.puc-rio.br
> Subject: Re: [obm-l] Problemas
>
>
> Caro Benedito:
>
> Aqui vai minha solução pro primeiro.
>
> Suponhamos que a aranha tenha n pernas. Seja X(n) o número de maneiras.
>
> Neste caso, cada maneira pode ser representada por uma seqûencia de 16
> símbolos distintos:
> M(1), M(2), ..., M(n) e S(1), S(2), ..., S(8)
> de forma que para cada k (1 <= k <= n), M(k) sempre preceda S(k).
>
> n = 1:
> a única sequencia possível é M(1), S(1) ==> X(1) = 1
>
> n = k:
> para cada sequência correspondente a n = k-1 ( ou seja, 2(k-1) símbolos),
> podemos formar uma sequencia correspondnete a n = k, inserindo os símbolos
> M(k) e S(k), de forma que M(k) preceda S(k).
> Inicialmente, podemos inserir M(k) em 2(k-1) + 1 = 2k - 1 posições
> distintas.
> Se não houvesse a restrição da precedência, poderíamos inserir S(k) em
(2k -
> 1) + 1 = 2k posições distintas, das quais k teriam M(k) antes de S(k) e k
> teriam S(k) antes de M(k).
> Descartando estas últimas, ficamos com k posições distintas para S(k).
>
> Logo, temos a recorrência: X(k) = k * (2k - 1) * X(k-1) ==>
>
> X(1) = 1
> X(2) = 2*3*X(1)
> X(3) = 3*5*X(2)
> X(4) = 4*7*X(3)
> X(5) = 5*9*X(4)
> X(6) = 6*11*X(5)
> X(7) = 7*13*X(6)
> X(8) = 8*15*X(7)
>
> Multiplicando tudo e simplificando, teremos: X(8) = 8! * (15!/(2^7*7!)) =
> 15! * 8 / 2^7 = 15! / 16.
>
> Um abraço,
> Claudio.
>
> ----- Original Message -----
> From: "benedito" <benedito@digi.com.br>
> To: <obm-l@mat.puc-rio.br>
> Sent: Monday, March 03, 2003 9:31 PM
> Subject: [obm-l] Problemas
>
>
> >
> > >Do livro   "102 Combinatorial Problems - From the Training of the  USA
> IMO
> > > > Team" , de Titu Andreescu e Zuming Feng - Birkhäuser. 2003,  dois
> > > problemas
> > > > interessantes:
> > > >
> > > > 1) Uma aranha tem uma meia e um sapato para cada uma de suas  8
> pernas. De
> > > > quantas maneiras diferente a aranha pode colocar as meias e os
> sapatos,
> > > > supondo  que , em cada perna, a meia tem de ser calçada antes do
> sapato?
> > > >
> > > > 2) Seja  n =  2^31 . 3^19. Quantos são os divisores inteiros
positivos
> > > > de  n^2 que são menores do que  n  mas  não dividem  n?
> > > >
> > > > (Nota:  n^2 =  n elevado a dois)
> > > >
> > > > Benedito Freire
> >
>
> =========================================================================
> 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
> O administrador desta lista é <nicolau@mat.puc-rio.br>
> =========================================================================
> =========================================================================
> 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
> O administrador desta lista é <nicolau@mat.puc-rio.br>
> =========================================================================

=========================================================================
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
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================