McNuggets

McNuggets de pollo se puede comprar en cantidades de 6, 9 y 20 piezas. Usted puede comprar exactamente 15 piezas mediante la compra de un 6 y un 9, pero no se puede comprar exactamente 10 McNuggets. ¿Cuál es el mayor número de McNuggets que NO se pueden comprar?

¿Quiere una sugerencia? Haga clic aquí.

Haga clic aquí para ver la respuesta completa.

Sugerencia 1

Necesitamos una manera sistemática para determinar qué cantidades se puede comprar, así que vamos a comenzar por escribir los números 1, 2, 3, .... Nos esperan que el número no es muy grande, tal vez no más grande que 50, por lo que escribimos una tabla de números

 1  2  3  4  5  6  7  8  9  10
11 12 13 ...

hasta 50. Luego subrayar cada número que se puede comprar. Puede utilizar este método para no perderse: Primero subrayar 6, 9, y 20, porque usted sabe que estos puede ser comprado. A continuación, proceder en la tabla para cada elemento subrayado (mantenimiento de un dedo en el número por lo que no perderá su lugar), y independientemente añadir 6, 9, y 20 a ese término y subraye la respuesta. Así empezamos por poner el dedo en 6, y entonces subrayando 6 + 6 = 12, 6 + 9 = 15 y 6 + 20 = 26. A continuación, mueva el dedo hacia abajo a la siguiente elemento subrayado (que es 9), y se añadirá 6, 9 y 15. Siga hasta el dedo sale del extremo de la tabla.

Sugerencia 2

La tabla debe parecer como esto:

 1  2  3  4  5  6  7  8  9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50

De análisis de la tabla parece que cualquier número mayor que 43 se puede comprar, pero ¿cómo podemos estar seguros? Por ejemplo, ¿podemos decir de este cuadro que el 51 se puede comprar?

Sugerencia 3

Sí, podemos decir que el 51 se pueden comprar, porque si compramos 6, necesitaríamos unos 45 más, y la tabla nos dice que podemos comprar 45. Utilice el hecho de que disponemos de 6 números en una fila que se puede comprar para demostrar que cualquier cantidad superior a 43 se pueden comprar.

El Resto de la Respuesta

Para comprar un número más grande, empezar con la compra de paquetes de 6 hasta que el número necesario se convierte en 50 o menos. Dado que sólo estamos reduciendo el número necesario en un 6 cada vez que, en este punto necesitamos un número en el rango 45-50, y ya sabemos que cualquiera de estos números se pueden comprar.

Máximo Común Divisor de Varios Números

Cuando empezamos a trabajar sobre este problema, no era obvio que exista el número más grande que no podía ser comprado. Supusimos que realmente tal número exista, y de hecho que sería menor que 50.

¿Qué hubiera pasado si los tamaños de las cajas habían sido 6, 9 y 21? Esto se parece mucho a el problema original, pero en este caso no existe el número más grande que no se pueden comprar. ¿Por qué? Porque cada uno de los tamaños es un múltiplo de 3, y por lo que cualquier cantidad que se compra debe ser un múltiplo de 3.

Usted probablemente está familiarizado con la idea del máximo común divisor de dos números. De hecho cualquiera tres números enteros positivos tienen un MCD también, al igual que cualquiera de los cuatro, y así sucesivamente. El MCD de varios números se define del mismo modo que para dos números: es el número más grande que divide exactamente todos los números. En el problema de McNuggets sabemos que si el MCD de los tamaños de caja no es 1, entonces no hay un cantidad más grande que no se puede comprar (cualquier combinación de cajas suma a una cantidad que es divisible por el MCD).

¿Qué pasa si el MCD es 1? En el problema original tenían tamaños de 6, 9, y 20, y el MCD de ellos es 1 (a pesar de que 3 divide tanto a los 6 y 9, no divide a los tres números, por lo que el MCD no es 3). De hecho, si el MCD es 1, entonces siempre hay una cantidad que no se puede comprar. Así, por otro ejemplo, si las cajas tenían tamaños de 15, 21 y 35, el MCD de los tres es 1 (a pesar de que cualquiera de los dos tienen un GCD que es mayor que 1), y hay una mayor cantidad que no puede ser comprado (es 139).

Para ver que siempre hay uno más grande en el caso GCD = 1, tenemos el hecho de que si el MCD de varios números es 1, entonces una combinación lineal entera de ellos es 1. Por ejemplo,

Esta combinación no se puede ser comprado, ya que tendría que comprar un número negativo de cajas de 20 piezas, pero va a corregir esto en un minuto. También recordamos que en este caso es suficiente para encontrar 6 cantidades adquiribles consecutivos, y luego todo mayor de que se podrán comprar. Por lo tanto, aún ignorando el hecho de que hay algunas cantidades negativas, simplemente podemos multiplicar esta ecuación para obtener

Ahora vamos a corregir las cantidades negativas. Todas ellas proceden de las cajas de 20 piezas, y si sólo tenemos que añadir 6 de estas cajas a cada uno de ecuaciones que se hacen:

Así que sabemos de esta lógica que cualquier cantidad de 120 o más pueden ser comprado, por lo que la mayor cantidad no adquirible es de 119 o menos (de hecho, descubrió que era 43).

El mismo razonamiento es válido para cualquier tamaño de las cajas, cuando el MCD = 1. Recibimos una combinación lineal de los tamaños de cajas para cada número de 1 a través del menor tamaño de caja, y luego ajustar las combinaciones para hacer todas las cantidades positivas.

Referencias

• El problema general pide la cantidad más grande de dinero que no se puede dar como combinación de monedas de valores fijos; esto se llama Problema de Frobenius o Problema de la Moneda. Aquí es una traducción de un artículo en Wikipedia sobre el Problema de la Moneda.
• (en inglés) Haz clic aquí para leer la pregunta original de Frances.