McNuggets y Frobenius

Henri Picciotto cenaba en McDonalds con su hijo cuando se le ocurrio un problema. ¿Que cantidades de McNuggets podemos comprar con cajas de 6, 9 y 20 McNuggets? Estas cantidades que si que podemos comprar se llaman números MnNuggets. Es fácil comprobar si un número pequeño es o no un número McNuggets. Por ejemplo, 4 y 7 no lo son, pues no los podemos escribir como combinación de cajas de 6, 9 y 20. En cambio, 15 si que lo es, puesto que podemos comprar 15 McNuggets comprando una caja de 6 y una de 9. Como  mcd(6,9,20)=1, habrá un número a partir del cual cualquier número será un número de McNuggets*. Esto nos plantea otra pregunta, ¿Cual es el número màs grande que no es número de McNuggets?
Si tenemos un número un poco grande, por ejemplo 37, podemos seguir unos pasos para comprobar si es o no de McNuggets. Supongamos que lo fuera, entonces si le restamos 6, 9 o 20 seguirá siendolo. Lo que hacemos restando es quitar una de las cajas que en principio nos permitian comprar esa cantidad. Vamos a hacer esto hasta encontrar un número que ya sepamos que es de McNuggets o que no lo es. Si llegamos a uno que lo es, esto nos dirá que el número del que hemos partido tambien lo es. En cambio, si llegamos a un número que no lo es, el primer número tampoc és McNuggets. Veamoslo con el 37. Si restamos 6, 9 y 20 obtenemos: \{31, 28, 17\}. Estos números aún son demasiado grandes para saber si són McNuggets, así que volvemos a restar 6, 9 y 20. Obtenemos \{25, 22, 11, 22, 19, 8, 11, 8 \}=\{25, 22, 19, 11, 8\}. Ninguno de estos números se puede obtener comprando cajas de McNuggets así que 37 tampoco.

Puedes seguir haciendo esto y veras que 43 no es un número de McNuggets pero que 44=20+6×4, 45=9×5, 46=2×20+6, 47=20+3×9, 48=8×6 y 49=2×20+9. Tenemos 6 números seguidos que són números de McNuggets. Si le sumamos una caja de 6 a cada uno de estos números obtenemos 50, 51, 52, 53, 54 y 55, que son los 6 siguientes. Volviendo a  adjuntar una caja de 6, obtenemos los siguientes 6. Esto nos dice que todos los números siguientes seran de McNuggets. Por lo tanto, 43 es el número más grande que no es McNuggets.

 Este problema es un caso particular del problema de las monedas o el problema de Frobenius (por el matemático Ferdinand Georg Frobenius). El problema de Frobenius consiste en encontrar el número más grande que se puede escribir como combinacion lineal de coeficientes positivos (es decir, sumandolos un número cualquiera de veces) de unos números dados a_1, a_2, dots, a_n que cumplen mcd(a_1, a_2, dots, a_n)=1. Este número se llama número de Frobenius y se escribe g(a_1, a_2, dots, a_n). En el caso de los McNuggets, tenemos a_1 = 6, a_2=9 i a_3=20 y hemos calculado que el número de Frobenius es 43.

Cuando tenemos dos números, el númer de Frobenius se puede encontrar con una fórmula. Tenemos g(a_1, a_2)=a_1a_2-a_1-a_2. Imaginate que tienes sellos de 7 y 15 céntimos, ¿Cual es la cantidad más grande que no se puede formar con estos sellos? Puedes calcularlo con la fórmula y comprobarlo despues manualmente como hemos hecho con  los McNuggets!

En cambio, si tenemos más de dos números (es decir, n>2, com en el caso de los McNuggets que teniamos n=3) no existe ningua fórmula explícita. Lo que si que hay son algoritmos (unos pasos a seguir) que nos permiten encontrar el número de Frobenius para el problema concreto.

Aquí tienes más problemas y aquí más información sobre el Problema de Frobenius.

*Esto es una consecuéncia del Teorema de Schur, si te interesa puedes buscarlo o pedir que te lo explique.

Anuncios

Una respuesta a “McNuggets y Frobenius

  1. Pingback: McDonald’s Vintage Packaging « Ventanas que me invento·

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s