Aranha colocar meia e sapato

Uma aranha tem uma meia e um sapato para cada um de seus oito pés. De quantas maneiras diferentes a aranha pode se calçar admitindo que a meia tem que ser colocada antes do sapato? (Considere que as meias e os sapatos são iguais entre si).

Gab: (8!)²/2

Como a aranha tem 8 pés, ela possui de acordo com o problema, 8 meias e 8 sapatos.

Considerando a condição de que ela deve calçar-se de maneira distinta, temos : sapatos -( 8x7x6x5x4x3x2x1) x meia -(8x7x6x5x4x3x2x1)

Isso produz (8! x 8!) = (8!) ^2 (elevado ao quadrado)


Mas, conforme a questão a meia deve vir antes do sapato, então devemos dividir (8!) ^2  por 2!, para desfazer as possíveis permutações que não podem acontecer.


Logo = (8!) ^2 / 2! = (8!)^2 / 2

Obrigado pela resposta, Nina. Eu não estava conseguindo me convencer de que eu deveria dividir por 2 por causa disso da ordem do sapato vir depois, pois não estava enxergando. Mas depois fiz um esquema e vi melhor. Suponha que uma pessoa tem uma meia e um sapato para cada uma das duas pernas, 1 e 2. Meia = M e sapato = S. A primeira meia escolhe a perna de 2 modos e os sapatos escolhem a perna de 2 modos. 2*2 = 4. Listando:
M1 S1 = ok
M1 S2 = não, pois o sapato foi colocado na perna 2 antes da meia.
M2 S2 = ok
M2 S1 = não, pois o sapato foi colocado na perna 1 antes da meia.
Daí vem a divisão por 2. Depois de fazer isso, entendi bem.

Agora suponha que as meias e os sapatos sejam diferentes, no caso da aranha. Teríamos 8!³/3!, concorda?

De nada, disponha ! .Pode demonstrar como chegastes à (8!)^3 /3!  ?

Primeiro escolhe-se a ordem em que vamos colocar nas pernas: 8! modos.
Depois escolhe-se a ordem em que vamos colocar os sapatos: 8! modos.
E as meias: 8!
Ou seja, tudo, 8!³ modos. Mas quando multiplicamos assim, contamos ordens que não podem (3!):
pms ---> ordem que interessa
psm
smp
spm
msp
mps
Só 1/3! = 1/6 dessas ordens interessa, que é a primeira: perna, meia, sapato.

Compreendi. Ótimo raciocínio Ashitaka !

Caros Nina, Ashitaka e demais amigos.
Apenas recentemente encontrei esse problema pela frente. Parece que é da Olimpíada Americana.
O gabarito que encontrei também era (8!)^2/2, mas eu não conseguia enxergar a lógica da divisão
por 2 nesse caso. Depois de muito penar, acho que consegui entender que esse gabarito está errado.
O correto é 16!/2^8. Vou tentar explicar meu raciocínio...
Como a aranha tem 8 pés e as meias e os sapatos são iguais entre si, cada ação envolve a escolha
de um pé e cada pé será escolhido duas vezes no processo, primeiro para calçar a meia e depois
para calçar o sapato.
Representando os pés da aranha por 1, 2, 3, ... , 8 seriam sequências válidas, por exemplo,
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 , 1 2 3 4 5 6 7 8 8 7 6 5 4 3 2 1 , 1 3 3 2 6 8 2 5 1 7 4 8 5 4 6 7 .
Veja que essa simbolização não exige que nos preocupemos que o sapato não seja calçado antes da
meia, pois a primeira vez que um número aparece representando um pé é claro que se refere à meia.
Então, o número de escolhas diferentes possível é dado pela permutação de 1 a 8 com repetição:
                                                         2,2,2,2,2,2,2,2
                                                       P                         = 16 ! / 2^8
                                                         16

Ashitaka, no raciocínio trocando a aranha por uma pessoa, note que no processo existem 4 ! = 24
sequências possíveis e não apenas as 4 mostradas. Por exemplo, devemos considerar também
possibilidades como (S1 S2 M1 M2), (M2 S1 S2 M1), etc., que não são válidas mas devem ser contadas.

Portanto, caso acrescentássemos mais uma ação, por exemplo, E = engraxar o sapato, a solução seria:
                                             3,3,3,3,3,3,3,3
                                           P                        = 24! / 3^8 e não (8!)^3 / 3
                                             24
Pra esse exemplo, uma sequência válida seria 5 2 8 1 2 3 6 4 7 3 2 1 5 8 1 3 4 4 6 5 7 6 8 7 . O raciocínio
é o mesmo: quando aparecer o primeiro 2 significa "vestir a meia no pé 2" , na segunda ocorrência do 2 o
significado é "calçar o sapato no pé 2" e na terceira aparição do número 2 o significado seria "engraxar o
sapato que está no pé 2" .

Espero ter ajudado alguém.

Abraços.

Boa tarde, pessoal.

Encontrei outra resolução para o problema, essa baseada na ideia da divisão por 2 , porém, sucessivas vezes. Achei interessante, mas ainda acho a minha mais elegante  : )

(Extraído da AMC) Representemos os sapatos pelos símbolos si , com 1 ≤ i ≤ 8, e as meias com mi , também com 1 ≤ i ≤ 8. Uma sequência desses símbolos em linha produz uma ordem na forma como a aranha deve se calçar. Queremos então determinar todos os anagramas de uma palavra formada por todos esses símbolos em que mi , com 1 ≤ i ≤ 8 , sempre esteja à esquerda de si . Das 16! permutações desses símbolos, em exatamente metade delas m1 está à esquerda de s1 e na outra metade ele está à direita. Analisando então os 16!/2 anagramas em que m1 está à esquerda de s1, temos que em metade deles m2 está à esquerda de s2 e na outra metade à direita. Assim, em 16!/4 anagramas, as meias m1 e m2 são calçadas antes dos sapatos s1 e s2. Repetindo o argumento, podemos concluir que em 16! /( 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2) = 16! / 2^8 anagramas, a aranha calça as meias antes dos sapatos correspondentes.