RE: [obm-l] Problemas

[João Gilberto Ponciano Pereira <jopereira@xxxxxxxxxxxxx>]

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