Boletín del IMI
Nº 35 (3 de febrero de 2022)

En esta sección se publican artículos cortos de divulgación, con una imagen y un máximo de 400 palabras (sin tener en cuenta en estas restricciones los datos de los autores). Las personas que quieran publicar un artículo pueden enviarlo a secreadm.imi@mat.ucm.es

Buscando problemas en McDonald's

Twitter: @patricioalmirn

Acorde a la página web de McDonald’s España, tenemos las opciones de pedir McNuggets en cajas de 4, 6, 9 y 25 piezas. ¿Qué sucede entonces si yo quiero exactamente 11 McNuggets? En un rápido cálculo los lectores seguro que ya saben que es imposible pedir exactamente 11 piezas de McNuggets sin embargo, podemos analizar este problema con un poco más de precisión.

 

En primer lugar, cualquier cantidad que queramos pedir tiene que poder expresarse como combinación natural de 4, 6, 9 y 25. Una observación rápida es que 25=4+6x2+9, por lo tanto nos basta con mirar las combinaciones de 4, 6 y 9. La segunda observación y más importante es que estos tres números son primos entre sí. ¿Cuál es la consecuencia de esta propiedad? 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.

El conjunto de 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. Un semigrupo numérico es, por definición, un submonoide aditivo de los números naturales con complemento finito. La propiedad de complemento finito sobre los naturales inmediatamente implica: 1) que está finitamente generado y 2) que debe existir un número mínimo a partir del cual todos los números naturales mayores que él son expresables como combinación de nuestros generadores; a este número lo denominamos conductor. ¿Cómo podemos calcular el conductor de un semigrupo? Este es el denominado problema de Frobenius. En general, solamente existen fórmulas cerradas para semigrupos con 2 o 3 generadores minimales, en nuestro caso el conductor es 12=(6x4)/2-6-4+(2-1)*9+1. Para un semigrupo numérico con más de tres generadores minimales, no existen fórmulas cerradas, pero sí numerosos algoritmos, y de hecho el problema de Frobenius es un problema NP-hard. Por suerte tenemos ordenadores y programas que nos permiten calcular el conductor de infinidad de semigrupos en un tiempo razonable.

Para finalizar, los españoles tenemos una gran ventaja frente a los americanos y es que, salvo 1,2,3,5,7 y 11, podemos pedir la cantidad exacta de McNuggets que queramos. En la web de McDonald’s USA se puede ver que las posibles cajas allí son de 4,6, 10, 20 y 40, ya imagináis lo que eso implica si uno es un poco caprichoso….