Iberoamericana 2016 P4

Avatar de Usuario
ésta

Colaborador OFO - Jurado
Mensajes: 292
Registrado: Sab 16 Oct, 2010 4:55 pm
Medallas: 4
Nivel: Ñandú

Iberoamericana 2016 P4

Mensaje sin leer por ésta » Mié 28 Sep, 2016 5:25 pm

Determine la mayor cantidad de alfiles que se pueden colocar en un tablero de ajedrez de [math]. tal que no haya dos alfiles en la misma casilla y cada alfil sea amenazado como máximo por uno de los otros alfiles.
Nota: Un alfil amenaza a otro si ambos se encuentran en dos casillas distintas de una misma diagonal. El tablero tiene por diagonales las 2 diagonales principales y las paralelas a ellas.
Imagen

Avatar de Usuario
Emerson Soriano

OFO - Mención OFO - Medalla de Oro OFO - Medalla de Plata OFO - Medalla de Bronce
Mensajes: 786
Registrado: Mié 23 Jul, 2014 10:39 am
Medallas: 4

Re: Iberoamericana 2016 P4

Mensaje sin leer por Emerson Soriano » Mié 28 Sep, 2016 10:39 pm

Spoiler: mostrar
Etiquetemos las casillas del tablero como sigue:
Sean [math] el conjunto de los alfis que se encuentra en la diagonal [math] (esquina superior derecha); [math] el conjunto de los alfis que se encuentran en la diagonal [math]; [math] el conjunto de los alfis que se encuentran en la diagonal [math], y así sucesivamente, hasta llegar a [math] que es el conjunto de los alfis que se encuentran en la diagonal [math] (esquina inferior izquierda). Es claro que [math].

Analicemos los conjuntos [math], [math], [math], ... , [math]. Notemos que cada uno de los elementos de [math], [math], [math], ... , [math] están en etiquetas pares. Si existen índices distintos [math] tales que ambos contienen algún elemento con la misma etiqueta, entonces en el tablero no hay ningún alfi más con esa misma etiqueta. Probaremos que entre los conjuntos [math], [math], [math], ... , [math], no hay más de dos de ellos que tienen exactamente dos elementos. En efecto, si hubieran al menos tres conjuntos con exactamente dos elementos, sean [math], [math] y [math] tres de los conjuntos con exactamente dos elementos. Luego, si [math] es un alfí de [math], pintamos todas las casillas que tienen la misma etiqueta de la casilla donde está [math]. Lo mismo hacemos con [math] y [math]. En total, hemos pintado seis bloques completos de etiquetas. Además, es claro que si todas las casillas de la etiqueta [math] han sido pintadas, entonces en ese bloque de etiquetas pintadas sólo hay un alfí. Como sólo estamos analizando casillas con etiquetas pares, entonces quedan sin pintar dos bloques completos de etiquetas, digamos las etiquetas [math], [math], pero nos quedan cinco conjuntos [math] por analizar. Como los elementos de esos cinco conjuntos [math] no están en [math], [math] y [math], entonces deben estar en casillas con etiquetas [math] o [math], pero por el principio de las casillas tenemos que hay tres casillas con la etiqueta [math] o [math], lo cual es absurdo. Por lo tanto, entre los conjuntos [math], [math], [math], ... , [math], hay a lo sumo dos de ellos con exactamente dos elementos, es decir, en el conjunto [math] hay a lo sumo [math] elementos. De manera análogo se analiza para los conjuntos [math], [math], [math], ... , [math], que también tienen entre todos a lo sumo [math] elementos. Por lo tanto, en todo el tablero hay a lo sumo [math] alfís.

El siguiente ejemplo es de @Guty.
Imagen

Avatar de Usuario
jhn

OFO - Medalla de Plata
Mensajes: 498
Registrado: Mié 10 Oct, 2012 3:25 pm
Medallas: 1
Nivel: Otro
Ubicación: Venezuela
Contactar:

Re: Iberoamericana 2016 P4

Mensaje sin leer por jhn » Lun 03 Oct, 2016 11:36 am

Spoiler: mostrar
El tablero tiene 30 diagonales (incluyendo las de una sola casilla en las esquinas). Si dos alfiles se atacan entonces bloquean 3 diagonales: la que ocupan y las dos perpendiculares a ella por donde están los alfiles. Luego las diagonales con 2 alfiles son la tercera parte de las diagonales ocupadas, o sea que a lo más habrá 10 diagonales con 2 alfiles y 20 con uno. Si contamos los alfiles por diagonales, esto da un máximo de [math], pero con cada alfil contado dos veces. Luego 20 es una cota superior, y mostrando un ejemplo con 20 se termina el problema.
Todo problema profana un misterio; a su vez, al problema lo profana su solución.
www.jhnieto.org

Avatar de Usuario
Violeta

OFO - Mención FOFO 7 años - Medalla Especial OFO - Medalla de Bronce
Mensajes: 361
Registrado: Sab 04 Jun, 2016 11:50 pm
Medallas: 3
Ubicación: Puerto Rico

Re: Iberoamericana 2016 P4

Mensaje sin leer por Violeta » Jue 06 Jul, 2017 8:08 pm

Spoiler: mostrar
Si coloreamos el tablero, pues, como un tablero de ajedrez, nos damos cuenta que los alfiles solo pueden atacar alfiles en su mismo color. Por ende, podemos solo considerar los alfiles colocados en casillas blancas. Cada par de alfiles amenzandose el uno al otro previenen que hayan otros alfiles en tres diagonales (la diagonal que comparten y las perpendiculares a estas diagonales por los alfiles). Es decir, cada dos alfiles "bloquean" tres diagonales. Vemos que hay 15 diagonales blancas, por lo que hay como mucho [math] alfiles en las casillas blancas, de donde tambien se deduce que hay como mucho 5 pares de alfiles que se amenazan mutuamente.. Si ahora consideramos las casillas negras, hay como mucho 20 alfiles posibles. Entonces, falta encontrar el ejemplo que cumpla. No voy a poner el que encontre por vago que soy y porque no quiero tomar el tiempo para hacer una cuadricula y pintarla en [math]. Uso la de @EmersonSoriano, en vez. :)

Para probar que no se puede con mas, asumamos que existe un ejemplo con 11 alfiles o mas. Digamos que hay una casilla blanca en la esquina inferior derecha. Entonces, hay 7 diagonales que corren de izquierda superior a derecha inferior. Ahora, por palomar, hay por lo menos 4 diagonales con alfiles amenazandose (porque asumimos que era un ejemplo valido, y hay como mucho dos alfiles por diagonal). Ahora consideramos las 8 diagonales que corren de derecha superior a izquierda inferior. Tambien, en estas diagonales se puede ver que hay por lo menos 3 diagonales en las que una pareja alfiles se amenazan el uno al otro. Estas 7 parejas de alfiles son todas distintas la una a la otra, absurdo, pues habiamos visto que como mucho pueden haber 5 parejas de alfiles amenazandose.. Entonces, no se puede con 11 o mas alfiles en un mismo color.
Para todo [math], existen [math] primos en sucesión aritmética.

Responder