Movendo Cavalos

Contexto Histórico
Em 1512, o matemático Italiano Paolo Guarini de Forli (1464-1520) apresentou um desafio de permutação cromática conhecido como “Quatro Cavalos”. Considere o tabuleiro do xadrez e as posições de cavalos brancos e cavalos pretos conforme a figura abaixo:

O problema consistia em saber se era possível e, se sim, qual seria o menor número necessário de movimentos para que os cavalos brancos e os cavalos pretos trocassem de posição, isto é, os cavalos brancos passariam a ocupar a posição inicial dos pretos e os cavalos pretos passariam a ocupar a posição inicial dos brancos. Somente poderiam ser utilizadas as casas destacadas do tabuleiro. 

Apesar de parecer simples em um tabuleiro reduzido, a tarefa se tornava complexa à medida que o desafio era alterado.

Em matemática é comum ter como estratégia transformar um problema em outro equivalente, porém com um cenário mais simples. Neste desafio mostraremos que este problema e algumas de suas variantes são mais facilmente estudados ao usarmos a abordagem da Teoria dos Grafos. Há casos, a despeito da complicada movimentação do cavalo no tabuleiro, em que os desafios passam a ser vistos como uma simples movimentação de rotação.

Os estudos formais em grafos datam do século XVIII e com grande influência do matemático suíço Leonhard Euler (1707-1783), que propôs uma solução para o problema das Pontes de Königsberg, em que era necessário encontrar um caminho que cruzasse cada uma das sete pontes da cidade de Königsberg exatamente uma vez e terminasse no mesmo ponto de partida. Euler abordou o problema usando uma representação gráfica e seu trabalho estabeleceu as bases para o estudo formal da teoria dos grafos.

Descrição

É dado um tabuleiro 3 por 3 com quatro cavalos posicionados nas extremidades do tabuleiro, como na figura abaixo:

O objetivo do desafio é movimentar os cavalos conforme as regras do movimento do cavalo no xadrez, em L, de forma que os cavalos pretos e brancos troquem sua posição inicial para uma das quatro novas posições sugeridas abaixo:

Mais especificamente, os cavalos se movem em “L”, assim como no jogo do xadrez, ou seja: duas casas horizontalmente e uma verticalmente, ou duas casas verticalmente e uma horizontalmente. É importante lembrar que não é permitido que dois cavalos ocupem o mesmo quadrado em nenhum momento do jogo.

Tente resolver esse desafio:

Saiba mais:

Você pode encontrar outros desafios em: portal da OBMEP.

Como fazer em casa/ na escola

• Materiais Necessários:
  • Uma folha sulfite;
  • Lápis e régua;
  • 4 tampinhas de refrigerantes (2 de uma cor, 2 de outra cor);
  • Canetas ou lápis coloridos.

• Instruções para Montagem:
  • Comece desenhando um quadrado 3×3 na folha sulfite. Isso criará uma grade com nove espaços quadrados.
  • Deixe os quatro quadrados nos cantos e o quadrado central sem pintar, pinte os demais. Isso criará um tabuleiro de jogo.
  • Pegue duas tampinhas de refrigerante de uma cor (por exemplo, vermelhas) e duas tampinhas de outra cor (por exemplo, azuis).
• Feito isso, é só começar a jogar!