Pentominó

Pentominó o que é


Origem: Wikipédia, a Enciclopédia Livre   (Redirecionado de Pentominoes ) 
Comparação dos sistemas de rotulagem para os 12 possíveis formas Pentomino. A primeira convenção de nomenclatura é a usada neste artigo. O segundo método é de Conway.
A pentomino é uma figura geométrica plano formado pela união de cinco quadrados iguais ponta a ponta. É um Polyomino com cinco células. Há doze pentaminós, sem contar rotações e reflexões como distintos. Eles são usados ​​principalmente em matemática recreativa para quebra-cabeças e problemas. [ 1 ] Pentominoes foram formalmente definido pelo professor americano Solomon W. Golomb , a partir de 1953 e mais tarde em seus 1.965 livro Poliominós: Puzzles, Patterns, Problemas, e embalagens . [ 2 ] [ 3 ] Golomb cunhou o termo "pentomino" do grego πέντε / Pente , "cinco", e o-omino de dominó , caprichosamente interpretar a "d-" de "dominó", como se fosse uma forma de o prefixo grego " di-"(dois). Golomb chamado os 12 livres pentaminós após letras do alfabeto latino que eles se assemelham.                   
Normalmente, o pentomino obtido por refletir ou girando um pentomino não conta como um pentomino diferente. A F, L, N, P, Y e Z são pentaminós quiral ; adicionando os seus reflexos (F ', J, N', Q, Y ', S) traz o número de unilaterais pentominós a 18. Pentominoes I, T, U, V, W, e X, permanecem os mesmos, quando reflectida. Isso é importante em alguns jogos de vídeo em que as peças não podem ser refletidas, como Tetris imitações e Rampart         
Cada um dos doze pentaminós pode telha do avião . Cada pentomino quiral pode dividir o avião sem refleti-lo. [ 4 ]   
John Horton Conway  proposto um sistema de rotulagem para pentominós alternativo, utilizando O, em vez de I, Q em vez de G, R, em vez de F e S em vez de N. A semelhança com as letras é mais tensas, especialmente para o pentominó ó, mas esta regime tem a vantagem de utilizar 12 letras do alfabeto consecutivos. Ele é usado por convenção em discutir Jogo da Vida de Conway , onde, por exemplo, fala-se do R-pentomino vez do F-pentomino.

Simetria [ editar ]

Os 12 pentaminós podem formar 18 formas diferentes, com 6 sendo espelhado
Pentominoes tem as seguintes categorias de simetria :
  • F, L, N, P, e Y pode ser orientada em 8 maneiras: 4 por rotação, e mais 4, para a imagem de espelho. O seu grupo de simetria consiste apenas no mapeamento de identidade 
  • T e U podem ser orientados em quatro formas de rotação. Eles têm um eixo de reflexão alinhado com as linhas de grade. Seu grupo de simetria tem dois elementos, a identidade e a reflexão de uma linha paralela aos lados dos quadrados.  
  • V e W pode também ser orientada em quatro formas de rotação. Eles têm um eixo de simetria de reflexão de 45 ° para as linhas de grade. O seu grupo de simetria tem dois elementos, a identidade e uma reflexão diagonal.
  • Z pode ser orientada em quatro modos: 2 por rotação, e mais 2 para a imagem no espelho. Tem apontar simetria, também conhecida como simetria rotacional de ordem 2. Seu grupo de simetria tem dois elementos, a identidade ea rotação de 180 °.  
  • I pode ser orientado em duas formas, por rotação. Ele tem dois eixos de simetria de reflexão, tanto alinhado com as linhas de grade. O grupo de simetria tem quatro elementos, a identidade, duas reflexões e da rotação de 180 °. É o grupo diedro de ordem 2, também conhecido como o grupo de quatro Klein 
  • X pode ser orientado de uma única maneira. Ele tem quatro eixos de simetria de reflexão, alinhado com as linhas de grade e as diagonais, e simetria rotacional de ordem 4. Seu grupo de simetria, o grupo diedro de ordem 4, tem oito elementos.
Se reflexões de uma pentomino são considerados distintos, como são com pentaminós unilaterais, então a primeira e quarta categorias acima dobrar de tamanho, resultando em um acréscimo de 6 pentaminós para um total de 18. Se rotações também são considerados distintos, então o pentaminós da primeira categoria contar óctuplo, os das próximas três categorias (T, U, V, W, Z) contam quatro vezes, eu conta duas vezes, e X conta apenas uma vez. Isso resulta em 5 × 8 + 5 × 4 + 2 + 1 = 63 fixos pentaminós.  
Por exemplo, dos oito possíveis orientações do L, pentominós M, N, P, e Y são como se segue:
L-pentomino Symmetry.svgF-Pentomino Symmetry.svg  N-Pentomino Symmetry.svg  P-pentomino Symmetry.svgPentomino.svg Y
Para figuras 2D em geral, existem mais duas categorias:
  • Sendo orientável em duas formas de uma rotação de 90 °, com dois eixos de simetria de reflexão, tanto alinhados com as diagonais. Este tipo de simetria requer, pelo menos, um heptomino
  • Sendo orientável de 2 maneiras, que são imagens de espelho um do outro, por exemplo, uma suástica . Este tipo de simetria requer, pelo menos, um octomino

Retângulos Tiling [ editar ]

Exemplo tilings
Um padrão de quebra-cabeça pentomino é azulejo uma caixa retangular com os pentaminós, ou seja, cobri-lo, sem sobreposição e sem lacunas. Cada um dos 12 pentominós tem uma área de cinco quadrados de unidade, de modo que a caixa deve ter uma área de 60 unidades. Tamanhos possíveis são 6 × 10, 5 × 12, 4 × 15 e 3 × 20. O ávido puzzler provavelmente pode resolver estes problemas com a mão dentro de algumas horas. A tarefa mais difícil, requerendo tipicamente um computador de busca , é contar o número total de soluções em cada caso.      
O 6 × 10 caso foi resolvido pela primeira vez em 1960 por Colin Brian e Jenifer Haselgrove . [ 5 ] Há exatamente 2339 soluções, excluindo variações triviais obtidos por rotação e reflexão de todo o retângulo, mas incluindo rotação e reflexão de um subconjunto de pentaminós ( que, por vezes, fornece uma solução adicional de uma maneira simples). A caixa 5 × 12 tem 1.010 soluções, a caixa de 4 × 15 tem 368 soluções, e a caixa de 3 × 20 tem apenas duas soluções (uma é mostrada na figura, e o outro pode ser obtido a partir da solução apresentada pela rotação, como um todo, o bloco que consiste em L, N, F, T, W, Y, e Z pentominós).    
Um quebra-cabeça um pouco mais fácil (mais simétrica), o 8 × 8 retângulo com um buraco de 2 × 2 no centro, foi resolvido por Dana Scott , já em 1958. [ 6 ] Há 65 soluções. Algoritmo de Scott foi uma das primeiras aplicações de um retrocesso programa de computador. Variações desta quebra permitir que os quatro orifícios a serem colocados em qualquer posição. Um dos links externos usa esta regra. A maioria dos tais padrões são solucionáveis, com as exceções de colocar cada par de buracos perto de dois cantos do tabuleiro de tal forma que ambos os cantos só poderia ser montado por um P-pentomino, ou forçar uma T-pentomino ou U-pentomino em um canto de tal forma que um outro furo é criado.     
Pentomino unsolvable.svg
Algoritmos eficientes têm sido descritos para resolver tais problemas, por exemplo, por Donald Knuth . [ 7 ] Correndo em moderno hardware , estes enigmas Pentomino agora pode ser resolvido em poucos segundos.   

Encher caixas [ editar ]

Um pentacube é um polycube de cinco cubos. Doze dos 29 pentacubes correspondem aos doze pentominós extrudido para uma profundidade de um quadrado. Um quebra-cabeça pentacube ou 3D quebra-cabeça pentomino , é de encher uma caixa de 3-dimensional com estas pentacubes 1 camada, ou seja, cobri-lo, sem sobreposição e sem lacunas. Cada um dos 12 pentacubes consiste em 5 cubos de unidade, e são como pentaminós 2D, mas com espessura unidade. Claramente a caixa deve ter um volume de 60 unidades. Tamanhos possíveis são 2 × 3 × 10 (12 soluções), 2 × 5 × 6 (264 soluções) e 3 × 4 × 5 (3940) soluções. Seguem-se uma solução de cada caso. [ 8 ]       Pentomino Cube Solutions.svg