Em dom, 8 de set de 2019 às 13:47, Ralph Teixeira <ralp...@gmail.com> escreveu: > > A face de baixo eh P1-P2-P3-P4, a de cima eh P8-P7-P6-P5 (P8 acima do P1, > etc.). Desse jeito, as 12 arestas sao as 8 do ciclo > P1-P2-P3-P4-P5-P6-P7-P8-P1, mais os 4 pares P1-P4, P2-P7, P3-P6, P5-P8. > > Cada "maneira de rotular" vai ser representada por uma linha com 8 numeros (o > rotulo do ponto Pj na coluna j). Por exemplo, uma rotulacao seria [1 7 5 3 8 > 2 4 6], indicando que o ponto P1 levou o numero 1, o ponto P2 levou o 7, etc. > Note que este exemplo eh, de fato, valido -- nao ha vizinhos com diferenca 1 > (no ciclo P1-...P8), e os pares P1-P4=1-3, P2-P7=7-4,... tambem nao tem > distancia 1,-1,7 nem -7 entre si. > > Bom, ai chutei o balde e botei no MatLab: :D :D :D
Mas poxa, Ralph! Se é para esculachar, esculache em Prolog! Isso tem muito aquela cara de "constraint solving" usada em programação lógica. Eu até consigo imaginar uma sequência de limitadores que devem ser satisfeitos para isso funcionar - coisas como uma sequência de oito variáveis e doze diferenças que não podem ser unitárias. > > Perm1=perms([1 2 3 4 5 6 7 8]) % Acha as 40320 > permutacoes; exagerei, podia fixar um deles, mas o Matlab aguenta. > Diff=abs(Perm1(:,[1:8,1,2,3,5])-Perm1(:,[2:8,1,4,7,6,8])); % Calcula > diferencas de rotulos entre vertices vizinhos -- cada coluna significa uma > aresta. > Test=ismember(Diff,[1 7]) % Encontra todos > as diferencas proibidas. Gera uma matriz com 1 para cada elemento 1 ou 7 de > Diff, e 0 caso contrario. > Index=(sum(Test,2)==0) % Para uma linha > ser valida, TODOS os elementos tem que ser 0, ou seja, a soma da linha tem > que dar 0. > Validas=Perm1(Index,:) % Seleciona a > submatriz com as linhas validas. > > Muito bem, achei 480 permutacoes validas... Aqui as 60 que comecam com 1, > talvez inspire alguem a achar uma solucao no braco, dividindo em casos... Hm, > vejo umas simetrias adicionais que poderiam ser exploradas... > > Abraco, Ralph. > > 1 7 5 3 8 2 4 6 > 1 7 5 3 6 8 2 4 > 1 7 4 6 8 2 5 3 > 1 7 4 6 3 8 2 5 > 1 7 4 6 2 8 3 5 > 1 7 3 6 8 5 2 4 > 1 7 3 5 8 6 2 4 > 1 7 3 5 2 8 4 6 > 1 7 2 5 3 8 4 6 > 1 7 2 4 8 6 3 5 > 1 7 2 4 8 5 3 6 > 1 7 2 4 6 8 5 3 > 1 6 8 4 2 5 3 7 > 1 6 8 3 7 5 2 4 > 1 6 8 3 7 4 2 5 > 1 6 8 3 5 2 4 7 > 1 6 4 7 5 2 8 3 > 1 6 4 7 3 8 2 5 > 1 6 4 7 2 8 3 5 > 1 6 3 7 2 5 8 4 > 1 6 3 5 2 8 4 7 > 1 6 2 5 7 4 8 3 > 1 6 2 5 3 8 4 7 > 1 6 2 4 7 5 8 3 > 1 5 8 4 6 2 7 3 > 1 5 8 4 2 6 3 7 > 1 5 8 3 6 2 7 4 > 1 5 7 4 6 2 8 3 > 1 5 7 3 8 4 2 6 > 1 5 7 3 6 2 8 4 > 1 5 3 7 4 8 2 6 > 1 5 3 7 2 6 8 4 > 1 5 3 6 4 8 2 7 > 1 5 2 7 4 8 3 6 > 1 5 2 6 8 4 7 3 > 1 5 2 6 4 8 3 7 > 1 4 8 6 3 5 2 7 > 1 4 8 5 7 2 6 3 > 1 4 8 5 3 6 2 7 > 1 4 7 5 8 2 6 3 > 1 4 7 3 8 5 2 6 > 1 4 6 3 8 2 7 5 > 1 4 6 3 7 2 8 5 > 1 4 6 3 5 8 2 7 > 1 4 2 7 5 8 6 3 > 1 4 2 7 3 6 8 5 > 1 4 2 7 3 5 8 6 > 1 4 2 6 8 5 7 3 > 1 3 8 6 4 2 5 7 > 1 3 8 6 2 5 7 4 > 1 3 8 6 2 4 7 5 > 1 3 8 5 7 2 6 4 > 1 3 7 5 8 2 6 4 > 1 3 7 5 2 4 8 6 > 1 3 7 4 2 5 8 6 > 1 3 6 4 8 2 7 5 > 1 3 6 4 7 2 8 5 > 1 3 6 4 2 8 5 7 > 1 3 5 7 4 2 8 6 > 1 3 5 7 2 8 6 4 > > On Sun, Sep 8, 2019 at 9:08 AM Anderson Torres <torres.anderson...@gmail.com> > wrote: >> >> Em sáb, 7 de set de 2019 às 02:23, marcone augusto araújo borges >> <marconeborge...@hotmail.com> escreveu: >> > >> > De quantas maneiras podemos atribuir um número de 1 a 8 a cada vértice de >> > um cubo de modo que não apareçam números consecutivos nas extremidades de >> > uma mesma aresta, sendo o 1 e o 8 considerados consecutivos e a dois >> > vértices não seja atribuído um mesmo número? >> > >> >> Eu só consigo pensar em resolver isso usando inclusão&exclusão. Mas >> quanto mais eu penso, mais feio fica! >> >> > -- >> > Esta mensagem foi verificada pelo sistema de antivírus e >> > acredita-se estar livre de perigo. >> >> -- >> Esta mensagem foi verificada pelo sistema de antivírus e >> acredita-se estar livre de perigo. >> >> >> ========================================================================= >> Instru�ões para entrar na lista, sair da lista e usar a lista em >> http://www.mat.puc-rio.br/~obmlistas/obm-l.html >> ========================================================================= > > > -- > Esta mensagem foi verificada pelo sistema de antivírus e > acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo. ========================================================================= Instru��es para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =========================================================================
