Original Article: The Tromino Puzzle by Norton Starr
Author: Norton Starr
|
O Quebra-cabeça Trominó
Para jogar uma versão física deste quebra-cabeça, usando 21 peças de trominó reais, uma única peça quadrada e uma base de xadrez de 8 x 8, primeiro posicione a peça quadrada única em qualquer uma das 64 posições quadradas na base. Em seguida, preencha os 63 quadrados restantes com os trominós, de modo que não haja sobreposição e nenhum quadrado vazio. Essa solução para o enigma é chamada de ladrilhos do quadrado 8 × 8. Alternativamente, comece colocando sucessivamente trominós na base do tabuleiro (cada uma dessas peças ocupando apenas três quadrados do padrão de grade) e quando todos os 21 estiverem posicionados, coloque a peça quadrada única na posição que permanece disponível. Aqui está o histórico da versão comercial deste quebra-cabeça, comercializado pela Kadon Enterprises.
Na reunião anual de janeiro de 2000 da Associação de Matemática da América, Arthur Benjamin recebeu o prêmio Haimo pelo ensino superior da faculdade. Em seu discurso de aceitação, ele desenhou sua prova favorita por indução. Este raciocínio assegura que um quadrado unilateral de 2n×2n
(ou seja, um tabuleiro de xadrez generalizado com quadrados de 2n ao longo de cada lado) com uma célula ocupada, sempre pode ser azulejado por trominós. Três anos depois de ouvir as observações de Benjamin, eu estava dando uma palestra sobre a indução e me lembrei da sua prova favorita. Complementando meus exemplos preparados, eu adicionei esse argumento clássico, devido a Solomon Golomb. Pensando que um enigma real desse tipo adicionaria um elemento da realidade e poderia suscitar interesse no método de indução, enviei uma nota a Kadon, um fabricante líder de quebra-cabeças, para ver se eles tinham algum que eu poderia comprar. Eles não tinham, então eu perguntei se eles fariam algumas para minhas especificações. Uma série de e-mails com Kate Jones, presidente da Kadon, levaram a um enigma do tipo acima ilustrado. Ela sugeriu o uso de várias cores diferentes para os azulejos de trominó, tornando-se um quebra-cabeça mais interessante do que eu originalmente tinha imaginado. Eu optei por telhas mais legais e translúcidas em vez de negrito, opacas e escolheram azul, aqua e ametista para os trominós. Kadon trouxe o quebra-cabeça sob o nome "Vee-21"; Veja www.gamepuzzles.com/polycub2.htm#V21.
Esta versão comercial, em três cores acrílicas vívidas e translúcidas, vem com um folheto de quarenta páginas que oferece uma série de aprimoramentos ao quebra-cabeça básico. Kate contribuiu com algumas extensões do quebra-cabeça, alguns jogos de estratégia de duas pessoas e a sugestão de requisitos de separação de cores para os ladrilhos que alguém poderia tentar. Ela também descobriu as possibilidades estéticas na criação de padrões simétricos. Kate convidou Oriel Maximé a contribuir com alguns dos seus desafios de labirinto para a peça com os trominós, e a brochura inclui uma variedade de modelos retangulares com linhas estrategicamente escolhidas das grades escurecidas para servir como barreiras nas quais as trominós não possam ser colocados. São fornecidos aqui dois enigmas informáticos interativos desse tipo. O enigma por 8 foi desenvolvido por dois dos meus alunos, enquanto um colega departamental contribuiu com o enigma M-by-N. O enigma M-by-N (roda na maioria dos sistemas, mas pode ser lento para carregar) é um pouco mais flexível, permitindo a escolha de qualquer número de linhas e colunas entre 2 e 32 inclusive. O enigma 8-por-8 (roda melhor com o Internet Explorer em um PC) tem uma ação de mouse diferente e é restrito a três cores de trominó. As instruções são fornecidas com cada um. As versões on-line e Kadon têm uma variedade de apelidos incomum, intrigante para crianças de quatro anos, bem como jogadores experientes. História A prova de que, para qualquer número inteiro positivo n, um quadrado de 2n×2n com uma célula ocupada (um quadrado "deficiente") pode sempre ser revestido por trominós é devido a Solomon Golomb. Ele publicou em seu artigo de 1954 [9] no American Mathematical Monthly. Como observado acima, foi para ilustrar o argumento de Golomb para 2n×2n quadrados deficientes que o enigma foi encomendado. O mesmo artigo introduziu o termo trominó e sua generalização, o poliminó. Um poliminó é uma matriz conectada de quadrados idênticos que têm a propriedade de que quaisquer dois quadrados não se toquem ou se encontrem ao longo de uma borda comum inteira. As únicas duas formas de trominó são três quadrados seguidos e a forma em L desse quebra-cabeça, e aqui "trominó" apenas se refere ao último mencionado. A prova de Golomb é um exemplo de primeira linha de indução matemática. Além da pura elegância do argumento, é uma instância rara de uma aplicação não-numérica do método. Isso contrasta com os exemplos e exercícios freqüentemente encontrados nos tratamentos de indução de livros didáticos, que tipicamente consistem em uma variedade de fórmulas para somas finitas, desigualdades e similares. A primeira aparição da prova em um meio popular foi na Revista de Matemática Recreativa de Joseph Madachy (RMM), onde Golomb incluiu na primeira de suas séries de artigos de quatro partes sobre poliminós publicados em RMM [10]. Na coluna seminal de Martin Gardner, 1957 Scientific American, que introduziu poliminós ao público em geral, ele observou que "um quadro com um quadrado desaparecido em qualquer ponto, pode ser coberto por 21 trominós de direita" [6, p. 154]. Para o seu primeiro livro de colunas de Jogos Matemáticos encontrados, Gardner elaborou observando que "um argumento de indução engenhoso demonstra que 21 trominós certas e um monominó irão cobrir o quadro 8 por 8, independentemente de onde o monominó for colocado” [8, p. 126].. O argumento dos ladrilhos de trominó para tabuleiros deficientes e o teorema geral 2n×2n apareceu em uma sucessão de livros desde os artigos Monthly e RMM. Foi explicado nos clássicos Polyominoes de Golomb [11, 1965, pp. 21-22] e na segunda edição desse livro [11, 1994, p. 5]. A segunda edição dá uma rica história e uma extensa pesquisa deste assunto intrigante, e é preenchido com imagens e quebra-cabeças. Suas 22 páginas de referências, citando livros e artigos, são um bônus adicional. O índice de nomes lista 81 indivíduos, alguns poucos referenciados em mais de uma vez no corpo do livro. Muitos destes serão reconhecidos por aficionados a jogos e matemáticos amadores, bem como por profissionais de qualquer área. Uma descrição do livro é dada na revisão [17] por George Martin. Em 1976, Ross Honsberger deu uma aplicação lúcida e detalhada do argumento de Golomb ao quadro de verificador em suas Mathematical Gems II [13, p. 61]. A idéia básica da prova também é mencionada no livro de George E. Martin, dedicado às peças de poliminós [16, pp. 27-28]. A revisão de David Singmaster [22] deste último livro é particularmente interessante, pois dá um belo esboço do assunto e da sua história. Este tópico também é um tópico cada vez mais comum para textos e livros problemáticos. Por exemplo, aparece nos discretos textos de matemática de Susanna Epp [5, p. 234], Richard Johnsonbaugh (que menciona os ladrilhos de trominó de retângulos como surgidos no design de layout VLSI) [14, pp. 58-59], e Kenneth Rosen [20, pp. 247-8]. Trominó também é tratado no livro de Daniel Velleman sobre a construção de provas [26, pp. 271-275] e o problema dos livros de John P. D'Angelo e Douglas B. West [1, p. 75] e por Jiří Herman, Radan Kučera e Jaromír Šimša [12, p. 271]. A ilustração mais cristalina do argumento de Golomb é a "prova sem palavras" de Roger Nelsen, dada em seu segundo livro desse título [19, p. 123]. Esta área de matemática recreativa se beneficiou de um contínuo fluxo de investigação e sugeriu problemas. Em 1985 e 1986, I-Ping Chu e Richard Johnsonbaugh estudaram a questão das ladrilhamento n × n em tabuleiros deficientes, onde n não precisa mais ser uma potência de 2 e, em geral, de placas retangulares deficiente e não deficiente [3, 4 ]. O livro de George Martin incluiu um capítulo inteiro dedicado às túnicas de trominó [16, pp. 23-37]. Os problemas de coloração para azulejos trominó são tratados por Ilvars Mizniks, que reconhece a página de seleção de cores Kadon Vee-21 como inspiração para sua pesquisa [18]. O artigo de 2004 [2], de J. Marshall Ash e Solomon Golomb, sobre o ladrilhamento de trominó de retângulos deficientes, contém vários resultados novos e básicos, um dos quais responde uma velha questão de Chu e Johnsonbaugh. Ash e Golomb terminam com um problema aberto de retângulos com 2 deficiências (retângulos com duas células removidas). A Internet é uma boa fonte de amostras de ladrilhamento e informações. Por exemplo, uma pesquisa em "trominó" e "ladrilhamento" exibe engedrações como aqueles de Alexander Bogomolny em www.cut-the-knot.org/Curriculum/Games/TrominoPuzzle.shtml e Christopher Mawata em www.utc.edu/Faculty/Christopher-Mawata/trominos/, que ilustram enigmas trominó de vários tamanhos. Variações Aqui estão algumas extensões do enigma trominó que os leitores podem considerar. O primeiro foi sugerido por meu irmão Raymond (Pete), que perguntou como alguém poderia organizar trominós na grade 8x8 para maximizar o número de quadrados desocupados. Isso pode ser elaborado: uma rota presumirá que os azulejos e a grade são ligadas a velcro para que eles permaneçam no lugar, enquanto, alternativamente, pode-se permitir que as peças deslizem de modo a permitir espremer o maior número possível de telhas (sempre dentro das linhas da grade). Pete não estava ciente de que a versão velcro é uma variação do quebra-cabeça de posicionamento pentaminó da Golomb, como descrito por Gardner [7, p. 128] e [8, p. 133]. Golomb estendeu este enigma a um jogo pentaminó de duas pessoas [7, p. 128] e [8, pp. 133-135], regras para as quais poderiam ser aplicadas também ao enigma trominó. David Klarner informou sobre um jogo de pentaminó de duas pessoas, Pan-Kāi (desenvolvido por Alex Randolph e publicado em 1961 pela Phillips Publishers), que incluiu a seguinte restrição: "a regra mais importante é que é proibido tocar uma peça dentro de uma região fechada do tabuleiro se menos de 5 células permanecerem desocupadas, a menos que o movimento preencha exatamente a região ". [15, p. 8] (Veja [21, página 75] para obter mais informações sobre Randolph e Pan-Kāi.) Outra direção é tridimensional. Considere um cubo de comprimento lateral 2n, contendo 23n células unitárias, uma das quais está ocupada (deficiência única). As células restantes podem ser revestidas com trominós tridimensionais (três cubos em forma de L, dois deles reunindo o terceiro em duas faces adjacentes do último)? A condição necessária para que 2n = 3k + 1 seja suficiente também. [23, Capítulo 6: Norton Starr 3-Dimensional Tromino Tiling], [24, pp. 72-87], e [25] O caso de um cubo de 4 × 4 × 4 apresenta alguns desafios modestos que podem divertir jogadores jovens. Problemas mais simples facilmente surgem por conta própria e foram considerados por muitos outros. Por exemplo, as matrizes completas de 3 × 3 e 6 × 6 podem ser revestidos com trominós? Pode cada matriz deficiente de 5 × 5 e 7 × 7 ser revestida? Estes dois últimos enigmas são mais desafiantes do que os casos completos de 3 × 3, 6 × 6 e de 8 × 8 deficientes. Mais adiante, os leitores podem considerar as inclinações de várias matrizes retangulares - veja as referências abaixo. Ao usar uma versão com mais de uma cor de trominó, como o Kadon Vee-21, considere várias restrições de cores. Por exemplo, tente arrumar os azulejos para que nenhum dos da mesma cor compartilhe uma borda. Na direção oposta, tente agrupar o maior número possível de telhas de uma cor. Para ambos os tipos de padrões, tente mais para fazer a telha parecer simétrica sobre uma diagonal ou sobre uma linha horizontal ou vertical. As oportunidades de diversão e descoberta são numerosas. Retângulos de diferentes tamanhos podem ser estudados clicando no enigma M-by-N. Para experiências de padrões de cores, o enigma Kadon é o melhor. Referências
|
