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).
Veamos qué cantidades sí se pueden obtener como combinación lineal de los números 6, 9 y 20, es decir, como 
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.
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.
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
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,
, para
enteros positivos?
A este número se le suele denotar por 
También en mi anterior entrada de la sección Matemoción vimos que el problema del cambio de moneda para dos monedas, 
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: 
Por desgracia, no existe una fórmula similar a la anterior para calcular los números de Frobenius 
Para el caso 
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,
Aunque en el caso de los nuggets de pollo esta no es una buena cota, ya que está bastante alejada del valor de 
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]](https://s0.wp.com/latex.php?latex=g%28a_1%2C+a_2%2C+a_3%29%5Cleq+%5Cdisplaystyle%7B1%5Cover+2%7D+%5Cleft%5B%5Csqrt%7B+a_1%5Ccdot+a_2+%5Ccdot+a_3+%5Ccdot+%28a_1%2B+a_2+%2B+a_3%29%7D-+a_1-+a_2+-a_3%5Cright%5D+&bg=T&fg=000000&s=0 "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 
En relación al cálculo exacto del valor de
Sin embargo, para 
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
Hitos en la red #77 – Naukas
[…] 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. […]