[obm-l] Dominos

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

Title: Dominos

Aqui vai uma versao mais simples do problema, onde ha apenas 10 dominos com numeros de 0 a 4:

Usando a ideia abaixo, temos que calcular o numero de sequencias de 10 numeros dentre {0,1,2,3,4} tais que dois numeros quaisquer sao vizinhos exatamente uma vez (o 10o. termo da sequencia eh considerado vizinho do 1o.)
Essa condicao garante que cada numero vai aparecer exatamente duas vezes. Aquela primeira condicao do primeiro termo ser igual ao ultima nao eh valida - foi mancada minha.

Fixe um numero qualquer, digamos o 0.

Entao, teremos dois tipos de sequencia:
a 0 b c 0 d _ _ _ _
ou
a 0 b _ _ c 0 d _ _
onde {a,b,c,d} = {1,2,3,4}.
Ou seja, os dois zeros distam 3 ou 5 um do outro.

Consideremos o primeiro tipo: a 0 b c 0 d x y z w

* a, b, c, d podem ser escolhidos de 4! = 24 maneiras.
Pra facilitar a analise, fixemos uma dessas escolhas. Digamos:
1 0 2 3 0 4 x y z w.

* Temos 3 possibilidades para x: 1, 2 ou 3.
Caso 1: x = 1 ==> 1 0 2 3 0 4 1 y z w
y soh pode ser 2 ou 3 e, uma vez escolhido y, z e w ficam unicamente determinados.
Por exemplo, se y = 2, entao necessariamente z = 4 e w = 3.
Logo, fixando x = 1 temos 2 possibilidades para a sequencia (y = 2 ou y = 3).

Caso 2: x = 2 ==> 1 0 2 3 0 4 2 y z w
y soh pode ser 1 e z pode ser 3 ou 4.
Se z = 3 entao w = 4  e  se z = 4 entao w = 3.
Logo, fixando x = 2 temos 2 possibilidades para a sequencia (z = 3 ou z = 4)

Caso 3: x = 3.
Esse caso eh analogo ao anterior, resultando em mais duas possibilidades para a sequencia.

*Em suma, existem 4!*(2+2+2) = 144 sequencias do primeiro tipo.

Uma analise semelhante mostra que existem 96 sequencias do segundo tipo (a menos de algum erro de conta).

Logo, temos um total de 144 + 96 = 240 sequencias, ou seja, 240 configuracoes possiveis para um jogo fechado de dominos usando apenas os 10 dominos que contem os numeros de 0 a 4.

Se voce quiser o numero de maneiras em que o jogo pode proceder de forma a usar todas as 10 pecas, voce precisa multiplicar 240 por 10*2^8, pois temos 10 possibilidades para a primeira peca colocada e, depois disso, 2 possibilidades para a peca seguinte (uma de cada lado da sequencia de dominos na mesa) ateh a nona. A decima fica unicamente determinada. Outra maneira de ver isso eh rodar o jogo de tras pra frente e ir retirando as pecas.

***

Pra 21 dominos com os numeros 0, 1, 2, 3, 4, 5, 6, acho que dah pra fazer do mesmo jeito, mas com muito mais sub-casos.

[]s,
Claudio.

on 12.05.05 20:29, Claudio Buffara at claudio.buffara@terra.com.br wrote:

> Acho que nao eh por falta de interesse que as pessoas nao estao respondendo.
> Deve ser porque o problema eh dificil mesmo.
>
> Uma ideia eh, ao inves de olhar para os dominos, olhe para os pares de numeros identicos em sequencia.
> Por exemplo, uma dada sequencia de dominos pode ser:
> ...[2,3][3,6][6,0][0,1][1,3][3,4][4,5][5,3][3,0]... 
> A sequencia correspondente de pares de numeros identicos eh:
> ...(2,2)(3,3)(6,6)(0,0)(1,1)(3,3)(4,4)(5,5)(3,3)(0,0)...
>
> Assim, ao inves de calcular o numero de sequencias de 21 dominos voce poderia olhar para o numero de sequencias de 21 numeros do conjunto A = {0,1,2,3,4,5,6} tais que:
> 1) elas comecam e terminam com o mesmo numero;
> 2) cada numero aparece exatamente 3 vezes;
> 3) dois numeros quaisquer (distintos) de A aparecem exatamente uma vez como vizinhos.
>
> Essas condicoes devem ser redundantes, mas nao faz mal.
>
> Talvez seja mais facil desse jeito...
>
> []s,
> Claudio.
>
> on 12.05.05 18:05, eritotutor at eritotutor@bol.com.br wrote:
>
> >  boa noite pessoal ...
> >  
> > Estou há algum tempo para fazer a quetão abaixo, entretanto, não sei q abordagem tomar para analisá-la
> > Ficaria grato se vcs pudessem me ajudar....
> >     
> >   Considere um jogo de dominó sem as peças com valores iguais dos dois lados (restarão portanto 21 peças). De quantas formas diferentes é possível "fechar o jogo", em uma partida com dois jogadores?
> >    
> >   Desde já agradeço...
> >    
> >   []s