O MAIOR VALOR QUE NÃO SE PODE PAGAR, AGORA COM UM LIMITE PRECISO

Imagine um caixa que aceita apenas alguns tipos de moeda, em quantidade ilimitada, e nunca dá troco. Alguns valores podem ser pagos exatamente; outros, nunca. Os matemáticos chamam os valores das moedas de geradores e fazem uma pergunta enganosamente simples: qual é o maior valor que não pode ser pago?

Valores que nunca podem ser pagos

Tome números inteiros a₁ < a₂ < … < aₙ sem nenhum fator compartilhado por todos eles. Um total obtido somando esses números, cada um quantas vezes se quiser, é “representável”. Apenas uma quantidade finita de números inteiros não o é; o maior deles é o número de Frobenius, F. (Se um dos valores for 1, tudo pode ser pago e define-se F = −1.)

Um pequeno exemplo: com moedas de 3, 4 e 6, dá para pagar 3, 4, 6, 7, 8 e todos os valores a partir daí, mas nunca 1, 2 ou 5. Logo, F = 5. Note que 3 e 6 têm um fator em comum; o que importa é que nenhum fator seja comum aos três.

Para duas moedas existe uma resposta exata, a fórmula de Sylvester: F(a₁, a₂) = a₁a₂ − a₁ − a₂. Para três ou mais, o trabalho consiste em limitar F: provar que ele não pode passar de certo valor calculado a partir das moedas.

Um teimoso fator 2

Paul Erdős e Ronald Graham provaram, para três ou mais geradores:

F ≤ 2aₙ₋₁⌊aₙ/n⌋ − aₙ

Aqui aₙ é o maior valor, aₙ₋₁ o segundo maior, n o número de valores, e ⌊ ⌋ significa arredondar para baixo. Assim como a fórmula de Sylvester, ela envolve as duas maiores moedas.

Eles também estimaram o pior caso, o maior F possível quando todos os n valores são no máximo t. A distância entre suas estimativas, de aproximadamente um fator 2, levou a uma conjectura registrada como Problema de Erdős nº 433. Jacques Dixmier a resolveu e também provou um limite mais simples, válido para qualquer conjunto: F ≤ aₙ²/(n − 1). O fator 2 sumiu, mas a segunda maior moeda também.

Mantendo as duas maiores moedas

Lin Chen, Tingwei Hu, Yuchen Mao e Guochuan Zhang, da Faculdade de Ciência e Tecnologia da Computação da Universidade de Zhejiang, queriam as duas coisas: nenhum fator 2 e a segunda maior moeda mantida. A resposta deles, válida para qualquer conjunto de dois ou mais valores:

F ≤ aₙ₋₁⌈aₙ/(n − 1)⌉ − aₙ − 1

Aqui ⌈ ⌉ significa arredondar para cima. Em comparação com Erdős e Graham, o fator 2 desapareceu, ao preço de dividir por n − 1 em vez de n e de arredondar para cima. Em comparação com Dixmier, o novo limite pode ser bem menor quando a segunda maior moeda é pequena diante da maior.

No exemplo 3, 4, 6, o limite de Erdős e Graham dá 10, o de Dixmier dá 18, e o novo dá 4 × 3 − 6 − 1 = 5, exatamente o valor verdadeiro. Nenhuma surpresa: esse conjunto pertence à família de casos extremos descrita abaixo, construída para atingir o limite exatamente; o artigo não traz nenhuma comparação em conjuntos típicos.

Classificando os valores pelo resto

A prova segue o caminho de Erdős e Graham. Classifique cada valor pelo resto da divisão pela maior moeda, aₙ. Assim que uma soma das moedas menores atinge determinado resto, acrescentar cópias de aₙ alcança todos os valores maiores com esse mesmo resto. A tarefa é mostrar que todo resto pode ser alcançado a baixo custo.

A ferramenta-chave é o teorema de Kneser, que diz quão grande um conjunto de somas precisa ser. Erdős e Graham o usaram para mostrar que somas de cerca de aₙ/n moedas cobrem mais da metade dos restos, e depois dobraram a aposta para cobrir todos. Cada moeda nessas somas vale no máximo aₙ₋₁, então dobrar o número de moedas dobra o custo: daí o fator 2.

A nova prova usa somas de ⌈aₙ/(n − 1)⌉ moedas. Quando essas somas deixam de alcançar alguns restos, o teorema de Kneser diz que os restos que faltam não estão espalhados ao acaso: eles formam famílias inteiras de restos espaçados em intervalos regulares. Quanto mais famílias faltam, mais as moedas menores precisam se amontoar em cada família alcançada; assim, cada uma dessas famílias contém algumas moedas pequenas, e as poucas moedas extras necessárias para alcançar as famílias que faltam saem baratas. O total nunca passa de ⌈aₙ/(n − 1)⌉ × aₙ₋₁.

Esse primeiro passo dá o limite sem o seu “− 1” final. A última unidade vem de um argumento separado, baseado em um teorema de Scherk e Kemperman sobre somas que só podem ser formadas de uma única maneira: ele mostra que o próprio valor-limite aₙ₋₁⌈aₙ/(n − 1)⌉ − aₙ sempre pode ser pago. Segundo os agradecimentos, os autores provaram primeiro o limite mais fraco; o GPT-6 depois ajudou a encontrar o argumento que o reduz em uma unidade, e também auxiliou na prova de que o limite não pode ser rebaixado e na revisão do inglês. Os autores declaram assumir a responsabilidade pelo manuscrito final.

Casos que atingem o limite exatamente

Esse limite não pode ser rebaixado: para todo n ≥ 3, os autores constroem infinitos conjuntos em que F é exatamente igual a ele. Tome qualquer q ≥ 2 e os valores q, 2q, …, (n − 1)q, mais (n − 2)q + 1. Todos menos um são múltiplos de q, então não pagam nada que q sozinho não pague. O conjunto se comporta como duas moedas, q e (n − 2)q + 1, e a fórmula de Sylvester dá um F que coincide exatamente com o novo limite. Com n = 3 e q = 3, essa receita produz precisamente o exemplo 3, 4, 6 acima.

Menos moedas, um teto mais baixo

O limite também pode ser lido em termos de densidade. Ele se aplica a qualquer conjunto reduzido formado pelos i menores valores mais o maior, desde que esses valores ainda não tenham nenhum fator comum. Retirar moedas só pode dificultar o pagamento, então um teto provado para o conjunto reduzido também vale para o conjunto completo. O que controla o resultado é aproximadamente aᵢ/i, o inverso da densidade com que os i primeiros valores preenchem os números de 1 a aᵢ: o grupo mais denso vence. Em particular, observam os autores, a segunda maior moeda pode simplesmente ser deixada de lado sempre que as moedas restantes ainda não tiverem nenhum fator comum a todas elas.

O artigo permanece puramente teórico: não dá nenhum número sobre quanto o novo limite é menor em conjuntos típicos de moedas, e o fato de ele não poder ser rebaixado só é provado para três valores de moeda ou mais.