Por Darren Glass
Estes quebra-cabeças são montados em um esquema gráfico onde cada nó é nomeado com um número inteiro. Pense nestes nós como se fossem pessoas e os números inteiros como uma quantia em dinheiro (ou como dívida) que essas pessoas possuem no banco. A cada rodada, escolha um nó; você tanto pode dar um real a cada um dos vizinhos quanto pegar um real emprestado de cada um dos vizinhos. Os movimentos preservam a quantidade total de reais no sistema, então se a quantia total inicial não é negativa, a princípio seria possível fazer uma sequência de movimentos que eventualmente deixarão todos os nós sem débitos. Para cada um dos quebra-cabeças abaixo, tente encontrar uma sequência de movimentos que fará com que nenhum nó esteja em débito, ou explique porque tal sequência de movimentos não existe.
Geralmente, é difícil dizer quando existe uma estratégia vencedora para um determinado quebra-cabeça. Um teorema atribuído a Baker e Norine, provado no artigo "Riemann-Roch and Abel-Jacobi theory on a finite graph" (que pode ser baixado aqui), posicionam esses quebra-cabeças em jogos do tipo chip-firing, de contexto mais geral, e fornecem uma resposta parcial a esta questão.
Teorema 0.1: Assuma que tenhamos um quebra-cabeça com A arestas, N nós, e R reais no total em um sistema. Se R > A – N, então existe uma estratégia vencedora. Além disso, para cada 0 ≤ R ≤ A – N existem tanto quebra-cabeças com estratégias vencedoras quanto não vencedoras. Conhecer este teorema fornece um modo de chegar rapidamente na resposta de quebra-cabeças que podem mantê-lo ocupado em longas viagens de avião ou em reuniões de comitê particularmente entediantes: desenhe um esquema gráfico com N nós e A arestas e uma configuração inicial com um total de A – N + 1 reais distribuídos entre os nós e tente em seguida encontrar uma estratégia vencedora. Também é interessante experimentar com exemplos com A – N reais para os quais não existe estratégia vencedora!
Quebra-cabeça "crise monetária" 1
Quebra-cabeça "crise monetária" 2
Quebra-cabeça "crise monetária" 3
Quebra-cabeça "crise monetária" 4
Quebra-cabeça "crise monetária" 5
Quebra-cabeça "crise monetária" 6
Sobre o autor: Darren Glass é um membro do Departamento de Matemática na Universidade Gettysburg. Este artigo saiu na revista MAA Focus, edição de Ago/Set - 2012.
Solução deste quebra-cabeça: Começamos com a observação de que as soluções destes quebra-cabeças não são únicas. Em particular, fazendo o 'empréstimo' uma vez para cada um dos vértices nos leva de volta ao ponto de início do jogo. Além disso, o ato de 'pegar emprestado' equivale a 'emprestar' em cada um dos demais vértices. Em particular, sem perda de generalidade, assume-se que exista (ao menos) um vértice para o qual não se toma nenhuma ação e para os demais vértices faça-se o 'empréstimo' um número não negativo de vezes. Abaixo temos possíveis soluções para 4 dos 6 quebra-cabeças em que foram eliminados todos os débitos monetários.
Solução do quebra-cabeça 1
Solução do quebra-cabeça 2
Solução do quebra-cabeça 5
Solução do quebra-cabeça 6
Os quebra-cabeças 3 e 4 não têm solução. Em ambos os casos, notamos que o sistema possui zero reais líquidos; então, a fim de que nenhum nó fique em débito temos que mover para uma posição onde cada nó tenha exatamente zero reais. No quebra-cabeça 3, notamos ainda que isto significa que deve-se 'emprestar' da aresta superior direita e da aresta inferior esquerda o mesmo número de vezes devido à simetria. Ao se fazer isto, a número de reais nos outros dois nós será ímpar, e portanto não conseguem zerar. Para observar que o quebra-cabeça 4 não possui solução, focamos nossa atenção nos dois nós do canto inferior esquerdo do esquema gráfico. Em particular, assuma que x é o número de reais no nó central esquerdo e y é o número de reais do nó inferior esquerdo, de tal modo que inicialmente x = 3, y = -2, e a quantidade x - y = 5. Observa-se que qualquer movimento válido mudará a quantidade x - y por um múltiplo de 3, e em particular nunca seremos capazes de obter x - y = 0. Isto mostra que não há uma maneira de eliminar o débito desse esquema gráfico.
