Frobenius y los Mcnuggets

(Con esta entrada participamos en el Primer Carnaval de Matemáticas)

Un número entero positivo “McNugget”, es aquel que es expresable como combinación lineal, con coeficientes enteros no negativos, de los números 6, 9 y 20. Se llama así porque 6, 9 y 20 eran los contenidos de las cajas de McDonald's® Chicken McNuggetsTM.

Hay números que son “McNugget”, como el 30 = 2*9+2*6, que abarcan un número entero de cajas (un pedido normal), y otros que no pueden serlo, como el 11, que no se puede descomponer en sumandos 6, 9 y 20.

Este es un simpático ejemplo de descomposición de un entero N en sumandos extraídos de un conjunto (lista) L. Por ejemplo, el número 10, según la lista (5,3,1) se puede descomponer en 10= 5+5 = 5+3+1+1 = 5+1+1+1+1+1 = 3+3+3+1 = 3+3+1+1+1+1 = 3+1+1+1+1+1+1+1 = 1+1+1…

Las sumas las podemos expresar como combinaciones lineales:

10 = 2*5+0*3+0*1 = 1*5+1*3+2*1 = 1*5+5*1 = …

En el caso de los “McNugget”, los coeficientes serían, evidentemente, el número de cajas que deberíamos pedir.

Generalizando, dado un conjunto de números enteros positivos a₁, a₂, a₃,…a_n, diremos que otro entero positivo N es representable según ese conjunto si existen coeficientes enteros no negativos x₁, x₂, x₃,…x_n tales que N= a₁*x₁+a₂*x₂+…a_n*x_n

Según sea el conjunto a₁, a₂, a₃,…a_n será distinta la discusión de si todos los enteros positivos N son representables en ese conjunto. Nos referiremos a partir de ahora a aquellos en los que que MCD(a₁, a₂, a₃,…a_n)=1, es decir, que sean coprimos, aunque no necesariamente dos a dos.

Este problema es llamado también de las monedas, porque equivale a discutir si una cantidad de dinero se puede expresar sólo con dos o tres tipos de monedas (o de billetes, o de sellos).

Se puede demostrar que para números N grandes es posible siempre esta expresión de un número como combinación lineal de este tipo (uno de los teoremas de Schur). Existirá, por tanto, un número que sea el mayor para el que no se cumpla, que no sea representable en ese conjunto. Este es el llamado número de Frobenius. Por ejemplo, en los McNugget, el número de Frobenius es 43, porque es el mayor de los números no representables con 6, 9 y 20. Todos los mayores que él lo son.

Encontrar el número de Frobenius para un conjunto de varios números primos entre sí es un problema muy complejo (tipo NP-hard) que sobrepasa los objetivos de este blog, dedicado a las cuestiones de nivel medio.

No obstante, podemos hacer alguna propuesta sobre él.

(a) El que un número N suficientemente grande sea representable siempre lo podemos razonar para el caso de dos coeficientes. Sean A y B enteros positivos primos entre sí. Sabemos que entonces la ecuación Ax+By=N siempre tiene solución: X₀=pN-Bt Y₀=qN+At, siendo p y q una solución de Ax+By = 1 y t un parámetro. Lo que tienes que investigar es si para N suficientemente grande, X₀ e Y₀ pueden ser ambos no negativos. Pues a por ello.

Con la ayuda de la hoja de cálculo también se puede investigar algún aspecto de este problema:

(b) Nuestro Buscador de Números Naturales permite encontrar aquellos que sean suma de múltiplos de otros. Así, los números McNugett serán suma de múltiplos de 6, 9 y 20. De esta forma puedes comprobar que el número de Frobenius para ellos es 43.

Sigue estos pasos:

Abre el Buscador de Naturales para Calc en

http://www.hojamat.es/sindecimales/divisibilidad/herramientas/hojas/buscador.ods

o para Excel en

http://www.hojamat.es/sindecimales/divisibilidad/herramientas/hojas/buscador.xls

Borra las condiciones con el botón correspondiente y diseña una búsqueda como suma de múltiplos en “Suma Especial” guiándote por la siguiente imagen (escribe SI, M6, M9…)



Concreta en la parte superior que buscaremos desde 1 hasta 200. Pulsa sobre el botón “Buscar números” y obtendrás una lista en la que a partir del número 44 todos aparecen consecutivos, por lo que se comprueba que 43 es el máximo que no es representable.



Silvester demostró que para dos números a y b coprimos, su número de Frobenius equivale a
g(a,b)=ab-a-b.

Puedes comprobarlo con el Buscador de Naturales. Borra condiciones y diseña una búsqueda sólo con dos múltiplos, y podrás observar que su número de Frobenius cumple la fórmula de Silvester. En la imagen puedes ver el caso de que a=11 y b=8, con lo que g(11,8)=11*8-11-8=69, y a partir del 70 todos son consecutivos.



(c) Hemos preparado un modelo de hoja de cálculo que encuentra todas las posibilidades de representación de un número respecto a otros varios. Por tratarse de un algoritmo voraz, puede tener algún fallo, pero parece funcionar bien.


Puedes descargártelo (dos versiones: Excel y Calc) desde

http://www.hojamat.es/blog/mcnugget.zip

En la segunda hoja dispones de unas breves instrucciones