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" <[EMAIL PROTECTED]> To: <[EMAIL PROTECTED]> 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:[EMAIL PROTECTED] > Sent: Monday, March 10, 2003 4:58 PM > To: [EMAIL PROTECTED] > 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" <[EMAIL PROTECTED]> > To: <[EMAIL PROTECTED]> > 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 é <[EMAIL PROTECTED]> > ========================================================================= > ========================================================================= > 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 é <[EMAIL PROTECTED]> > ========================================================================= ========================================================================= 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 é <[EMAIL PROTECTED]> =========================================================================