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 {2,3,6,7,8}\{2, 3, 6, 7, 8\}.

O conceito: combinações lineares com coeficientes naturais

Um placar PP é possível quando existem números naturais a,b,c,d,ea, b, c, d, e (quantas vezes cada jogada aconteceu) tais que:

P=2a+3b+6c+7d+8e,a,b,c,d,e∈NP = 2a + 3b + 6c + 7d + 8e,\quad a,b,c,d,e \in \mathbb{N}
Placar como combinação linear das jogadas, com coeficientes naturais

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 P≥2P \geq 2 é alcançável, e o 1 é o único buraco (além do 0, que é o placar de quem não pontuou).

0123456789+3+2+2+29 − 0 = 3 + 2 + 2 + 2 = 9
Com só 2 e 3: partindo de 0, um salto de 3 e três saltos de 2 chegam a 9. Todo ímpar a partir de 3 é um 3 mais alguns 2.

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 mdc(a,b)=d>1\mathrm{mdc}(a,b)=d>1, só múltiplos de dd são alcançáveis, e infinitos números ficam de fora. Segundo, se mdc(a,b)=1\mathrm{mdc}(a,b)=1, existe um maior número impossível, chamado número de Frobenius:

g(a,b)=ab−a−bg(a,b) = ab - a - b
Número de Frobenius para dois valores com mdc igual a 1

Para 3 e 7, g=21−3−7=11g = 21 - 3 - 7 = 11. A quantidade de placares impossíveis também tem fórmula: (a−1)(b−1)2\frac{(a-1)(b-1)}{2}, que dá 6. De fato, a lista é 1, 2, 4, 5, 8 e 11.

04812162024+3+7+7+724 − 0 = 3 + 7 + 7 + 7 = 24
Partindo de 0, um salto de 3 e três saltos de 7 chegam a 24: uma das duas formas de obter 24 com jogadas de 3 e 7.

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 3a+7b=243a + 7b = 24.

Resolvendo 3a + 7b = 24 nos naturais
  1. 0≤7b≤24⇒b∈{0,1,2,3}\displaystyle 0 \le 7b \le 24 \Rightarrow b \in \{0,1,2,3\} 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.
  2. 24−7b≡0(mod3)  ⟺  b≡0(mod3)\displaystyle 24 - 7b \equiv 0 \pmod 3 \iff b \equiv 0 \pmod 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.
  3. b∈{0,3}\displaystyle b \in \{0, 3\} Dos candidatos, sobram b = 0 e b = 3.
  4. 3a=24⇒a=8\displaystyle 3a = 24 \Rightarrow a = 8 Para b = 0: 3a = 24, logo a = 8 (oito jogadas de 3 pontos).
  5. 3a=3⇒a=1\displaystyle 3a = 3 \Rightarrow a = 1 Para b = 3: 3a = 24 - 21 = 3, logo a = 1 (uma jogada de 3 e três de 7).
  6. 3⋅8=24,3+21=24\displaystyle 3\cdot 8 = 24,\quad 3 + 21 = 24 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.

12131415161718+3+318 − 12 = 3 + 3 = 6
De 12, 13 e 14 (três seguidos), cada salto de 3 leva ao próximo número com o mesmo resto: 12 → 15 → 18, e assim por diante.

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 3a+7b=13a + 7b = 1 tem solução inteira (a=−2a = -2, b=1b = 1), 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.