Olimpíada de Mayo 2022 N2 P1

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Matías V5

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2016 FOFO 6 años - Jurado-FOFO 6 años OFO - Jurado-OFO 2017
OFO - Jurado-OFO 2018 OFO - Jurado-OFO 2020 OFO - Jurado-OFO 2021
Mensajes: 1114
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 8
Nivel: Exolímpico

Olimpíada de Mayo 2022 N2 P1

Mensaje sin leer por Matías V5 »

En un tablero de $7 \times 7$ algunas casillas están pintadas de rojo. Sea $a$ la cantidad de filas que tienen un número impar de casillas rojas y sea $b$ la cantidad de columnas que tienen un número impar de casillas rojas. Determinar todos los posibles valores de $a+b$.
Para cada valor hallado, dar un ejemplo de cómo puede estar pintado el tablero.
We gave you a start so you'd know what to do
You've seen how it works, now it's over to you (...)
For there's so much more to explore!

Numberblocks - https://www.youtube.com/watch?v=KzTR72_srTU
sebach

Colaborador-Varias OFO - Medalla de Bronce-OFO 2017 OFO - Medalla de Bronce-OFO 2018 OFO - Medalla de Bronce-OFO 2020 OFO - Medalla de Plata-OFO 2021
OFO - Medalla de Plata-OFO 2022 OFO - Medalla de Plata-OFO 2023 OFO - Medalla de Oro-OFO 2024
Mensajes: 202
Registrado: Dom 06 Mar, 2011 11:49 am
Medallas: 8
Nivel: Exolímpico

Re: Olimpíada de Mayo 2022 N2 P1

Mensaje sin leer por sebach »

Spoiler: mostrar
Lo importante de notar de este (lindo según mi opinión) problema, es que al cambiar una celda de color, la cantidad de casillas rojas de la fila en la que está cambia la pariedad (suma o resta $1$), y lo mismo ocurre con la columna en la que está esa casilla. Por lo que al hacer un cambio, cualquiera sea, el valor de $a + b$ mantiene su pariedad (o bien aumenta en $2$, o bien disminuye en $2$, o bien se mantiene.

Si todas las casillas quedaran sin pintar, $a = 0, b = 0, a + b = 0$. Por lo que $a+b$ siempre será par (interesante que ocurre en cualquier tablero, sin importar las dimensiones).
Ahora, podemos obtener configuraciones en donde $a + b$ nos de cualquier valor par entre $0$ y $7 + 7 = 14$ (todo el tablero pintado) ?

La respuesta es sí. Vayamos pintando de a una casilla de la diagonal principal. Pintando la primera, $a=1, b=1, a+b=2$. Pintando la segunda, $a=2, b=2, a+b=4$. Y así, como nos movemos a filas y columnas vacías en cada movimiento, $a$ y $b$ aumentan siempre en $1$. Por lo que así seguieremos aumentando $a$ y $b$ en $1$, hasta llegar a pintar toda la diagonal, en donde $a=7, b=7, a+b=14$. Como $a, b \leq 7$, $a + b \leq 14$, y como dijimos que su suma debe ser par y vimos que podemos obtener todos los valores pares de $0$ a $14$ inclusive, estos son todos los posibles valores.
Avatar de Usuario
Ulis7s

OFO - Mención-OFO 2024
Mensajes: 183
Registrado: Dom 07 May, 2023 1:13 pm
Medallas: 1
Nivel: 1
Ubicación: La Pampa

Re: Olimpíada de Mayo 2022 N2 P1

Mensaje sin leer por Ulis7s »

$ Resolución:$
Spoiler: mostrar
Lo primero que vamos a demostrar es que $a$ y $b$ tienen la misma paridad, esto lo haremos por el método del absurdo.
Supongamos $a$ es par y $b$ es impar. Luego hay $x$ filas con $y$ casillas pintadas ($x$ par y $y$ impar). Luego hay $2$ casos:
a) Si las $y$ casillas hay por lo menos $2k +1$ en una misma columna con $k$ mayor que $0$ nos quedan $y-2k-1$ para repartir o sea una cantidad par ya que $y$ impar. Entonces $b$ = $1$ + impar = par o sea absurdo porque habíamos empezado afirmando que $b$ era impar.
b) Si las $y$ se distribuyen de manera que no haya $2$ en una misma columna pasa que $a=b$ y esto también es un absurdo ya que no hay un numero que sea par e impar a la vez.
Lo mismo podemos hacer para demostrar que no puede pasar que $b$ par y $a$ impar
Entonces como contradicción pasa que $a$ es par, y $b$ es par o $a$ es impar y $b$ es impar y esto nos conduce a que $a+b$ debe ser estrictamente par. Luego podemos notar que si tomamos el caso favorable de que $a=b$ y notamos que $a$ varia entre $0$ y $7$ entonces $b$ también variara entre $0$ y $7$. Luego $a+b=2a$ y como dijimos que $a$ variaba los posibles valores son los números pares desde $a=0$, $a+b=0$ hasta $a=7$, $a+b=14$.
O sea los posibles valores de $a+b$ son los pares desde $0$ hasta $14$ y para hacer todas estas coloraciones vamos haciendo los pasos que cumple el absurdo $b)$ los cuales serian ir pintando la diagonal de uno a uno; Empezando desde no tener nada pintado hasta tener toda la diagonal pintada.✩
We needed 5 more more points!! :roll: @ulisess.kr
Responder