Selectivo Ibero 2019 - Problema 1

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

Colaborador OFO - Jurado FOFO 6 años - Jurado
Mensajes: 928
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 6
Nivel: Exolímpico

Selectivo Ibero 2019 - Problema 1

Mensaje sin leer por Matías V5 » Jue 08 Ago, 2019 6:30 pm

Sea $n$ un entero positivo. En un tablero de $(2n+1)\times(2n+1)$ Matías marca alternativamente una cruz o un punto en cada casilla hasta completar el tablero (primero marca una cruz). Luego cuenta la cantidad de filas que tienen más cruces que puntos y la cantidad de columnas que tienen más puntos que cruces. Sean $X$ y $P$ respectivamente estas cantidades. El puntaje de Matías es $X+P$. Determinar, para cada $n$, el mayor puntaje que puede obtener Matías.
"La geometría es el arte de hacer razonamientos correctos a partir de figuras incorrectas." -- Henri Poincaré

BrunZo

OFO - Medalla de Bronce FOFO 8 años - Mención Especial OFO - Medalla de Plata FOFO Pascua 2019 - Medalla FOFO 9 años - Medalla Especial
Mensajes: 208
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 5
Nivel: 1

Re: Selectivo Ibero 2019 - Problema 1

Mensaje sin leer por BrunZo » Jue 08 Ago, 2019 6:39 pm

Idea de solución:
Spoiler: mostrar
Es claro que, analizando por separado columnas y filas, $X\leq 2n$ y $P\leq 2n$.

Avatar de Usuario
Fran5

OFO - Medalla de Oro OFO - Jurado FOFO Pascua 2019 - Jurado FOFO 7 años - Jurado FOFO 8 años - Jurado
Mensajes: 894
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 9
Nivel: Exolímpico
Ubicación: Santa Fe

Re: Selectivo Ibero 2019 - Problema 1

Mensaje sin leer por Fran5 » Jue 08 Ago, 2019 8:12 pm

Spoiler: mostrar
Observemos que si gira el tablero unos 90 grados, entonces tiene un puntaje de $(4n+2)-(X+P)$, puesto que una fila suma si y sólo si no suma cuando la ve como columna.

Es claro que no se puede tener puntaje $0$, pues contando por filas y por columnas habría más cruces que puntos y viceversa
Del mismo modo, si $X=1, P=0$ entonces hay a lo más $(2n+1)+n(2n)$ cruces y $n(2n+1)$ puntos, lo cual sería en total $4n^2+3n+ 1 <(2n+1)^2$ puntos y cruces. Abrsurdo

Luego $X,P \geq 1$, con lo cual $X,P \leq 2n$.

El ejemplo es el siguiente: Colocamos cualquier cosa en la casilla superior izquierda, luego cruces en la primer columna y puntos en la primer fila. El resto, como es un subtablero de lado par, lo dejamos tipo ajedrez.
Luego hay $n+1$ cruces (y puntos) en cada una de las filas (y columnas) que van desde la segunda hasta la última

Y el puntaje total es $X+P = 4n$
"Al toque Roque // Al pique Quique // Tranca palanca // No pasa nada // Argentina Gana // La tenés adentro // Costa Rica te entro"

The_CastaT
Mensajes: 4
Registrado: Mar 10 Abr, 2018 4:56 pm
Nivel: 2

Re: Selectivo Ibero 2019 - Problema 1

Mensaje sin leer por The_CastaT » Jue 08 Ago, 2019 8:15 pm

El mayor numero que puede obtener Matías es 3.n+1.
Lo que pensé fue que para que se cuente una X tendría que haber al menos n+1 cruces en la fila. Si se aplica así en todas las filas entonces tendrías 2.n+1=X.
Si todas las cruces estuvieran juntas en un rectángulo [(2.n+1).(n+1)]. Entonces tendrías un espacio de n.(2.n+1), si en las columnas hay al menos n+1 de puntos en una columna entonces cuenta como P. La máxima cantidad de P ahora seria n.
entonces la suma entre X y P seria (2.n+1)+n = 3.n+1.

Avatar de Usuario
Matías V5

Colaborador OFO - Jurado FOFO 6 años - Jurado
Mensajes: 928
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 6
Nivel: Exolímpico

Re: Selectivo Ibero 2019 - Problema 1

Mensaje sin leer por Matías V5 » Jue 08 Ago, 2019 8:28 pm

The_CastaT escribió:
Jue 08 Ago, 2019 8:15 pm
El mayor numero que puede obtener Matías es 3.n+1.
Lo que pensé fue que para que se cuente una X tendría que haber al menos n+1 cruces en la fila. Si se aplica así en todas las filas entonces tendrías 2.n+1=X.
Si todas las cruces estuvieran juntas en un rectángulo [(2.n+1).(n+1)]. Entonces tendrías un espacio de n.(2.n+1), si en las columnas hay al menos n+1 de puntos en una columna entonces cuenta como P. La máxima cantidad de P ahora seria n.
entonces la suma entre X y P seria (2.n+1)+n = 3.n+1.
Hola @The_CastaT!
Fijate que no puede pasar que en todas las filas haya más cruces que puntos, porque si así fuera, en el tablero habría por lo menos $2n+1$ cruces más que puntos, mientras que según el enunciado Matías va completando las casillas alternadamente (una cruz, un punto, una cruz, un punto, etc.) así que sólo termina habiendo una cruz más que puntos.
Por otra parte, aún si fuera cierto que se puede conseguir que $X=2n+1$, fijate que no es necesariamente cierto que el máximo puntaje se obtenga en ese caso: en teoría, podría pasar que te convenga usar un valor más chico de $X$ para poder conseguir un $P$ más grande, aumentando así la suma de ambos. O sea que, aún si esa fuera la respuesta correcta (en este caso no lo es) faltaría más justificación para que la solución esté completa.
Saludos!
"La geometría es el arte de hacer razonamientos correctos a partir de figuras incorrectas." -- Henri Poincaré

Responder