[obm-l] Dominos (correcao)

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

Hoje tah mais complicado que o de habito....

Problema: Dados 10 dominos distintos da forma {a,b} com 0 <= a < b <= 4, de
quantas formas podemos arranja-los em sequencia de modo que dois dominos
vizinhos tenham um numero em comum (e o 10o. domino tenha um numero em comum
com o 1o.)?

Problema equivalente: De quantas maneiras podemos arranjar 10 elementos do
conjunto {0,1,2,3,4} em sequencia de modo que dois numeros quaisquer sejam
vizinhos exatamente uma vez (o 10o. termo da sequencia eh considerado
vizinho do 1o.)

Solucao proposta para o segundo problema:

Fixe um elemento qualquer de {0,1,2,3,4}. Digamos, o 0.

Teremos 3 tipos de sequencia:
(1)  a 0 b c 0 d x y z w
ou
(2)  a 0 b x c 0 d y z w
ou
(3)  a 0 b x y c 0 d z w

onde {a,b,c,d} = {x,y,z,w} = {1,2,3,4}

Repare que sequencias do tipo a 0 b x y z c 0 d w jah estao incluidas dentre
as de tipo (2) e sequencias do tipo a 0 b x y z w c 0 d dentre as de tipo
(1).

Em cada sequencia de cada tipo, a, b, c e d poderao ser escolhidos de 4! =
24 maneiras distintas.

No tipo (1): a 0 b c 0 d x y z w
x pertence a {a, b, c}
x = a ==> w = b  ou  w = c
x = b ==> w = c  ou  w = d
x = c ==> w = b  ou  w = d
Em cada caso, y e z ficam unicamente determinados.
Por exemplo, se x = b e w = d, entao y = a e z = c necessariamente.
Assim, fixados a, b, c, d, teremos 3*2 = 6 possibilidades para x, y, z, w.

No tipo (2): a 0 b x c 0 d y z w
x pertence a {a, d}
x = a ==> w = d ==> {y,z} = {b,c}
x = d ==>  y = a ==> {z,w} = {b,c}
Assim, fixados a, b, c, d, teremos 2*2 = 4 possibilidades para x, y, z, w.

No tipo(3): a 0 b x y c 0 d z w
{x,y} = {a,d}  e  {z,w} = {b,c}
Assim, fixados a, b, c, d, teremos 2*2 = 4 possibilidades para x, y, z, w.

Logo, fixados a, b, c, d, teremos 6 + 4 + 4 = 14 sequencias de todos os
tipos.

Total = 24*14 = 336.

Logo, existem 336 configuracoes diferentes para um jogo fechado de 10
dominos, cada um com 2 numeros distintos do conjunto {0,1,2,3,4}.

Cada configuracao pode ser obtida de 10*2^8 = 2560 maneiras (ou seja,
existem 2560 ordens distintas de colocacao dos dominos na mesa para se obter
cada configuracao)

Assim, com estes 10 dominos, um jogo fechado pode ser obtido de 860160
formas distintas

Espero que agora esteja certo.

[]s,
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
=========================================================================