General McNugget problema

Question

El clásico McNugget problema de los estados:

McNuggets de pollo se puede comprar en cantidades de 6, 9 y 20 piezas. Usted puede comprar exactamente 15 piezas por 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?

El problema puede ser generalizado a uno de los siguientes:

Si usted tiene un artículo que se puede comprar en cantidades de $a$, $b$, y $c$ ($a < b < c$, $gcd(a,b,c) = 1$), ¿cuál es el entero más grande $N$ de los elemento que no puede ser comprado? (que se encuentra enteros $x$, $y$, $z$ que satisfacer $xa + yb + zc = N$)

En la clase de informática hoy en día, estábamos discutiendo maneras de resolver este problema y es una manera de encontrar la secuencia más pequeña de $a$ números consecutivos que todo podría estar formado por $xa + yb + zc$. A continuación, el número más grande que no se puede comprar, es uno menos que la primera de las $a$ números consecutivos.

Nuestra pregunta era: ¿cómo determinar el punto de partida para tratar de secuencias de $a$ números consecutivos? Usted no desea que se inicie demasiado bajo, o usted va a tomar mucho tiempo para encontrar la solución, y usted no desea que se inicie demasiado alto, o puede que se pierda la solución.

Answer 1

Deje $a_1,\ldots,a_k$ ser enteros positivos con $\operatorname{gcd}(a_1,\ldots,a_k)=1$. A continuación, para todos lo suficientemente grande $N$, existen enteros no negativos $x_1,\ldots,x_k$ tal que

$a_1 x_1 + \ldots + a_k x_k = N$.

De hecho, este papel le da un elemental discreta de la geometría de la prueba de que el número de $r(N)$ de este tipo de soluciones es asintótica a $\frac{N^{k-1}}{(k-1)! a_1 \cdots a_k}$. Por lo tanto no es un bien definido conductor de $\mathfrak{c}(a_1,\ldots,a_k)$, el menor entero positivo $c$ tal que $r(N) \geq 1$ todos los $N \geq c$.

Informática el director de orquesta $c$ se denominan los Diophantine Problema de Frobenius. Cientos de artículos han tratado. Es sabido que cada uno de ellos fijo $k$ no es un polinomio de tiempo de algoritmo para el cálculo de $\mathfrak{c}$. Creo que esta fue la primera establecida en

R. Kannan, Celosía se traduce de un polytope y el Frobenius problema, Combinatorica 12 (1992), 161-177.

En el $k = 3$ caso de que usted está preguntando acerca de, un estudio anterior de Harold Greenberg da un algoritmo que es más sencillo, y (si no me equivoco) más rápido que la del caso general.

Por último, más recientemente Ramírez-Alfonsín escribió todo un libro sobre el problema de Frobenius. La información contenida puede ser más integral y/o hasta la fecha que la mía.

Answer 2

Si usted está buscando un número de $n$ comenzar a determinar el número de representaciones de $n$,$n+1$,$n+2$,$\ldots$ hasta que usted consigue una racha de $a_1$ enteros consecutivos, con un resultado positivo de las representaciones y quiere estar seguro de que su $n$ es el menor de estos números, esto es equivalente a pedir un límite inferior en el conductor de $\mathfrak{c}(a,b,c)$ como se define en mi post anterior. En tres variables, se sabe que

$\mathfrak{c}(a,b,c) \geq \sqrt{3abc} - a - b - c + 1$,

así que usted puede empezar a buscar allí. La desigualdad procede de la siguiente papel.

J. L. Davison, En el Lineal de Diophantine Problema de Frobenius, J. Teoría de los números, 48 (1994), no. 3, 353-363.

Answer 3

El caso de 2 tamaños fue dada como un problema de poner los sellos en las cartas por Sylvester. Si el sello denominaciones $p$$q$,$\gcd(p,q) = 1$, Alexander Bogomolny tiene una bonita prueba que la máxima de no-representable número es $A(p, q) = p q - p - q$.

Formulario de la familia de las progresiones aritméticas: $$ \begin{align*} f_0 &= 0 + 0 q, 0 + 1 q, 0 + 2 q, \ldots \\ f_1 &= 1 + 0 q, 1 + 1 q, 1 + 2 q, \ldots \\ \vdots \\ f_{p - 1} &= p - 1 + 0 q, p - 1 + 1 q, p - 1 + 2 q, \ldots \end{align*} $$ Como $\gcd(p, q) = 1$, las secuencias son disjuntos y su unión es todos los números representables como $x p + y q$. La siguiente generación de función representa el conjunto: $$ F(z) = \frac{1}{1 - z^p} (1 + z^p + z^{2 p} + \dotsb + z^{(p - 1) p}) = \frac{1 - z^{p, q}}{(1 - z^p) (1 - z^q)} $$ El conjunto $\mathbb{N}_0$ es simplemente: $$ N(z) = \frac{1}{1 - z} $$ La diferencia es un polinomio cuyos exponentes dar la no-representable números: $$ N(z) - F(z) = \frac{(1 - z^p) (1 - z^q) - (1 - z) (1 - z^{p, q})} {(1 - z) (1 - z^p) (1 - z^q)} $$ Restando grados obtenemos el grado del polinomio, es decir, $A(p, q) = p q - p - q$.

Si usted tiene $a$, $b$, y $c$ pares de primos relativos, entonces $A(a, b, c) \le \min\{A(a, b), A(a, c), A(b, c)\}$

Answer 4

En este caso concreto se describe en Wikipedia sobre el problema de monedas, donde se muestra la máxima de que no se puede comprar es $43$.

Answer 5

Es así que después de este post ha sido publicado y solo sé un poco sobre el tema, pero si la pregunta es solo por dónde empezar el programa que debe ser bastante simple:

Nota en primer lugar de la fórmula para resolver el problema de dos variables: Encontrar el mínimo de N tal que $$ ax + by \neq N $$ Teorema: N = ab - a - b = (a - 1)*(b - 1) - 1

WLOG asumir un < b.

La reducción de un mod, solo tenemos que encontrar el punto en el que cada clase de congruencia en una es, finalmente, llenado, y luego restar una.

Dado que sólo tenemos otro número, b, simplemente calcular r tal que $ r + b \equiv 0 $ para encontrar el último número que aparece en la serie de la adición de b a sí mismo un mod. En ese número, el último de la congruencia de la clase se llena, así que sabemos que $ N \equiv r $ (mod a)

Ahora sabemos que la b tuvo que ser añadido al valor de la segunda a la última de la congruencia, y que la adición de b el valor de un momento a sí mismo producirá ab, que es equivalente a 0 mod a. De ello se sigue que r representa ab - b en los enteros.

Este número es el primer número, de tal forma que cada valor después de que se llene, porque sabemos que ab es resuelto y cada una de congruencia de la clase después de ab - b, serán llenadas por la adición de b a sí mismo un modulo. Por lo tanto, ab - b - a es el primer número que NO PUEDE ser hecho.

Si tenemos más de dos tipos de cajas de McNuggets, entonces la respuesta que obtenga debe ser menor que ab - a - b, ya que si sólo tuviéramos los dos podríamos McCalculate a nuestras anchas.

La introducción de un tercer número complica este método cuando b y c están lejos, porque vamos a tener que decidir si es más fácil para agregar por el número más alto, o el número más pequeño modulo una. Pero sólo podemos añadir que cada uno de ellos un número finito de veces, y cómo muchos de los valores de c podemos añadir antes de que nos busto ab - a - b puede ser fácilmente calculada. Una vez que se constata el más difícil de la congruencia de la clase/clases para hacer, simplemente se convierte en un asunto de que manera se hace con b y c modulo para ver si es la más fácil.

Esperemos que le da una forma concisa y primaria en la manera de responder a la pregunta por siempre y para todas las cantidades de los insumos.