LA MAYOR CANTIDAD QUE NO SE PUEDE PAGAR, AHORA ACOTADA AL MILÍMETRO

Imagina una caja registradora que solo acepta unos pocos tipos de monedas, en cantidad ilimitada, y que nunca da cambio. Algunas cantidades se pueden pagar exactamente; otras, jamás. Los matemáticos llaman a los valores de las monedas generadores y se plantean una pregunta engañosamente sencilla: ¿cuál es la mayor cantidad que no se puede pagar?

Cantidades que nunca se pueden pagar

Tomemos números enteros a₁ < a₂ < … < aₙ sin ningún factor compartido por todos ellos. Un total obtenido sumando estos números, cada uno tantas veces como se quiera, es «representable». Solo un número finito de enteros no lo son; el mayor es el número de Frobenius, F. (Si uno de los valores es 1, todo se puede pagar y se fija F = −1.)

Un ejemplo pequeño: con monedas de 3, 4 y 6 se puede pagar 3, 4, 6, 7, 8 y cualquier cantidad a partir de ahí, pero nunca 1, 2 o 5. Así que F = 5. Fíjate en que 3 y 6 comparten un factor; lo que importa es que ningún factor sea común a los tres.

Para dos monedas hay una respuesta exacta, la fórmula de Sylvester: F(a₁, a₂) = a₁a₂ − a₁ − a₂. Para tres o más, el trabajo consiste en acotar F: demostrar que no puede superar cierto valor calculado a partir de las monedas.

Un obstinado factor 2

Paul Erdős y Ronald Graham demostraron, para tres o más generadores:

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

Aquí aₙ es el valor más grande, aₙ₋₁ el segundo más grande, n el número de valores, y ⌊ ⌋ significa redondear hacia abajo. Como la fórmula de Sylvester, involucra las dos monedas más grandes.

También estimaron el peor caso, el mayor F posible cuando los n valores son todos como mucho t. La diferencia entre sus estimaciones, de aproximadamente un factor 2, dio lugar a una conjetura registrada como el Problema de Erdős n.º 433 (Erdős Problem #433). Jacques Dixmier la resolvió y demostró además una cota más simple, válida para cualquier conjunto: F ≤ aₙ²/(n − 1). El factor 2 desaparece, pero también la segunda moneda más grande.

Conservar las dos monedas más grandes

Lin Chen, Tingwei Hu, Yuchen Mao y Guochuan Zhang, de la Facultad de Ciencias de la Computación y Tecnología de la Universidad de Zhejiang, querían ambas cosas: sin factor 2 y conservando la segunda moneda más grande. Su respuesta, válida para cualquier conjunto de dos o más valores:

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

Aquí ⌈ ⌉ significa redondear hacia arriba. En comparación con Erdős y Graham, el factor 2 ha desaparecido, a cambio de dividir entre n − 1 en lugar de n y redondear hacia arriba. En comparación con Dixmier, la nueva cota puede ser sustancialmente menor cuando la segunda moneda más grande es pequeña frente a la mayor.

En el ejemplo 3, 4, 6, la cota de Erdős y Graham da 10, la de Dixmier da 18, y la nueva da 4 × 3 − 6 − 1 = 5, exactamente el valor real. No es ninguna sorpresa: este conjunto pertenece a la familia de casos extremos descrita más abajo, construida para alcanzar la cota exactamente; el artículo no ofrece ninguna comparación con conjuntos típicos.

Clasificar las cantidades por su resto

La demostración sigue el camino de Erdős y Graham. Se clasifica cada cantidad según su resto al dividirla entre la moneda más grande, aₙ. En cuanto una suma de las monedas más pequeñas alcanza un resto dado, añadir copias de aₙ permite llegar a todas las cantidades mayores con ese mismo resto. La tarea es demostrar que todos los restos se pueden alcanzar a bajo coste.

La herramienta clave es el teorema de Kneser, sobre lo grande que debe ser un conjunto de sumas. Erdős y Graham lo usaron para mostrar que las sumas de unas aₙ/n monedas cubren más de la mitad de los restos, y luego duplicaron para cubrirlos todos. Cada moneda de estas sumas vale como mucho aₙ₋₁, así que duplicar el número de monedas duplica el coste: de ahí el factor 2.

La nueva demostración usa sumas de ⌈aₙ/(n − 1)⌉ monedas. Cuando estas sumas dejan sin cubrir algunos restos, el teorema de Kneser dice que los que faltan no están dispersos al azar: forman familias enteras de restos espaciados a intervalos regulares. Cuantas más familias faltan, más tienen que apiñarse las monedas pequeñas en cada familia alcanzada, de modo que cada una de esas familias contiene algunas monedas pequeñas, y las pocas monedas adicionales necesarias para llegar a las familias que faltan salen baratas. El total nunca supera ⌈aₙ/(n − 1)⌉ × aₙ₋₁.

Ese primer paso da la cota sin su «− 1» final. La última unidad procede de un argumento aparte, basado en un teorema de Scherk y Kemperman sobre las sumas que solo pueden formarse de una única manera: muestra que la cantidad límite aₙ₋₁⌈aₙ/(n − 1)⌉ − aₙ también se puede pagar siempre. Según los agradecimientos, los autores demostraron primero la cota más débil; después, GPT-6 ayudó a encontrar el argumento que la rebaja en una unidad, y colaboró también en la demostración de que la cota no puede rebajarse y en la corrección del inglés. Los autores declaran que asumen la responsabilidad del manuscrito final.

Casos que tocan el límite exactamente

Esta cota no se puede rebajar: para todo n ≥ 3, los autores construyen infinitos conjuntos en los que F coincide exactamente con ella. Se toma cualquier q ≥ 2 y los valores q, 2q, …, (n − 1)q, más (n − 2)q + 1. Todos menos uno son múltiplos de q, así que no pagan nada que q no pueda pagar por sí sola. El conjunto se comporta como dos monedas, q y (n − 2)q + 1, y la fórmula de Sylvester da un F que coincide exactamente con la nueva cota. Con n = 3 y q = 3, esta receta produce precisamente el ejemplo 3, 4, 6 de más arriba.

Menos monedas, un techo más bajo

La cota también puede leerse en términos de densidad. Se aplica a cualquier conjunto reducido formado por los i valores más pequeños más el más grande, siempre que estos sigan sin compartir ningún factor común. Quitar monedas solo puede hacer más difícil pagar, así que un techo demostrado para el conjunto reducido también vale para el completo. Lo que controla el resultado es aproximadamente aᵢ/i, el inverso de la densidad con la que los i primeros valores llenan los números de 1 a aᵢ: gana el grupo más denso. En particular, señalan los autores, la segunda moneda más grande puede dejarse de lado sin más siempre que las monedas restantes sigan sin tener ningún factor común a todas ellas.

El artículo es puramente teórico: no da ninguna cifra de cuánto menor es la nueva cota en conjuntos de monedas típicos, y su optimalidad solo está demostrada para tres valores de moneda o más.