.Desafio: Grupo de dois

Problema
(Indicado a partir do 7º ano do E. F.)

Jogo

• Dez palitos de fósforo estão alinhados.
• Você pode formar pares movendo um palito, de modo que ele pule dois outros e seja colocado sobre o terceiro, respeitando sempre a disposição dos palitos no momento da movimentação.
• Depois de formado um par, esse permanece na fileira e não poderá ser desfeito!
• O objetivo do jogo é formar cinco pares, utilizando-se todos os palitos.

Clique no botão a seguir para comprovar que o jogo tem solução.

Para indicar cada passo do jogo, você pode usar a seguinte notação: Passo 1: 1-4 2 3 5 6 7 8 9 10 Passo 2: 1-4 2 3-7 5 6 8 9 10 Passo 3: 1-4 2 3-7 6 8 9-5 10 Passo 4: 1-4 3-7 6-2 8 9-5 10 Passo 5: 1-4 3-7 6-2 9-5 10-8.

Encontre todas as soluções para esse problema e descreva os respectivos passos.

Observação: Soluções com movimentações diferentes dos palitos são consideradas soluções diferentes; mesmo que conduzam aos mesmos pares finais.

Você pode utilizar um APPLET para ajudar na solução do problema. É só clicar no botão abaixo!

Solução

(I) Dois palitos podem ficar isolados em um “canto”? Vamos analisar a primeira situação. Para a segunda, o raciocínio será análogo.

(a) Observe que nessa disposição não podemos movimentar o palito azul, pois de um lado dele não existem palitos e do outro lado não existem dois palitos isolados e consecutivos, de modo que ele possa pular “os dois e ser colocado sobre um terceiro”. Nenhum outro palito formará par com esse palito (1) nesse momento; pois ele só seria o terceiro de uma sequência de três palitos (dois para serem pulados e ele para receber o seu par), se desmontássemos o X que ocupa a terceira posição (3), o que não é permitido pelas regras do jogo. (b) Para formarmos um par com o palito rosa, teríamos, a princípio, duas opções. Mas, observe que, depois de executarmos qualquer um dos dois movimentos propostos, não seria possível formarmos um par com o palito azul.

Assim, dois palitos não podem ficar isolados em um “canto”. (Proibição (I))

(II) Três palitos podem ficar isolados em um “canto”? Vamos analisar a primeira situação. Para a segunda, novamente o raciocínio será análogo.

(a) Observe que nessa disposição não podemos movimentar nenhum dos palitos azuis, segundo a regra do jogo. Com efeito, do lado esquerdo do palito (1) não existem outros palitos e, do lado direito, ao pular os dois palitos consecutivos, não existe um terceiro palito isolado para que o palito (1) possa ser colocado sobre ele e formar um par. Com relação ao palito (2), tanto do seu lado esquerdo como do direito, só existe um palito isolado, logo o palito (2) não pode ser movimentado segundo as regras do jogo. Também, nenhum outro palito formará par com os palitos (1) e (2), já que eles só seriam o quarto de uma sequência de quatro palitos (um a ser movimentado, dois para serem pulados e cada um deles para receber o seu respectivo par) se desmontássemos o X que ocupa a quarta posição, o que não é permitido. (b) O palito rosa pode ser movimentado e também é o terceiro de uma sequência de três palitos. Assim, teríamos as próximas opções de movimento. Mas depois de executarmos qualquer um desses movimentos, não seria possível formarmos pares com os palitos azuis nos demais movimentos.

Assim, três palitos não podem ficar isolados em um “canto”. (Proibição (II))

(IV) Seis palitos podem ficar isolados ?

Como pares não podem ser desfeitos, qualquer uma das três situações equivaleria a jogar o jogo com seis palitos e, nesse caso, o próximo movimento nos levaria necessariamente a uma das próximas configurações. Na primeira e segunda configurações teríamos a Proibição (III): quatro palitos isolados em um “canto”. Nas terceira e quarta configurações teríamos a Proibição (II): três palitos isolados em um “canto”. Nas duas últimas configurações teríamos a Proibição (I): dois palitos isolados em um “canto”.

Assim, seis palitos não podem ficar isolados, ou seja, não podemos jogar o jogo com seis palitos. (Proibição (IV))

Tendo em vista as Proibições (I) e (II), após o primeiro passo a sequência dos dez palitos deve ficar em uma das formas abaixo. Vamos analisá-las uma a uma quanto aos próximos passos no jogo.

(a) Observe que, embora produzidas por movimentos iniciais distintos, a posição dos palitos nas situações E e F são iguais.
e tanto à esquerda quanto à direita do X temos a Proibição (III): quatro palitos isolados em um “canto”.
Assim, com as situações E e F não finalizamos o jogo.

(b) Analisemos, agora os casos A e B. Neles, podemos, a partir do segundo passo, considerar uma sequência de 8 palitos. Devido às Proibições (I) e (II), uma sequência de oito palitos, após o próximo passo (o segundo passo do jogo), vai ficar em uma das formas mostradas abaixo.

■ Para os casos AB₁ e AB₄, teremos que nos ater a uma sequência de seis palitos. Mas, de acordo com a Proibição (IV), não podemos concluir o jogo a partir dessa configuração.

Portanto, nos casos AB₁ e AB₄ não conseguimos finalizar o jogo.

■ Analisemos o caso AB₂. Após o próximo passo, obteremos uma das sequências a seguir.

– As sequências (1), (4) e (5) configuram, respectivamente, as Proibições (III), (II), (I).
– A sequência (3) é análoga à da Proibição (II): três palitos isolados em um “canto”.
– Para a sequência (2) há oito possibilidades de conclusão do jogo, a partir da configuração A:

e oito possibilidades de conclusão do jogo, a partir da configuração B:

■ A análise do caso AB₃ é análoga ao caso AB₂. Temos, então, mais dezesseis soluções para o jogo.

(c) Vamos ao caso C. Após o próximo movimento, teríamos uma das seguintes configurações.

■ Para os casos (6), (7), (8) e (9) teremos as Proibições (IV), (II), (I), (III), respectivamente. Logo não poderemos concluir o jogo a partir dessas configurações.
■ No caso (11), não é possível formar um par com o primeiro palito e, portanto, o jogo não poderá ser concluído.
■ A sequência (12), apresenta a configuração da Proibição (III). Assim, temos mais uma sequência sem possibilidade para a conclusão do jogo.
■ Resta-nos apenas a sequência (10) e esta é a sequência AB₂, obtida a partir da configuração B com o movimento 2-5 sendo feito antes do 7-10. Temos, então, mais oito soluções.

(d) Resta, apenas, o caso D e este é análogo ao caso C. Temos, então, mais oito soluções.

Finalmente, dentro do espírito do que foi definido como solução do jogo,
temos exatamente 48 soluções

Solução elaborada pelos Moderadores do Blog.

Explorando a solução

[tex]\bigstar \, \, \, [1,3] \, [2,6] \, [4,8] \, [5,9] \, [7,10] \\
\bigstar \, \, \, [1,3] \, [2,6] \, [5,9] \, [4,8] \, [7,10] \\
\bigstar \, \, \, [1,4] \, [2,5] \, [3,8] \, [6,9] \, [7,10] \\
\bigstar \, \, \, [1,4] \, [2,5] \, [3,8] \, [7,10] \, [6,9] \\
\bigstar \, \, \, [1,4] \, [2,5] \, [6,9] \, [3,8] \, [7,10] \\
\bigstar \, \, \, [1,4] \, [2,6] \, [3,7] \, [5,9] \, [8,10] \\
\bigstar \, \, \, [1,4] \, [2,6] \, [3,7] \, [8,10] \, [5,9] \\
\bigstar \, \, \, [1,4] \, [3,7] \, [2,6] \, [5,9] \, [8,10] \\
\bigstar \, \, \, [1,4] \, [3,7] \, [2,6] \, [8,10] \, [5,9] \\
\bigstar \, \, \, [1,4] \, [3,8] \, [2,5] \, [6,9] \, [7,10]\\
\bigstar \, \, \, [1,4] \, [3,8] \, [2,5] \, [7,10] \, [6,9] \\
\bigstar \, \, \, [2,5] \, [1,4] \, [6,9] \, [3,8] \, [7,10] \\
\bigstar \, \, \, [2,5] \, [1,4] \, [3,8] \, [6,9] \, [7,10] \\
\bigstar \, \, \, [2,6] \, [1,3] \, [4,8] \, [5,9] \, [7,10] \\
\bigstar \, \, \, [2,6] \, [1,3] \, [5,9] \, [4,8] \, [7,10].[/tex]

A seguir mostramos a frequência dessas configurações nos 48 movimentos possíveis:

[tex]\bigstar \, \, \, [1,3] \, [2,6] \, [4,8] \, [5,9] \, [7,10] \, (2 \, conjuntos \, de \, movimentos)\\
\bigstar \, \, \, [1,3] \, [2,6] \, [5,9] \, [4,8] \, [7,10] \, (2 \, conjuntos \, de \, movimentos)\\
\bigstar \, \, \, [1,4] \, [2,5] \, [3,8] \, [6,9] \, [7,10] \, (8 \, conjuntos \, de \, movimentos) \\
\bigstar \, \, \, [1,4] \, [2,5] \, [3,8] \, [7,10] \, [6,9] \, (4 \, conjuntos \, de \, movimentos) \\
\bigstar \, \, \, [1,4] \, [2,5] \, [6,9] \, [3,8] \, [7,10] \, (4 \, conjuntos \, de \, movimentos) \\
\bigstar \, \, \, [1,4] \, [2,6] \, [3,7] \, [5,9] \, [8,10] \, (2 \, conjuntos \, de \, movimentos)\\
\bigstar \, \, \, [1,4] \, [2,6] \, [3,7] \, [8,10] \, [5,9] \, (2 \, conjuntos \, de \, movimentos)\\
\bigstar \, \, \, [1,4] \, [3,7] \, [2,6] \, [5,9] \, [8,10] \, (2 \, conjuntos \, de \, movimentos) \\
\bigstar \, \, \, [1,4] \, [3,7] \, [2,6] \, [8,10] \, [5,9] \, (2 \, conjuntos \, de \, movimentos) \\
\bigstar \, \, \, [1,4] \, [3,8] \, [2,5] \, [6,9] \, [7,10] \, (4 \, conjuntos \, de \, movimentos) \\
\bigstar \, \, \, [1,4] \, [3,8] \, [2,5] \, [7,10] \, [6,9] \, (4 \, conjuntos \, de \, movimentos) \\
\bigstar \, \, \, [2,5] \, [1,4] \, [6,9] \, [3,8] \, [7,10] \, (4 \, conjuntos \, de \, movimentos) \\
\bigstar \, \, \, [2,5] \, [1,4] \, [3,8] \, [6,9] \, [7,10] \, (4 \, conjuntos \, de \, movimentos) \\
\bigstar \, \, \, [2,6] \, [1,3] \, [4,8] \, [5,9] \, [7,10] \, (2 \, conjuntos \, de \, movimentos)\\
\bigstar \, \, \, [2,6] \, [1,3] \, [5,9] \, [4,8] \, [7,10] \, (2 \, conjuntos \, de \, movimentos).[/tex]

Observe que determinados pares de palitos podem se apresentar em posições diferentes na configuração final, gerando soluções distintas. Por exemplo, [tex] \, [1,3] \, [2,6] \, [4,8] \, [5,9] \, [7,10] \, [/tex] e [tex] \, [1,3] \, [2,6] \, [5,9] \, [4,8] \, [7,10] \, [/tex] são disposições finais distintas de um mesmo conjunto de pares de palitos.
Assim, se não levarmos em consideração a posição dos pares na configuração final temos apenas três conjuntos de pares de cinco palitos nas configurações possíveis: