Antigamente existiam marcianos de 3 cores diferentes: vermelhos, verdes e azuis. Como Marte foi devastada por uma guerra intergaláctica, sobraram apenas 2 marcianos de cada uma das cores. Para reconstruir a população marciana, eles decidiram usar uma máquina que transforma dois marcianos, de cores distintas, em quatro marcianos com a cor diferente dos dois iniciais. Por exemplo, se um marciano vermelho e um marciano azul usassem a máquina, eles seriam transformados em quatro marcianos verdes.
É possível que, após usar essa máquina um número finito de vezes, tenhamos 2023 marcianos vermelhos, 2024 marcianos verdes e 2025 marcianos azuis?
Passo 1
Resumindo o enunciado: começamos com marcianos de cada cor. A máquina, ao receber dois marcianos de cores distintas e , elimina um de cada e cria quatro do terceiro tipo . Cada operação, portanto, transforma
com uma das três possibilidades de troca, e queremos saber se é possível chegar a em um número finito de operações. Vamos usar invariantes de contagem total (paridade) e congruências módulo 3 para decidir.
Passo 2
Calcular quantas operações são necessárias para ajustar o total de marcianos. O total inicial é
e o total desejado é
Como cada operação aumenta o total em , se usarmos operações teremos total
logo
que é inteiro. Portanto a contagem total não obstrui a possibilidade.
Passo 3
Verificar a paridade do total. O número total de marcianos é sempre par pois partimos de e adicionamos a cada operação. O total final também é par. Logo não há contradição de paridade.
Passo 4
Usar restrições módulo 3 nas quantidades de cada cor. Note que, em cada operação que converte duas cores distintas em cor , o vetor de mudança é, em , igual a
em ordem apropriada. Chamando de , e os vetores de mudança módulo 3 quando se produz vermelho, verde ou azul, obtemos a matriz de geração
cujo determinante em é
Como é invertível, qualquer alvo módulo 3 é alcançável. O estado inicial em bmod3 é (2,2,2) e o alvo é
(2023,2024,2025)equiv(1,2,0)pmod3
Logo existe combinação de kR,kG,kB operações de cada tipo tal que
(2,2,2)+kRVR+kGVG+kBVBequiv(1,2,0)pmod3
juntamente com kR+kG+kB=3033. Resolvendo em bmod3 achamos uma solução consistente.
Passo 5
Como as condições de total (inteiro k=3033), paridade (sempre par) e congruências módulo 3 não apresentam impedimento e o sistema de vetores VR,VG,VB gera todo F3^3, conclui-se que existem escolhas de sequências de operações que conduzem de (2,2,2) a (2023,2024,2025).