Solução do Giant Puzzle #8 – Infestação

Parabéns a todos que se desafiaram a solucionar o Giant Puzzle #8!

Conseguiram resolver este puzzle:

  1. Gustavo Coimbra
  2. Bruno Mucciaccia

O Problema

A família de Pei acaba de se mudar para uma velha casa no interior para fugir da vida agitada da cidade. A casa ainda precisa de algumas reformas e os cômodos ainda não estão bem definidos, exceto o quarto de Pei que fica no canto superior esquerdo da casa.

Considere a casa um grid com infinitas linhas e colunas.

Logo nas primeiras noites, ela descobre que seu quarto está infestado de pequenas criaturas chamadas susuwatari.

Essas criaturas têm uma propriedade peculiar: toda vez que uma é capturada, ela desaparece e outras duas surgem – uma imediatamente abaixo e outra a direita da criatura capturada. Pei descobre ainda que não é possível capturar um susuwatari se as posições em que aparecerão as novas criaturas já estiverem ocupadas.

a) Considere que Pei conseguiu encurralar um susuwatari no canto superior do seu quarto com dimensões 3×3. Desenhe uma estratégia que consiga tirar a criatura do quarto dela. Se não conseguir, mostre que é impossível.

b) Qual o número máximo de susuwataris que Pei consegue tirar do seu quarto, se considerarmos que o quarto dela tem dimensões 2021×2021? Conte apenas as criaturas que estão inicialmente no quarto.

 

A Solução

Item A

Vamos usar o conceito de invariante.

Como descrito no problema, sempre que removermos uma criatura do grid, devemos colocar outras duas imediatamente abaixo e à direita.

Considerando que cada célula tem um peso x, a soma dos pesos ocupados pelas criaturas se mantém constante ao capturá-las.

Assim, considerando o canto superior esquerdo como peso 1, temos o grid:

A soma dos pesos do grid completo é:

S1 = 1 + ½ + ¼ + … = 2

S2 = ½ + ¼ + … = 1

S = S1 + S2 + … = 2 + 1 + ½ + … = 4

Agora, calculando o peso do quarto:

1 + ( ½ * 2) + (¼ * 3) + (⅛ * 2) + 1/16 = 3 + 1/16 = 49/16

Então, o peso fora do grid é 15/16.

Voltando ao problema, temos um sussuwatari no canto superior esquerdo com peso 1.

Caso fosse possível removê-lo, existiria uma configuração de criaturas, fora do quarto, em que os pesos combinados some 1.

Como a soma dos pesos fora do quarto é 15/16 < 1, é impossível. Portanto, não existe estratégia para remover o sussuwatari.

Item B

No problema anterior, mostramos que é impossível remover uma criatura posicionada no canto superior esquerdo de um grid 3X3

Logo, podemos reduzir o problema ao caso.

É fácil ver que conseguimos retirar uma criatura da casa (2021,2021).

Qualquer outra casa adjacente deverá lidar com uma segunda “retirada” da casa (2021,2021).

Vamos mostrar que não conseguimos passar mais de 2 vezes pela casa (2021,2021):

De forma análoga ao item A, temos um quarto de 1X1 e devemos medir quantos sussuwatari conseguimos retirar.

Adotando o grid abaixo, temos:

D(disponível) = S(grid) – 1 = 3

Logo, retirar 1 sussuwatari é possível.

Ao retirar o primeiro, preenchemos o entorno do grid, de forma que, para um sussuwatari chegando ao ponto (2021,2021), temos:

S(disponível) = S(grid) – 2 = 2

Logo, também é possível retirar 2 sussuwatari.

Porém, para um terceiro chegando no ponto (2021,2021), temos um problema equivalente ao de remover os 3 sussuwataris da situação anterior de um grid 2X2.

S(disponível) = S(grid) – 2 – ¼ = 7/4 

Como S(criaturas) = 2 e 2 > 7/4, é impossível tirar 3 criaturas pelo ponto (2021,2021).

Portanto, o número máximo é 2.

Clique aqui para acessar o nosso mais novo puzzle! Esperamos pela sua resposta.

Deixe um comentário

O seu endereço de e-mail não será publicado.

Este site utiliza cookies para aprimorar sua experiência, ou seja, armazenamos dados para análise e para produção de conteúdo adaptado ao seu interesse. Ao clicar em "Aceito" você concorda em armazenar cookies em seu dispositivo. Para saber mais, leia nossa Política de privacidade e Cookies.