OFO 2020 Problema 5

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Monazo

OFO - Medalla de Plata OFO - Medalla de Oro FOFO Pascua 2019 - Mención OFO - Jurado
Mensajes: 192
Registrado: Dom 14 Sep, 2014 2:30 pm
Medallas: 4
Nivel: 1

OFO 2020 Problema 5

Mensaje sin leer por Monazo » Mié 22 Ene, 2020 12:02 am

En el Certamen Nacional de la FOMA (Falsa OMA), los exolímpicos empezaron a corregir las planillas de la Odisea con el siguiente procedimiento. Inicialmente están todas las planillas en una sola pila. En cada operación se puede elegir una pila que tenga al menos $3$ planillas, corregir una planilla de esa pila y archivarla, y finalmente dividir el resto de la pila en dos nuevas pilas, no necesariamente iguales y con al menos una planilla cada una.
Los exolímpicos no recuerdan cuántas planillas tenían para corregir originalmente, así que recurren a los dos olímpicos con más memoria: Male y Raimu. El problema es que ellos tampoco lo recuerdan bien. Mientras que Male piensa que había $2019$ planillas, Raimu insiste en que la cantidad original era $2020$.
En cierto momento de la noche, los exolímpicos observaron que todas las pilas de planillas que aún quedaban por corregir tenían exactamente $4$ planillas cada una.
(a) ¿Puede pasar que Male tenga razón?
(b) ¿Puede pasar que Raimu tenga razón?

Avatar de Usuario
Monazo

OFO - Medalla de Plata OFO - Medalla de Oro FOFO Pascua 2019 - Mención OFO - Jurado
Mensajes: 192
Registrado: Dom 14 Sep, 2014 2:30 pm
Medallas: 4
Nivel: 1

Re: OFO 2020 Problema 5

Mensaje sin leer por Monazo » Sab 01 Feb, 2020 12:26 am

Solución Oficial

Caso 1: ¿Se puede con $2020$ planillas?
Spoiler: mostrar
Primero analizaremos el caso para $2020$ planillas, y vamos a demostrar que no es posible.
En un principio, tenemos una pila con $2020$. Si llamamos $x$ a la cantidad de pilas hasta el momento e $y$ a la cantidad de planillas "no corregidas", tenemos en un principio que $x+y=2021$. Ahora notemos que esta es una propiedad invariante. Cada vez que nosotros realizamos una operación, se corrige una planilla y a la vez se crea una nueva planilla. Por lo que obtenemos que $x$ aumenta en $1$ e $y$ disminuye en $1$, por lo que $x+1+y-1=x+y=2021$.

Si nosotros queremos obtener al final, varias pilas de $4$ planillas cada una, entonces se tiene que cumplir que la cantidad de planillas sin corregir, sea justamente $4$ veces la cantidad de pilas hasta el momento, por lo tanto, $y=4x$. Pero recordando que siempre tenemos que $x+y=2021$, sustituyendo obtenemos que $5x=2021$. Pero aquí llegamos a una contradicción, dado que $\frac{2021}{5}$ no es entero, por lo tanto, no es posible para el caso en que iniciamos con $2020$ planillas, debido a que necesitamos $404,2$ pilas al final, y las pilas son siempre enteras!!
Caso 2: ¿Se puede con $2019$ planillas?
Spoiler: mostrar
Notemos que ahora, la invariante es $x+y=2020$. Y si al final queremos que $y=4x$, obtenemos que $5x=2020$, por lo tanto, $x=404$, y es entero!! Pero acá sucede un error que varios cometieron, y hay que remarcar. Todo lo que estuvimos viendo, son todas condiciones necesarias para el problema. Es decir, lo que acabamos de ver, es que para que se cumpla el objetivo del problema, necesitamos obtener al final $404$ pilas de $4$ planillas cada una, pero que nuestra invariante no rompa, no significa que se puede, es decir, no es una condición suficiente. Por lo tanto debemos recurrir a otro método de análisis. Y a partir de acá pueden pasar dos cosas, que realmente se pueda, o quizás vemos otra propiedad que nos garantice que para $2019$ no se puede.
La mayoría de las veces sucede que cuando la invariante no rompe, es porque es muy probable que se pueda, y es ahí donde nos confiamos un poco, y tratamos de hallar un ejemplo. Si encontramos al menos un ejemplo ganamos, y demostramos de una manera sencilla que se puede.

Finalmente, el ejemplo es muy sencillo. De la pila inicial, en cada operación vamos a ir sacando $5$ planillas, donde una es corregida y archivada, y las otras $4$ forman una nueva pila de $4$. Por lo tanto, si vamos restando de a $5$, vamos a estar formando directamente pilas de $4$, y así hasta que nos queden $9$ planillas en la pila inicial. Es aquí donde retiramos nuevamente $5$ planillas más, y podemos notar que ahora se nos formarán $2$ pilas de $4$ planillas cada una, y la que resta es archivada. Y listo!! Ya con este ejemplo demostramos que para $2019$ se puede!!
Moralejas
Spoiler: mostrar
Voy a armar esta sección, para aprender algunos conceptos y que luego se traten de evitar en las pruebas oficiales.

$\bullet$ La primera moraleja es, que si encuentran alguna invariante, o alguna propiedad copada, siempre son muy útiles para demostrar que no se puede. Siempre hay que tratar de diferenciar cuando una condición es necesaria y cuando es suficiente. Estas propiedades que encontramos, suelen ser simplemente condiciones "necesarias", por eso son muy buenas para demostrar cuando algo no se puede realizar.

$\bullet$ Otra cosa que vi en las resoluciones, es que varios trataron de demostrar que para $2020$ no se puede, porque el método de resolución para $2019$ no funciona. Hay que tener cuidado con eso, porque están tratando de "forzar" el problema. La verdad es que existen demasiadas formas de resolución para $2019$ y por qué no, quizás alguna también sirva para $2020$. Traten de aprender a reconocer cuando están cometiendo este error, dado que es muy común, y muchas veces pasa, aunque traten de evitarlo, en el fondo lo están cometiendo.
Última edición por Monazo el Lun 03 Feb, 2020 4:08 pm, editado 1 vez en total.
4  

Avatar de Usuario
NPCPepe

FOFO 9 años - Mención Especial OFO - Medalla de Plata
Mensajes: 33
Registrado: Lun 17 Jun, 2019 9:22 pm
Medallas: 2
Nivel: 2
Ubicación: Argentina

Re: OFO 2020 Problema 5

Mensaje sin leer por NPCPepe » Sab 01 Feb, 2020 12:49 am

Spoiler: mostrar
El proceso inverso de la corrección es: tomar dos pilas, juntarlas y agregarle una planilla.
Dado un conjunto de pilas de $4$ planillas cada una, la cantidad de planillas es $4n$ siendo n la cantidad de pilas.
Al hacer una corrección inversa, la cantidad de planillas pasa a ser $4n+1$ ya que se agrega una planilla, y la cantidad de pilas disminuye en $1$ ya que se juntan $2$ pilas.

Cuando queda una sola planilla (la original), la cantidad de hojas es $4n+n-1=5n-1$, $2019$ tiene resto $4$ en la división por 5 por lo que puede tener forma $5n-1$ con $n$ entero pero $2020$ no se puede representar de esa forma ya que es multiplo de $5$. Entonces puede pasar que Male tenga razón pero no puede pasar que Raimu tenga razón.
$3=569936821221962380720^3+(-569936821113563493509)^3+(-472715493453327032)^3$: esta es la tercer menor solucion descubierta para la ecuación $a^3+b^3+c^3=3$ , las otras dos son $1^3+1^3+1^3=3$ y $4^3+4^3+(-5)^3=3$

Avatar de Usuario
Sandy

OFO - Medalla de Bronce OFO - Medalla de Plata
Mensajes: 90
Registrado: Lun 27 Nov, 2017 1:59 am
Medallas: 2
Nivel: 3

Re: OFO 2020 Problema 5

Mensaje sin leer por Sandy » Sab 01 Feb, 2020 12:58 am

Monazo escribió:
Mié 22 Ene, 2020 12:02 am
En el Certamen Nacional de la FOMA (Falsa OMA), los exolímpicos empezaron a corregir las planillas de la Odisea con el siguiente procedimiento. Inicialmente están todas las planillas en una sola pila. En cada operación se puede elegir una pila que tenga al menos $3$ planillas, corregir una planilla de esa pila y archivarla, y finalmente dividir el resto de la pila en dos nuevas pilas, no necesariamente iguales y con al menos una planilla cada una.
Los exolímpicos no recuerdan cuántas planillas tenían para corregir originalmente, así que recurren a los dos olímpicos con más memoria: Male y Raimu. El problema es que ellos tampoco lo recuerdan bien. Mientras que Male piensa que había $2019$ planillas, Raimu insiste en que la cantidad original era $2020$.
En cierto momento de la noche, los exolímpicos observaron que todas las pilas de planillas que aún quedaban por corregir tenían exactamente $4$ planillas cada una.
(a) ¿Puede pasar que Male tenga razón?
(b) ¿Puede pasar que Raimu tenga razón?
Spoiler: mostrar
Originalmente hay una pila, y con cada operación se crea una fila nueva, y la cantidad de planillas (no archivadas) se reduce en $1$.
Supongamos que inicialmente hay $I$ planillas y la cantidad de planillas corregidas fue $x$, tenemos que la cantidad de planillas restantes es $I-x$, y a la vez es $4$ veces la cantidad de pilas, es decir $4\times (x+1)$, por lo tanto:

$I-x=4x+4\Rightarrow I=5x+4 \Rightarrow I\equiv 4 (mod 5)$, por lo tanto no es posible que hubiera $2020$ planillas, pero sí $2019$.

Si en todas las operaciones se corrige una planilla de la pila original, y se aparte una nueva pila de $4$ planillas, después de $403$ operaciones habrá $403$ pilas de $4$ planillas, y la original tendrá $2019-403-4\times 403=4$ planillas, luego Male tiene razón.

Responder