Teorema Chicken McNuggets

Avatar de Usuario
Vladislao

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2016 FOFO 6 años - Jurado-FOFO 6 años OFO - Jurado-OFO 2017
FOFO Pascua 2017 - Jurado-FOFO Pascua 2017
Mensajes: 809
Registrado: Mar 28 Dic, 2010 3:26 pm
Medallas: 6
Nivel: Exolímpico
Ubicación: Córdoba

Teorema Chicken McNuggets

Mensaje sin leer por Vladislao » Sab 07 Sep, 2013 7:25 pm

Teorema

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

Corolario: La cantidad de números [math] que no se pueden escribir como suma de múltiplos positivos de [math] y [math] es [math].


Demostración:
Spoiler: mostrar
Diremos que si la ecuación [math] tiene soluciones no negativas [math] entonces [math] es bueno.

Veamos que si [math] entonces no hay solución para la ecuación [math].

En efecto, supongamos que hay algún par de enteros no negativos [math] satisfaciendo [math]. Entonces, ciertamente [math]. Luego, [math] y [math]. Como [math] y [math] eran coprimos, resulta que [math] y [math]. Sigue que [math] y [math] para ciertos [math] y [math] enteros no negativos. Luego, [math], sigue que [math]. Luego, como [math] y [math] eran enteros no negativos, uno debe ser [math] y el otro [math]. En ambos casos se ve el absurdo fácilmente.

Probaremos ahora que si [math], entonces [math] es bueno.

Consideremos por el momento la ecuación general [math] con [math]. Hay una única solución en la que [math]. En efecto, tomando módulo [math], resulta que [math], de donde [math], como queríamos.

Veamos ahora que [math] es bueno si y sólo si, para [math], existe [math] tal que [math]. En efecto, si [math], basta tomar [math] y estamos. Para la recíproca notemos que si [math] entonces [math] no es bueno: en efecto, como [math] es solución a la ecuación [math] en enteros, resulta que todas las soluciones son de la forma [math] y [math], donde [math] es un entero. Luego, para [math], es claro que [math], y [math] no es bueno. Y si, [math], resulta que [math] y [math] no es bueno. Luego, hemos probado lo que queríamos.

Luego, podemos pensar el conjunto de todos los enteros positivos [math] que no son buenos como el conjunto de todos los enteros de la forma [math] con [math] y [math]. Luego, si [math] no es bueno, resulta [math]. De donde si [math] entonces [math] es bueno, como queríamos probar.

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

Llamaremos [math].

Si [math] y [math] fueran buenos simultáneamente, entonces existirían [math] enteros no negativos tales que [math] y [math]. Luego, sigue que [math]. Como [math] y [math] son enteros no negativos resulta que [math] es bueno, lo cual es un absurdo.

Si [math] y [math] no fueran buenos simultáneamente, entonces tomando [math], no existen [math] tales que [math] y [math]. Como [math], tomando módulo [math], resulta que [math], de donde sólo puede ser [math]. Pero si [math], entonces [math] de donde [math], y por lo tanto [math], pero [math] y [math] eran negativos, absurdo.

De todo ésto, resulta finalmente que de entre los números entre [math] y [math] exactamente la mitad son buenos y la mitad no. Resulta finalmente que la cantidad de números que no son buenos es [math].
2  
Sea [math] Para todo entero positivo [math] se cumple que [math] es un número primo.

Avatar de Usuario
CarlPaul_153
Mensajes: 119
Registrado: Vie 11 Oct, 2013 11:05 am
Nivel: 2

Re: Teorema Chicken McNugget

Mensaje sin leer por CarlPaul_153 » Jue 19 Dic, 2013 5:49 pm

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] sin huecos
ni superposiciones, usando exclusivamente piezas rectangulares de [math]. ¿Y si
el rectangulo que se quiere armar es de [math]? ¿Y si es de [math]? 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], donde [math] e [math] no pueden ser negativos. Por Teorema Chicken McNugget [math]. Por lo tanto los rectángulos de [math] y [math] no pueden formarse con piezas de [math].
Ahora para el rectangulo [math], si desarrollamos las ecuaciones [math] y [math] nos queda que las únicas posibilidades con [math] e [math] no negativos son:
[math]
[math]
[math]
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] formas de armar el rectángulo.
Si todo te da igual estás haciendo mal las cuentas. Albert Einstein.

Avatar de Usuario
Caro - V3

Colaborador-Varias OFO - Jurado-OFO 2015
Mensajes: 358
Registrado: Sab 16 Oct, 2010 4:20 pm
Medallas: 2
Nivel: Exolímpico

Re: Teorema Chicken McNugget

Mensaje sin leer por Caro - V3 » Jue 19 Dic, 2013 6:17 pm

CarlPaul_153 escribió:Por Teorema Chicken McNugget [math]
Este teorema dice que a partir de cierto punto todos los números se pueden expresar como [math] con [math] e [math] enteros no negativos, pero no significa que ninguno de los números menores se pueda expresar de esa forma.

Ejemplo con [math] y [math]:
Queremos encontrar el mayor [math] que no se puede expresar como [math] con [math] e [math] enteros no negativos.
El teorema nos dice que este es el número [math].
Veamos qué pasa para los naturales menores a [math]:
  • [math] no se puede.
  • [math]. Por lo tanto [math] se puede expresar como [math] con [math] e [math] enteros no negativos.
  • [math] no se puede.
  • [math]. Por lo tanto [math] se puede expresar como [math] con [math] e [math] enteros no negativos.
  • [math] no se puede.
  • [math]. Por lo tanto [math] se puede expresar como [math] con [math] e [math] enteros no negativos.
Y como dice el teorema, todos los números mayores o iguales a [math] se pueden expresar como [math] con [math] e [math] enteros no negativos. Doy un par de ejemplos, pero es fácil de verificar: [math]
3  
Guía de [math]: sirve para escribir ecuaciones como [math]

Avatar de Usuario
CarlPaul_153
Mensajes: 119
Registrado: Vie 11 Oct, 2013 11:05 am
Nivel: 2

Re: Teorema Chicken McNugget

Mensaje sin leer por CarlPaul_153 » Jue 19 Dic, 2013 6:25 pm

Este teorema dice que a partir de cierto punto todos los números se pueden expresar como [math] con [math] e [math] 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] Por Teorema Chicken McNugget se puede con cualquier [math]
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
Si todo te da igual estás haciendo mal las cuentas. Albert Einstein.

usuario250

OFO - Jurado-OFO 2015
Mensajes: 206
Registrado: Vie 30 Dic, 2011 12:30 pm
Medallas: 1

Re: Teorema Chicken McNugget

Mensaje sin leer por usuario250 » Jue 19 Dic, 2013 7:18 pm

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

OFO - Jurado-OFO 2015
Mensajes: 206
Registrado: Vie 30 Dic, 2011 12:30 pm
Medallas: 1

Re: Teorema Chicken McNuggets

Mensaje sin leer por usuario250 » Vie 20 Dic, 2013 8:08 pm

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.

Avatar de Usuario
Vladislao

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2016 FOFO 6 años - Jurado-FOFO 6 años OFO - Jurado-OFO 2017
FOFO Pascua 2017 - Jurado-FOFO Pascua 2017
Mensajes: 809
Registrado: Mar 28 Dic, 2010 3:26 pm
Medallas: 6
Nivel: Exolímpico
Ubicación: Córdoba

Re: Teorema Chicken McNuggets

Mensaje sin leer por Vladislao » Vie 20 Dic, 2013 10:18 pm

usuario250 escribió: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] e [math] que vos marcaste -que es lo que usás después para hallar la cantidad de números buenos-).
Sea [math] Para todo entero positivo [math] se cumple que [math] es un número primo.

usuario250

OFO - Jurado-OFO 2015
Mensajes: 206
Registrado: Vie 30 Dic, 2011 12:30 pm
Medallas: 1

Re: Teorema Chicken McNuggets

Mensaje sin leer por usuario250 » Sab 21 Dic, 2013 2:24 pm

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

ricarlos
Mensajes: 400
Registrado: Lun 17 Dic, 2012 2:24 pm

Re: Teorema Chicken McNuggets

Mensaje sin leer por ricarlos » Lun 24 Feb, 2014 7:10 pm

usuario250 escribió: es "no positivo" al igual que el voto de un traidor
En cambio Bulu ese si que es afin (del verbo afanar) con Barbie.
Dado un triangulo ABC y los puntos medios L, M y N de los lados BC, AC y AB, respectivamente, probar que las bisectrices de los angulos ANB, BLC y CMA son concurrentes.

Avatar de Usuario
julianferres_

OFO - Medalla de Bronce-OFO 2015 OFO - Medalla de Plata-OFO 2016 OFO - Medalla de Plata-OFO 2017
Mensajes: 388
Registrado: Sab 17 Sep, 2011 8:01 pm
Medallas: 3
Nivel: Exolímpico
Ubicación: Villa Ramallo, Buenos Aires

Re: Teorema Chicken McNuggets

Mensaje sin leer por julianferres_ » Lun 10 Nov, 2014 1:59 am

Vladislao escribió: Como [math], tomando módulo [math], resulta que [math], de donde sólo puede ser [math]. Pero si [math], entonces [math] de donde [math], y por lo tanto [math], pero [math] y [math] eran negativos, absurdo.
En realidad te queda [math] y tambien es facil ver que no se puede

Responder