Le podemos vender 44, pero no 43

Les recomiendo mucho el video de Numberphile, del mes pasado, titulado Cómo ordenar 43 McNuggets, sobre los números de Frobenius (también en Wikipedia).

Dada una lista l =\{a_1, a_2, \ldots, a_k\} de enteros positivos primos relativos, el número de Frobenius de l es el mayor entero positivo que no puede escribirse como una suma

a_1 x_1 + a_2 x_2 + \ldots + a_k x_k                                            (*)

con x_1, x_2, \ldots, x_k \in \mathbb N. Por ejemplo, el número de Frobenius de \{4,5\} es 11, ya que

12 = 4\times 3 + 5\times 0

13 = 4\times 2 + 5\times 1

14 = 4\times 1 + 5\times 2

15 = 4 \times 0 + 5\times 3,

y por lo tanto cualquier otro número mayor que 15 puede obtenerse sumando múltiplos de 4 a las expresiones anteriores.

De hecho, no es muy difícil demostrar que el número de Frobenius de \{a,b\} es (a-1)(b-1)-1, y que el número de enteros positivos que no se pueden escribir de la forma (*) es igual a \dfrac{1}{2}(a-1)(b-1) (Sylvester, 1884). Por ejemplo, con 4 y 5, tenemos

(4-1)(5-1)-1=11            y             \dfrac{1}{2}(4-1)(5-1) = 6.

Los números que no se pueden expresar con 4 y 5 son 1, 2, 3, 6, 7 y 11.

El problema de los McNuggets se refiere a expresiones de enteros con la lista \{6, 9, 20\}, el número de nuggets individuales en cada caja en venta. El número de Frobenius de dicha lista es, precisamente 43. No existe una fórmula que calcule el número de Frobenius de \{a,b,c\}, como en el caso de dos números. Más aún, el problema de calcular el número de Frobenius, llamado el problema de las monedas, de una lista con k enteros, es del tipo NP.

Curiosamente, en el video, la cajera de McDonalds le dice que no puede venderle 43 nuggets, y le ofrece 44 con dos cajas de 20 y una de 4. El que haya cajas con 4 nuggets cambia las cosas: resulta que 43 sí se puede expresar con 4, 6, 9, y 20 de la forma

43 = 4\times 1 + 6\times 2 + 9\times 3,

lo que muestra la necesidad de que McDonalds tenga un matemático a la mano para poder vender las órdenes de clientes exigentes.

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