¿Hay alguna posibilidad de pedir 11 nuggets de pollo a pesar de que las cajas son de 4, 6 y 9?

En primer lugar, cualquier cantidad que queramos pedir tiene que poder expresarse como combinación natural de 4, 6, 9 y 25, es decir de la forma: 4a + 6b + 9c + 25d con a, b, c y d números enteros positivos. Una observación rápida es que 25 = 4 + 6 · 2 + 9.por lo tanto nos bastará con mirar las combinaciones de 4, 6 y 9. La segunda observación, y de hecho la más importante para el problema que nos ocupa, es que estos tres números son primos entre sí, es decir, como nos enseñaron a todos en la escuela son tres números cuyo único divisor común es el número 1.

¡Ojo! Divisor común para todos ellos pues como se puede comprobar 2 divide a 4 y a 6, y 3 divide a 6 y a 9 pero sin embargo 2 no divide a 9 y 3 no divide a 2. Y dirán ustedes ¿tan importante es la propiedad de que el número 1 sea su único divisor común? Pues resulta que el hecho de que su máximo común divisor sea 1 es equivalente a que el número de números naturales que no se pueden expresar como combinación natural de 4, 6 y 9 sea ¡un número finito! Traducido a nuestro problema, que es pedir nuggets, esto quiere decir que hay un número infinito, sin repetición, de posibilidades para nuestras posibles peticiones.

El conjunto de estas posibles combinaciones naturales de 4, 6 y 9 es lo que en matemáticas se denomina un semigrupo numérico generado por 4, 6 y 9. Hablando de manera formal, un semigrupo numérico, S, es, por definición, un subconjunto de los números naturales que satisface las siguientes propiedades:

1) si a y b son elementos de S entonces a+b es un elemento de S

2) el número de números naturales que no pertenecen a S es un número finito, lo que en matemáticas se denomina que el complemento de S sobre los números naturales es finito.

La propiedad de complemento finito sobre los naturales implica de manera inmediata que debe existir un número mínimo a partir del cual todos los números naturales mayores que él pertenecen a nuestro conjunto S; a este número lo denominamos conductor. ¿Podemos dar una fórmula general para el conductor de un semigrupo numérico? Este es el denominado problema de Frobenius para semigrupos numéricos o también conocido como problema del cambio de moneda. Este problema, aunque se puede decir que fue propuesto como tal a mediados del siglo XIX, en realidad es un problema que acompaña a la humanidad desde la creación de la primera moneda. Imagine el lector aquellos primeros gobernantes creadores de la moneda allá por el siglo VII a.C., teniendo que lidiar con el problema de los posibles precios que se pueden dar en función de los valores de las monedas que se crearían. Sin duda un problema de alta dificultad dada la notación numérica de aquellos tiempos.

Volviendo a nuestro problema en cuestión, y sabiendo ya que tenemos infinitas posibilidades de peticiones para nuestros nuggets, la pregunta ahora es ¿cuál es la mayor cantidad de nuggets que no podemos pedir en el mostrador? Traducido a lenguaje matemático significa calcular el conductor del semigrupo generado por 4, 6 y 9. Para ello nos hace falta introducir el concepto de generadores minimales. Decimos que

son generadores minimales de un semigrupo numérico S si son el menor conjunto de números naturales con los cuales cualquier elemento s de S se escribe como:

En el caso de que el número de generadores minimales de S sea 2, digamos entonces el conductor se escribe de la forma

Sorprendentemente, las fórmulas para el caso de 3 generadores son bastante más complicadas en general y para el caso de más de 3 generadores se demostró que no existen fórmulas polinomiales en función de los generadores minimales, lo cual convierte el problema de Frobenius en un problema NP; lo que viene a ser un problema de difícil resolución computacional.

Relacionado con el problema de Frobenius, existe una conjetura que lleva sin resolverse más de 50 años. En 1978, Herbert Wilf propuso un peculiar algoritmo con el cual calcular el conductor de un semigrupo numérico S generado minimalmente por

De este modo, Wilf observó que si sumamos 1 a la mayor numeración de las bombillas apagadas en esta última ronda entonces obtenemos el conductor del semigrupo. Para el semigrupo de nuggets 4, 6 y 9 podemos calcular que el conductor del semigrupo es 12 y que las únicas cantidades que no podemos pedir los españoles son 1, 2, 3, 5, 7 y 11 mediante la representación propuesta por Wilf:

A raíz del algoritmo propuesto por Wilf se puede observar que cuanto más grande es el conductor, mayor debe ser la cantidad de elementos que no pertenecen al semigrupo; por otro lado, cuantas más generadores minimales tengamos, menor debería ser, a priori, la cantidad de elementos que no pertenecen al semigrupo en comparación con el conductor. Con todo esto, si llamamos c al conductor del semigrupo, llamamos n al número de generadores minimales y llamamos g al número de elementos que no pertenecen al semigrupo entonces Wilf planteó la siguiente pregunta:

Hoy en día esta pregunta se conoce como conjetura de Wilf sobre semigrupos numéricos y constituye uno de los problemas abiertos más fascinantes en teoría de semigrupos numéricos. Es más, a pesar de estar demostrada en gran cantidad de casos, parece que a día de hoy aún estamos lejos de su resolución.

Para finalizar, y volviendo a nuestro problema de pedir nuggets, un dato curioso es la diferencia entre las cantidades posibles en España y en Estados Unidos. Según la web de esta conocida marca de comida rápida, pero esta vez en EE.UU. se puede ver que las posibles cajas allí son de 4, 6, 10, 20 y 40. Es fácil comprobar que 2 divide a todos ellos y que por tanto su máximo común divisor es distinto de 1. Como hemos dicho anteriormente, esto implica que en Estados Unidos ¡existen infinitas cantidades que no podemos pedir de manera exacta! Sin duda es sorprendente pues originalmente los nuggets comenzaron a comercializarse en cajas de 6, 9 y 20 cuyo semigrupo tiene conductor 44 (como puede comprobar el lector mediante el algoritmo de Wilf). Sin duda, en España parece que tenemos ventaja en este aspecto y que por el contrario en Estados Unidos han perdido la ventaja de poder elegir casi cualquier cantidad.

* El ABCdario de las Matemáticas es una sección que surge de la colaboración con la Comisión de Divulgación de laReal Sociedad Matemática Española (RSME).

SOBRE EL AUTOR

Patricio Almirón Cuadros

es investigador postdoctoral en el Instituto de Matemáticas de la Universidad de Granada