El problema de los McNuggets de pollo

Un conocido problema de Teoría de Números que aparece en muchos libros es el Problema de los nuggets de pollo.

El problema dice lo siguiente:

en los restaurantes McDonald’s los nuggets de pollo vienen en cajas de 6, 9 y 20 unidades (estos son los tamaños originales, antes de que se incluyeran las cajas de 4 en los Happy Meal). Por lo tanto, podemos obtener exactamente 15 nuggets si compramos una caja de 6 y otra de 9, pero no es posible conseguir la cantidad exacta de 14 nuggets. Comprando diferentes cantidades de estos tres tipos de cajas, ¿cuál es la cantidad más grande de nuggets de pollo que no se pueden conseguir de forma exacta?

De hecho, podríamos plantearnos si existirán infinitas cantidades que no se pueden conseguir, o si será un número finito de cantidades. Por lo tanto, en el primer caso la solución del problema será que no hay una cantidad determinada más grande que las demás, es decir, hay cantidades de nuggets tan grandes como queramos que no se pueden conseguir, “infinitas”, mientras que en el segundo caso, sí podemos buscar cuál es esa cantidad mayor que las demás.

Este problema fue introducido por el matemático Henri Picciotto, quien lo incluiría en su libro de texto de álgebra, escrito con Anita Wah, Algebra: Themes, Tools, Concepts (1994).

Caja de 20 McNuggets de pollo de McDonald’s

Veamos qué cantidades sí se pueden obtener como combinación lineal de los números 6, 9 y 20, es decir, como $6 x + 9 y + 20 z$ , para $x, y, z$ números enteros no negativos. Esta expresión representa la cantidad de nuggets contenidos en $x$ cajas de 6, $y$ cajas de 9 y $z$ cajas de 20.

6, 9, 12 = 2 x 6; 15 = 6 + 9; 18 = 2 x 9; 20, 21 = 2 x 6 + 9; 24 = 6 x 4; 26 = 6 + 20; 27 = 3 x 9; 29 = 9 + 20; 30 = 6 x 5; 32 = 2 x 6 + 20; 33 = 3 x 9 + 6; 35 = 6 + 9 + 20; 36 = 6 x 6; 38 = 2 x 9 + 20; 39 = 6 x 5 + 9; 40 = 2 x 20; 41 = 2 x 6 + 9 + 20; 42 = 6 + 4 x 9

Como podemos observar, hay cantidades de nuggets que pueden obtenerse con diferentes combinaciones de cajas, por ejemplo, 18 = 2 x 9 = 3 x 6, dos cajas de 9 nuggets o 3 cajas de 6.

Por el contrario, los números que no se pueden obtener como combinación lineal de 6, 9 y 20, hasta el número 43, son veintidós:

1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16,

17, 19, 22, 23, 25, 28, 31, 34, 37 y 43.

¿Y qué pasa a partir del número 43? Observemos que

44 = 6 x 4 + 20, 45 = 3 x 9 + 3 x 6, 46 = 6 + 2 x 20,

47 = 3 x 9 + 20, 48 = 8 x 6, 49 = 9 + 2 x 20,

y todos los demás números más grandes que estos se pueden expresar como múltiplos de 6 sumandos a alguno de estos seis números, luego son combinaciones lineales de 6, 9 y 20.

En consecuencia, la cantidad más grande de nuggets de pollo que no pueden obtenerse a partir de las cajas de 6, 9 y 20 unidades es 43.

Logotipo del Licor 43, cuyo nombre se deriva de los 43 ingredientes básicos que se utilizaron en la receta original de este licor, principalmente hierbas, y frutas cítricas, también otras frutas, de la cuenca del mediterráneo — Logotipo del Licor 43, cuyo nombre se deriva de los 43 ingredientes básicos que se utilizaron en la receta original de este licor, principalmente hierbas y frutas cítricas, también otras frutas, de la cuenca del Mediterráneo

En la actualidad también hay cajas de 4 nuggets, que fueron introducidas con los Happy Meal, por lo que ahora sí se pueden obtener más cantidades que antes. Por ejemplo, 43 = 4 + 2 x 6 + 3 x 9. De hecho, si contamos con estos cuatro tipos de cajas de nuggets de pollo, con 4, 6, 9 y 20 unidades, solamente no se pueden obtener las cantidades

1, 2, 3, 5, 7, 11.

Y la cantidad más grande de nuggets de pollo que no pueden obtenerse a partir de las cajas de 4, 6, 9 y 20 unidades es 11.

Contenido del menú infantil de los restaurantes McDonald’s, conocido como Happy Meal, que incluye cajas de 4 nuggets de pollo

El problema de los nuggets de pollo no es más que un caso particular del Problema del cambio de moneda (de Frobenius), del que hablamos en mi anterior entrada del Cuaderno de Cultura Científica. Recordémoslo:

Sea $A = \{a_1, a_2,\ldots , a_n\}$ un conjunto de números enteros positivos, relativamente primos (es decir, sin divisores comunes), ¿cuál es el entero positivo N más grande que no puede ser representado como combinación lineal de ellos, es decir, $N = m_1 a_1 +m_2 a_2 +\cdots + m_n a_n$ , para $m_1, m_2,\ldots , m_n$ enteros positivos?

A este número se le suele denotar por $g(a_1, a_2,\ldots, a_n)$ y se le llama número de Frobenius.

También en mi anterior entrada de la sección Matemoción vimos que el problema del cambio de moneda para dos monedas, $n = 2$ , conocido como problema de los sellos de Sylvester, había sido completamente resuelto por el matemático inglés James J. Sylvester (1814-1897) en 1884. Además, se había obtenido una fórmula explícita para calcular el valor del número de Frobenius.

De hecho, la cantidad más grande que no puede ser expresada como combinación lineal de dos números a y b, sin divisores comunes, está dada por la siguiente fórmula: $g(a, b) = ab- a- b.$ Es decir, en el contexto del problema de los nuggets de pollo, si existieran solo dos tipos de cajas con las cantidades a y b, entonces la cantidad más grande que no podría ser obtenida exactamente sería la dada por la anterior fórmula.

Por desgracia, no existe una fórmula similar a la anterior para calcular los números de Frobenius $g(a_1, a_2,\ldots, a_n)$ para el caso de tres, o más, tipos de monedas, $n\geq 3$ .

Para el caso $n = 3$ , que es el directamente relacionado con el problema de los nuggets de pollo, no existe una fórmula explícita para calcular $g(a_1, a_2, a_3)$ . Es cierto que para cantidades concretas no muy grandes, como el caso de los nuggets de pollo o uno tan sencillo como el de las puntuaciones de rugby (existen tres posibles puntuaciones en este deporte, 5 puntos por un ensayo, 3 puntos por un puntapié de botepronto y 2 puntos por una trasformación tras un ensayo, luego existen solamente tres cantidades de puntos que no se pueden obtener en el rugby, 1, 2 y 4, es decir, $g(2,3,5)=4$ ), se pueden calcular a mano, sin embargo, no existe una fórmula similar a la de Sylvester.

Ensayo de Irlanda, contra Italia, en el Torneo de las 6 naciones de 2015

Por otra parte, sí existen varias fórmulas para obtener cotas inferiores y superiores del número de Frobenius, como por ejemplo la cota inferior obtenida por J. L. Davidson,

$g(a_1, a_2, a_3)\geq \sqrt{3\cdot a_1\cdot a_2 \cdot a_3} -a_1- a_2- a_3$ .

Aunque en el caso de los nuggets de pollo esta no es una buena cota, ya que está bastante alejada del valor de $g(6, 9, 20) = 43$ ,

$g(6, 9, 20)\geq \sqrt{3\cdot 6\cdot 9 \cdot 20} -6-9-20 = 21,9$ ,

en general, esta es una cota muy fina, que se acerca mucho al valor real del número de Frobenius.

Una fórmula del mismo estilo, sencilla y clara, para obtener una cota superior fue obtenida por Becks y Zacks,

$g(a_1, a_2, a_3)\leq \displaystyle{1\over 2} \left[\sqrt{ a_1\cdot a_2 \cdot a_3 \cdot (a_1+ a_2 + a_3)}- a_1- a_2 -a_3\right]$ ,

aunque de nuevo para el caso particular de los nuggets de pollo está alejada del valor buscado, puesto que queda $g(6, 9, 20)\leq 79,7$ .

En relación al cálculo exacto del valor de $g(a_1, a_2, a_3)$ , este problema ha sido resuelto de forma computacional mediante el uso de diferentes algoritmos, que pueden verse en la literatura matemática del problema.

Sin embargo, para $n\geq 4$ , el problema es mucho más complejo y aún es un problema abierto.

Como otros tópicos matemáticos, el número de Frobenius tiene multitud de aplicaciones en muy diversas áreas de la Ciencia, como la Teoría de Números, las Ciencias de la Computación, la Teoría de Códigos, las Teselaciones, la Teoría de Grafos o el Álgebra lineal, por citar algunas.

Para terminar… un pequeño problema para quien quiera entretenerse. Imaginemos que somos pasteleros y que uno de los postres principales de nuestra pastelería son los brownies. Vendemos estos deliciosos pasteles de chocolate en cajas de 6, 10 y 15 brownies, entonces ¿qué cantidades exactas de brownies no se pueden guardar utilizando ese tipo de cajas? (11 no se pueden guardar, pero 21 sí) ¿cuál es la cantidad más grande que no se puede almacenar exactamente?

Bibliografía

1.- Henri Picciotto, Anita Wah, Algebra: Themes, Tools, Concepts, Creative Publications, 1994. Versión libre on-line

2.- Matthias Beck, How to change coins, M&M’s, or chicken nuggets: the linear diphantine problem of Frobenius, Resources for teaching Discrete Mathematics (editor Brian Hopkins), MAA, 2009.

3.- Coin problem, WolframMathWorld

4.- Miodrag S. Petkovic, Famous Puzzles of Great Mathematicians, AMS, 2009.

5.- Mathias Beck, Shelemyahu Zacks, Refined upper bounds for the linear Diophantine problem of Frobenius, Advances in Applied Mathematics, 32, 2004, 454-467.

Sobre el autor: Raúl Ibáñez es profesor del Departamento de Matemáticas de la UPV/EHU y colaborador de la Cátedra de Cultura Científica

Próximos eventos

La evolución humana, desde la neurociencia, será el asunto a analizar en la VI Jornada sobre Evolución y Neurociencias

Los cambios del cerebro durante el embarazo y la maternidad, cómo el estrés ha pasado de ser un mecanismo de supervivencia a un eventual elemento de riesgo para nuestra salud o cuál ha sido el papel que ha jugado el suicidio en la evolución del ser humano serán algunos de…

25–26 de abril, 2024

Bizkaia Aretoa UPV/EHU

Avenida Abandoibarra, 3, Bilbao

1 comentario

Hitos en la red #77 – Naukas 19 de julio, 2015

[…] En estos días de verano en el hemisferio norte, con los niños de vacaciones, aumentan las comidas en los restaurantes de comida rápida. Raúl Ibáñez aporta fundamento matemático para organizar las compras de grupos numerosos en El problema de los McNuggets de pollo. […]