Com a temporada da liga profissional de futebol americano em andamento nos Estados Unidos, buscas por tabela de jogos e por clássicos entre times rivais disparam toda semana. Quem acompanha os placares percebe um padrão curioso: aparecem 17, 20, 23, 24, 27, mas quase nunca 1 ou 5. Isso não é acaso. Por trás de cada placar existe uma pergunta clássica de teoria dos números: quais inteiros podem ser escritos como soma de valores fixos?
Quanto vale cada jogada
Pelas regras do futebol americano profissional, um touchdown vale 6 pontos. Depois dele, o time tenta a conversão: o chute extra vale 1 ponto e a jogada de conversão de 2 vale 2. O field goal vale 3 pontos e o safety vale 2. Agrupando o touchdown com a conversão, as “jogadas completas” valem 2, 3, 6, 7 ou 8 pontos.
O ponto de 1 nunca aparece sozinho: ele só existe como complemento de um touchdown. Por isso, para o placar final, o que importa é o conjunto .
O conceito: combinações lineares com coeficientes naturais
Um placar é possível quando existem números naturais (quantas vezes cada jogada aconteceu) tais que:
Repare que 6, 7 e 8 não acrescentam nada de novo: 6 = 3 + 3, 7 = 2 + 2 + 3 e 8 = 2 + 3 + 3. Então basta estudar 2 e 3. Todo número par a partir de 2 é soma de vários 2; todo ímpar a partir de 3 é um 3 mais vários 2. Resultado: todo inteiro é alcançável, e o 1 é o único buraco (além do 0, que é o placar de quem não pontuou).
O problema da moeda (ou dos nuggets)
Agora imagine uma liga fictícia em que só existem jogadas de 3 e de 7 pontos. Essa é a versão esportiva do famoso problema da moeda: com moedas de 3 e 7, que valores você consegue pagar sem troco? A mesma pergunta ficou conhecida como problema dos nuggets, por causa de caixas vendidas em quantidades fixas.
Dois fatos organizam tudo. Primeiro, se , só múltiplos de são alcançáveis, e infinitos números ficam de fora. Segundo, se , existe um maior número impossível, chamado número de Frobenius:
Para 3 e 7, . A quantidade de placares impossíveis também tem fórmula: , que dá 6. De fato, a lista é 1, 2, 4, 5, 8 e 11.
Exemplo resolvido: de quantas formas se chega a 24?
Na liga fictícia de jogadas de 3 e 7, um time terminou com 24 pontos. Quais combinações de jogadas são possíveis? Queremos as soluções naturais de .
- Como b é o coeficiente do valor maior, ele tem poucas opções: 7b não pode passar de 24, então b vale 0, 1, 2 ou 3.
- Use divisibilidade para filtrar: 24 - 7b precisa ser múltiplo de 3. Como 7 deixa resto 1 na divisão por 3 e 24 deixa resto 0, b precisa ser múltiplo de 3.
- Dos candidatos, sobram b = 0 e b = 3.
- Para b = 0: 3a = 24, logo a = 8 (oito jogadas de 3 pontos).
- Para b = 3: 3a = 24 - 21 = 3, logo a = 1 (uma jogada de 3 e três de 7).
- Verificação: 3 · 8 + 7 · 0 = 24 e 3 · 1 + 7 · 3 = 3 + 21 = 24. As duas combinações estão certas e não há outras.
Por que tudo a partir de 12 funciona
O argumento é elegante: 12 = 3 · 4, 13 = 3 · 2 + 7 e 14 = 7 · 2. São três números consecutivos alcançáveis. Como somar uma jogada de 3 leva cada um deles ao próximo da mesma classe de resto, 15, 16, 17 e todos os seguintes também são alcançáveis. Três consecutivos bastam porque o menor valor é 3: é a mesma ideia de indução que aparece em demonstrações de divisibilidade.
Erros comuns
- Achar que mdc igual a 1 garante tudo. Garante que, a partir de certo ponto, tudo é alcançável, mas não que todo número seja. Com 3 e 7, o 11 continua impossível.
- Aceitar coeficientes negativos. A equação tem solução inteira (, ), mas ninguém marca “menos dois field goals”. No problema da moeda, os coeficientes precisam ser naturais.
- Esquecer de testar todos os valores de b. Parar na primeira solução encontrada faz perder combinações, como no exemplo do 24.
- Contar o ponto extra como jogada independente. Ele depende do touchdown; tratá-lo como jogada solta levaria à conclusão errada de que um placar de 1 é possível.
Perguntas frequentes
Um time pode terminar um jogo com 1 ponto?
Não. O ponto extra só existe depois de um touchdown, e as jogadas que pontuam sozinhas valem 2 ou mais. Como 2 e 3 geram todo inteiro a partir de 2, o único placar final impossível é 1.
O que é o número de Frobenius?
É o maior inteiro que não pode ser escrito como combinação com coeficientes naturais de valores dados. Para dois valores a e b com mdc 1, ele vale ab - a - b. Para 3 e 7, dá 11.
E se os valores tiverem mdc maior que 1?
Aí só múltiplos do mdc são alcançáveis. Com jogadas de 4 e 6, por exemplo, nenhum placar ímpar é possível, e não existe um maior número impossível.
Existe fórmula para três ou mais valores?
Não existe fórmula fechada geral para três ou mais valores. Nesses casos se usam algoritmos ou a análise por restos, como fizemos com 2 e 3.