Teorema Chicken McNuggets

[Vladislao]

Teorema

Sean [math]a y [math]b enteros positivos coprimos entre sí. Consideremos para cada [math]n natural la ecuación [math]ax+by=n, donde [math]x e [math]y son enteros no negativos. Entonces, el mayor [math]n tal que no existen [math]x e [math]y no negativos verificando dicha igualdad, es [math]n=ab-a-b.

Corolario: La cantidad de números [math]n que no se pueden escribir como suma de múltiplos positivos de [math]a y [math]b es [math]K=\frac{(a-1)(b-1)}{2}.


Demostración:

Spoiler: mostrar

Diremos que si la ecuación [math]ax+by=n tiene soluciones no negativas [math]x,y entonces [math]n es bueno.

Veamos que si [math]n=ab-a-b entonces no hay solución para la ecuación [math]ax+by=n.

En efecto, supongamos que hay algún par de enteros no negativos [math](x,y) satisfaciendo [math]ax+by = ab-a-b. Entonces, ciertamente [math]a(x+1)+b(y+1)=ab. Luego, [math]a\mid b(y+1) y [math]b\mid a(x+1). Como [math]a y [math]b eran coprimos, resulta que [math]a \mid y+1 y [math]b\mid x+1. Sigue que [math]y+1 = k_1a y [math]x+1 = k_2b para ciertos [math]k_1 y [math]k_2 enteros no negativos. Luego, [math]ab = a(x+1)+b(y+1) = abk_2+bak_1, sigue que [math]1 = k_2+k_1. Luego, como [math]k_1 y [math]k_2 eran enteros no negativos, uno debe ser [math]0 y el otro [math]1. En ambos casos se ve el absurdo fácilmente.

Probaremos ahora que si [math]n\geq ab-a-b+1, entonces [math]n es bueno.

Consideremos por el momento la ecuación general [math]ax+by=n con [math]x,y\in \mathbb{Z}. Hay una única solución en la que [math]0\leq y \leq a-1. En efecto, tomando módulo [math]a, resulta que [math]by\equiv n \pmod{a}, de donde [math]y\equiv nb^{-1}\pmod{a}, como queríamos.

Veamos ahora que [math]n es bueno si y sólo si, para [math]0\leq y \leq a-1, existe [math]x\geq 0 tal que [math]ax+by=n. En efecto, si [math]x\geq 0, basta tomar [math](x,y) y estamos. Para la recíproca notemos que si [math]x< 0 entonces [math]n no es bueno: en efecto, como [math](x,y) es solución a la ecuación [math]ax+by=n en enteros, resulta que todas las soluciones son de la forma [math]x'=x-b\lambda y [math]y'=y+a\lambda, donde [math]\lambda es un entero. Luego, para [math]\lambda\leq 0, es claro que [math]y'=y+a\lambda \leq (a-1)+a\lambda <0, y [math]n no es bueno. Y si, [math]\lambda>0, resulta que [math]x'=x-b\lambda \leq x < 0 y [math]n no es bueno. Luego, hemos probado lo que queríamos.

Luego, podemos pensar el conjunto de todos los enteros positivos [math]n que no son buenos como el conjunto de todos los enteros de la forma [math]ax+by con [math]x<0 y [math]0\leq y\leq a-1. Luego, si [math]n no es bueno, resulta [math]n = ax+by \leq a\cdot (-1) + b(a-1) = ab-a-b. De donde si [math]n\geq ab-a-b+1 entonces [math]n es bueno, como queríamos probar.

Notemos que podemos calcular ahora fácilmente cuántos enteros positivos [math]n no son buenos. En efecto, sea [math]1 \leq n \leq ab-a-b, veamos que [math]n es bueno si y sólo [math](a-1)(b-1)-n+1 no es bueno. Basta con probar una implicación (la otra se deduce muy trivialmente).

Llamaremos [math]C(n) = (a-1)(b-1)-n+1.

Si [math]n y [math]C(n) fueran buenos simultáneamente, entonces existirían [math]x_1, y_1, x_2, y_2 enteros no negativos tales que [math]ax_1+by_2=n y [math]ax_2+by_2=C(n). Luego, sigue que [math]a(x_1+x_2)+b(y_1+y_2)=n+C(n) = ab-a-b. Como [math]x_1+x_2 y [math]y_1+y_2 son enteros no negativos resulta que [math]ab-a-b es bueno, lo cual es un absurdo.

Si [math]n y [math]C(n) no fueran buenos simultáneamente, entonces tomando [math]0 \leq y_1,y_2 \leq a-1, no existen [math]x_1,x_2\geq 0 tales que [math]ax_1+by_1=n y [math]ax_2+by_2=C(n). Como [math]a(x_1+x_2)+b(y_1+y_2) = ab-a-b, tomando módulo [math]a, resulta que [math]y_1+y_2\equiv -1 \pmod{a}, de donde sólo puede ser [math]y_1+y_2=a-1. Pero si [math]y_1+y_2=a-1, entonces [math]a(x_1+x_2)+b(a-1) =ab-a-b de donde [math]a(x_1+x_2) = ab, y por lo tanto [math]x_1+x_2=b, pero [math]x_1 y [math]x_2 eran negativos, absurdo.

De todo ésto, resulta finalmente que de entre los números entre [math]1 y [math]ab-a-b+1 exactamente la mitad son buenos y la mitad no. Resulta finalmente que la cantidad de números que no son buenos es [math]K = \frac{ab-a-b+1}{2}=\frac{(a-1)(b-1)}{2}.

[CarlPaul_153]

Este lo saqué de los apuntes generales de Martín (Muchas gracias de paso, me sirvió mucho):

Problema 13: Decidir si es posible armar un rectángulo de [math]39 \times 44 sin huecos
ni superposiciones, usando exclusivamente piezas rectangulares de [math]5 \times 11. ¿Y si
el rectangulo que se quiere armar es de [math]42 \times 55? ¿Y si es de [math]39 \times 55? En cada
caso, si la respuesta es afirmativa, dar un ejemplo y en caso contrario, explicar
por que.
ACLARACIÓN: En todos los casos está permitido girar las piezas

Spoiler: mostrar

Bueno, tenemos la ecuación [math]5x+11y=n, donde [math]x e [math]y no pueden ser negativos. Por Teorema Chicken McNugget [math]n>5 \times 11-5-11=39. Por lo tanto los rectángulos de [math]39 \times 44 y [math]39 \times 55 no pueden formarse con piezas de [math]5 \times 11.
Ahora para el rectangulo [math]55 \times 42, si desarrollamos las ecuaciones [math]5x+11y=42 y [math]5x+11y=55 nos queda que las únicas posibilidades con [math]x e [math]y no negativos son:
[math]5(4)+11(2)=42
[math]5(0)+11(5)=55
[math]5(11)+11(0)=55
Por lo tanto, si 42 es el ancho y 55 el largo del rectángulo, lo podremos armar con 5 columnas de 5 de ancho y 11.5 de largo cada una, y 2 columnas de 11 de ancho y 5.11 de largo cada una.
A modo de curiosidad, hay [math]\binom{6}{2}=15 formas de armar el rectángulo.

[Caro - V3]

Por Teorema Chicken McNugget [math]n>5 \times 11-5-11=39

Este teorema dice que a partir de cierto punto todos los números se pueden expresar como [math]ax + by con [math]x e [math]y enteros no negativos, pero no significa que ninguno de los números menores se pueda expresar de esa forma.

Ejemplo con [math]a = 2 y [math]b = 9:
Queremos encontrar el mayor [math]n que no se puede expresar como [math]ax + by con [math]x e [math]y enteros no negativos.
El teorema nos dice que este es el número [math]n = ab - a - b = 2 \times 9 - 2 - 9 = 7.
Veamos qué pasa para los naturales menores a [math]7:

• [math]1 no se puede.
• [math]2 = 2 \times 1 + 9 \times 0. Por lo tanto [math]2 se puede expresar como [math]ax + by con [math]x e [math]y enteros no negativos.
• [math]3 no se puede.
• [math]4 = 2 \times 2 + 9 \times 0. Por lo tanto [math]4 se puede expresar como [math]ax + by con [math]x e [math]y enteros no negativos.
• [math]5 no se puede.
• [math]6 = 2 \times 3 + 9 \times 0. Por lo tanto [math]6 se puede expresar como [math]ax + by con [math]x e [math]y enteros no negativos.

Y como dice el teorema, todos los números mayores o iguales a [math]7 se pueden expresar como [math]ax + by con [math]x e [math]y enteros no negativos. Doy un par de ejemplos, pero es fácil de verificar: [math]8 = 2 \times 4 + 9 \times 0 \;,\; 9 = 2 \times 0 + 9 \times 1 \;,\; 10 = 2 \times 5 + 9 \times 0 \;,\; 11 = 2 \times 1 + 9 \times 1 \;,\; \ldots

[CarlPaul_153]

Este teorema dice que a partir de cierto punto todos los números se pueden expresar como [math]ax + by con [math]x e [math]y enteros no negativos, pero no significa que ninguno de los números menores se pueda expresar de esa forma.

tienes razón, me había dado cuenta e incluso antes de resolver el problema verifiqué que no se podía con 39, pero se me chispoteó. Lo más que puede hacer este teorema en este problema es asegurarte que vas a encontrar valores no negativos para las ecuaciones con n>39.

Uno mas facil:

En el país de los gnomos existen solo monedas de 7 gnomo pesos y 30 gnomo pesos, el objeto más barato en el mundo cuesta 2000 gnomo pesos. Demostrar que cualquier objeto puede ser comprado con dichas monedas.

solución 1

Spoiler: mostrar

[math]7x+30y=n Por Teorema Chicken McNugget se puede con cualquier [math]n>7.30-7-30=173

solución 2

Spoiler: mostrar

Si el objeto cuesta 7k, lo podremos comprar utilizando monedas de 7 gnomo pesos.
Ahora:
30≡2 m(7)
30.2≡4 m(7)
30.3≡6 m(7)
30.4≡1 m(7)
30.5≡3 m(7)
30.6≡5 m(7)
Por lo tanto, el objeto que mas veces me requiere usar monedas de 30 gnomo pesos es aquel que sea congruente a 5 modulo 7. Y 30x6=180 pero los 6 numeros anteriores, como ninguno es congruente a 5 modulo 7 ni mayor que 30.5=150 también son validos. por lo tanto, puedo comprar de forma exacta cualquier objeto mayor a 173.
NOTA: Supongo que esta solución es basicamente la demostración del Chicken Mcnugget con un ejemplo, explicado con mis palabras. Tampoco es que me haya detenido a leer la demostración del teorema. Capaz es similar...

Petición: Este ejercicio, en la pagina que lo encontre, pedía ser resuelto por inducción, pero no se me ocurre como plantearlo, asi que agradecería mucho si alguien me explica como es.
Nota: Pense que el nombre de el teorema era un chiste, pero buscando en internet, me cercioré de que es verdadero. Inclusive está el Teorema del Sandwich, el Teorema de la Pizza xD. http://eliatron.blogspot.com.ar/2013/10 ... ocina.html

[usuario250]

Nahhhh, en OMA es el Teorema de Pico, no porque lo inventé yo sino porque en un nacional en segundo nivel, en la corrección de problemas pasé a explicar uno y use ese teorema jaj.

[usuario250]

La demostración es facil. si k es entero positivo, k=x*a+y*b (probar que se pueden elegir x,y tales que x>(-b) e y>(-a) ).
entre x e y tiene que haber al menos un positivo (caso contrario x*a+y*b es "no positivo" al igual que el voto de un traidor)
si x es positivo, ab-a-b+k=(x-1)*a+(y+a-1)*b donde x-1 e y+a-1 son no negativos.
si y es positivo, ab-a-b+k=(x+b-1)*a+(y-1)*b donde x+b-1 e y-1 son no negativos.

[Vladislao]

La demostración es facil. si k es entero positivo, k=x*a+y*b (probar que se pueden elegir x,y tales que x>(-b) e y>(-a) ).
entre x e y tiene que haber al menos un positivo (caso contrario x*a+y*b es "no positivo" al igual que el voto de un traidor)
si x es positivo, ab-a-b+k=(x-1)*a+(y+a-1)*b donde x-1 e y+a-1 son no negativos.
si y es positivo, ab-a-b+k=(x+b-1)*a+(y-1)*b donde x+b-1 e y-1 son no negativos.

En el post original la idea es exactamente esa. Los pasos están hechos con mucho detalle (incluso probando resultados más fuertes como la unicidad de esos [math]x e [math]y que vos marcaste -que es lo que usás después para hallar la cantidad de números buenos-).

[usuario250]

No sabía que estaba la demostración en el post oficial. después lo vi.

[ricarlos]

es "no positivo" al igual que el voto de un traidor

En cambio Bulu ese si que es afin (del verbo afanar) con Barbie.

[julianferres_]

Como [math]a(x_1+x_2)+b(y_1+y_2) = ab-a-b, tomando módulo [math]a, resulta que [math]y_1+y_2\equiv -1 \pmod{a}, de donde sólo puede ser [math]y_1+y_2=a-1. Pero si [math]y_1+y_2=a-1, entonces [math]a(x_1+x_2)+b(a-1) =ab-a-b de donde [math]a(x_1+x_2) = ab, y por lo tanto [math]x_1+x_2=b, pero [math]x_1 y [math]x_2 eran negativos, absurdo.

En realidad te queda [math]a(x_1+x_2)+b(a-1)=ab-a-b \Rightarrow x_1+x_2=-1 y tambien es facil ver que no se puede