OFO 2018 Problema 2

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

OFO - Medalla de Oro-OFO 2015 OFO - Jurado-OFO 2016 OFO - Jurado-OFO 2017 FOFO Pascua 2017 - Jurado-FOFO Pascua 2017 FOFO 7 años - Jurado-FOFO 7 años
OFO - Jurado-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019 FOFO 9 años - Jurado-FOFO 9 años
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Medalla de Bronce-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 1125
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 22
Nivel: Exolímpico
Ubicación: Santa Fe

OFO 2018 Problema 2

Mensaje sin leer por Fran5 »

Se tiene un tablero cuadriculado de $9 \times 9$ cuyas casillas están coloreadas alternadamente de blanco y de negro, como un tablero de ajedrez. En este tablero hay que colocar $8$ torres de manera que se cumplan simultáneamente las siguientes dos condiciones:
  • No puede haber dos torres que se ataquen entre sí, es decir que estén en una misma fila o en una misma columna del tablero.
  • Las $8$ torres deben estar en casillas del mismo color.
¿De cuántas maneras distintas se puede hacer esto?
"Al toque Roque // Al pique Quique // Tranca palanca // No pasa nada // Argentina Gana // La tenés adentro //
Avatar de Usuario
Fran5

OFO - Medalla de Oro-OFO 2015 OFO - Jurado-OFO 2016 OFO - Jurado-OFO 2017 FOFO Pascua 2017 - Jurado-FOFO Pascua 2017 FOFO 7 años - Jurado-FOFO 7 años
OFO - Jurado-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019 FOFO 9 años - Jurado-FOFO 9 años
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Medalla de Bronce-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 1125
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 22
Nivel: Exolímpico
Ubicación: Santa Fe

Re: OFO 2018 Problema 2

Mensaje sin leer por Fran5 »

Solución oficial:
Spoiler: mostrar
Supongamos primeramente, sin pérdida de generalidad, que las casillas de las esquinas son de color negro. Luego tenemos $41$ casillas negras y $40$ casillas blancas en nuestro tablero.

Supongamos que tenemos una distribuición de $8$ torres en el tablero tal que cualesquiera dos de ellas no se ataquen entre sí. De este modo, observamos que no puede haber dos torres en la misma fila ni en la misma columna.
A partir de esta observación, notamos que si en nuestro tablero intercambiamos dos filas ó dos columnas de lugar, la nueva distribución de las $8$ torres tampoco tendrá algún par de torres que se ataquen entre sí.

Luego, podemos transformar nuestro tablero "tipo ajedrez" en el siguiente tablero con $4$ subtableros.
Imagen
Ahora, procederemos a contar las formas de distribuir nuestras $8$ torres, dividiendo en dos casos: si ocupan casillas negras, u ocupan casillas blancas.
En cada caso deberemos considerar cuál será la fila/columna en la que no ubicaremos ninguna torre.

Si las torres ocupan casillas negras:

Consideramos sólo el subtablero superior izquierdo y el inferior derecho. Es claro que las torres de un subtablero no atacarán a otro.
Como podemos ubicar a lo más $5$ torres en el primero y $4$ torres en el segundo, tenemos dos posibilidades. Que haya $5$ en el primer subtablero y $3$ en el segundo, o que haya $4$ en cada uno.
  • Para la primer posibilidad, hay $5!$ maneras de ubicar las torres en el subtablero superior, y luego hay $4$ formas de quitar una columna del subtablero inferior. Considerando las $3$ columnas que nos quedan, hay $4 \cdot 3 \cdot 2 = 4!$ maneras de ubicar las $3$ restantes.
    Luego hay $5!\cdot 4 \cdot 4! = 11520$ maneras en esta primer posibilidad.
  • Para la segunda posibilidad, hay $5$ formas de quitar una columna del subtablero superior. Co-nsiderando las $4$ columnas que nos quedan, hay $5 \cdot 4 \cdot 3 \cdot 2 = 5!$ maneras de ubicar $4$ torres , y luego hay $4!$ maneras de ubicar las $4$ restantes en el subtablero inferior.
    Luego hay $5 \cdot 5! \cdot 4! = 14400$ maneras en esta segunda posibilidad.
Si las torres ocupan casillas blancas:

Consideramos sólo el subtablero superior derecho y el inferior izquierdo. Es claro que las torres de un subtablero no atacarán a otro.
Como podemos ubicara a lo más $4$ torres en cada subtablero, deberá haber exactamente $4$ en cada uno.
  • Para el subtablero inferior, distribuimos las torres fila por fila. Luego hay $5 \cdot 4 \cdot 3 \cdot 2 = 5!$ maneras de ubicar $4$ torres.
    Para el subtablero derecho, distribuimos las torres por columna. Contando del mismo modo, hay $5!$ maneras de ubicar las $4$ torres.
    Luego, hay $5!5! = 14400$ maneras en este segundo caso.
En total, tenemos $11520 + 14400 + 14400 = 40320$ maneras de ubicar las $8$ torres en el tablero cumpliendo las condiciones.
3  
"Al toque Roque // Al pique Quique // Tranca palanca // No pasa nada // Argentina Gana // La tenés adentro //
Matías

OFO - Medalla de Bronce-OFO 2016 OFO - Medalla de Bronce-OFO 2017 FOFO Pascua 2017 - Medalla-FOFO Pascua 2017 OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años
OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 COFFEE - Mención-COFFEE Ariel Zylber
Mensajes: 206
Registrado: Mar 06 Oct, 2015 7:59 pm
Medallas: 8
Nivel: 3

Re: OFO 2018 Problema 2

Mensaje sin leer por Matías »

Spoiler: mostrar
Aclaro que considero que las cuatro esquinas del tablero son casillas negras.

Vamos a decir que una columna o fila del tablero es negra si tiene $5$ casillas negras y $4$ blancas, y es blanca si tiene $5$ casillas blancas y $4$ negras. También vamos a decir que una casilla es $N\times N$ si está en columna y fila negras, es $N\times B$ si está en columna negra y fila blanca, es $B\times N$ si está en columna blanca y fila negras, y es $B\times B$ si está en columna y fila blancas.

Es importante ver que si dos torres están en casillas del mismo color, es imposible que se amenacen si están en columnas de distinto color o en filas de distinto color.

Para cada posible configuración del tablero, nos vamos a fijar en la casilla que no está amenazada por ninguna torre, que está en la columna y la fila vacías:

Si esta casilla es $N\times N$, tenemos que las filas negras "pierden" una casilla negra y las filas blancas "pierden" una casilla blanca, y tenemos que se "pierde" una fila negra, entonces cada fila queda con $4$ casillas negras y $4$ blancas y quedan $4$ filas de cada tipo, entonces la cantidad de configuraciones de cada color es $4!^2=576$ (contando la primera fila de abajo a arriba, tenemos $4$ posibilidades de colocar la torre, en la segunda fila también son $4$, ya que las casillas de la segunda fila no están en las mismas columnas que las de primera fila, en la tercera fila son $3$ posibilidades, ya que la torre de la primera fila bloque una casilla de la tercera, en la cuarta fila son $3$, la quinta y la sexta fila son $2$, la séptima y la octava fila es $1$), y como hay $25$ casillas $N\times N$, en total tenemos $576\times 2\times 25=28800$ posibilidades (el $\times 2$ es porque el color de las casillas que ocupan las torres puede ser blanco o negro).

Si esta casilla es $B\times N$, tenemos que las filas negras "pierden" una casilla blanca y las filas blancas "pierden" una casilla negra, y se "pierde" una fila negra, entonces quedan $4$ filas negras, con $5$ casillas negras y $3$ blancas, y quedan $4$ filas blancas con $5$ casillas blancas, y $3$ negras. Ahora bien, no podemos colocar las torres en casillas blancas porque al haber $4$ filas negras con $3$ casillas blancas, va a haber una fila negra en la que ya no se pueda poner ninguna torre en una casilla blanca. De la misma manera, no podemos colocar las torres en casillas negras porque al haber $4$ filas blancas con $3$ casillas negras, va a haber una fila blanca en la que ya no se pueda poner ninguna torre en una casilla negra. Por lo tanto no tenemos ninguna posibilidad si la casilla es $B\times N$, y si es $N\times B$ tampoco, ya que al rotar el tablero $90°$, la casilla pasa a ser $B\times N$ y estamos en la misma situación.

Si esta casilla es $B\times B$, tenemos que las filas negras pierden una casilla blanca y las filas blancas pierden una casilla negra, y se pierde una fila blanca, entonces quedan $5$ filas negras, con $5$ casillas negras y $3$ blancas y quedan $3$ filas blancas con $5$ casillas blancas y $3$ negras. Ahora bien, no podemos colocar las torres en casillas blancas ya que al haber $5$ filas negras con $3$ casillas blancas, van a haber dos filas negras donde no pueda ir ninguna torre en una casilla blanca. Sin embargo, sí podemos colocar las torres en las casillas negras, y tenemos $5!3!=720$ posibilidades ($5!=120$ posibilidades para colocar las torres en las filas negras y $3!=6$ posibilidades para colocar las torres en las filas blancas), y como tenemos $16$ casillas $B\times B$, nos quedan $16\times 720=11520$ configuraciones.

Por lo tanto concluimos que en total tenemos $11520+28800=40320$ posibilidades de colocar las torres.
Avatar de Usuario
enigma1234

OFO - Medalla de Oro-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años OFO - Medalla de Plata-OFO 2019 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 OFO - Medalla de Oro-OFO 2024
Mensajes: 211
Registrado: Sab 03 Jun, 2017 8:07 pm
Medallas: 5
Nivel: Exolímpico

Re: OFO 2018 Problema 2

Mensaje sin leer por enigma1234 »

Spoiler: mostrar
Sea $f(n)$ y $g(n)$ la cantidad de formas de colocar n y n-1 torres en un tablero de $n\times n$ respectivamente de tal manera que no se ataquen.

Veamos cuanto es $f(n)$. Al colocar n torres en un tablero de $n\times n$ tal que no se ataquen, es claro que hay exactamente 1 en cada fila y cada columna. Es claro que hay n formas de colocar una torre en la primera fila. Entonces hay n posiciones posibles para de la casilla de la primera columna. "Eliminando" la fila y la columna a la cual pertenece dicha casilla entonces nos queda colocar n-1 torres en un tablero de $(n-1)\times (n-1)$ tal que no se ataquen, es claro que hay exactamente 1 en cada fila y cada columna que se puede hacer de $f(n-1)$ formas.
Por tanto $f(n)=n\times f(n-1)$ y como es claro que $f(1)=1$ entonces tenemos por inducción que $f(n)=n!$

Ahora vemos cuanto es $g(n)$. Supongamos que tenemos n-1 torres en un tablero de $n\times n$ tal que no se ataquen, entonces es claro que si queremos colocar una torre mas esta tendría que estar en la única fila y la única columna en la cual aun no hay una torre, es decir tiene posición única. Entonces supongamos que tenemos un tablero de n torres en un tablero de $n\times n$ tal que no se ataquen hay n formas de quitar una torre con lo cual tendríamos una ordenación de n-1 torres osea una ordenación de $g(n)$ y es claro que no puede haber 2 ordenaciones de $g(n)$ iguales por que de cada ordenación de $g(n)$ de llega a una de $f(n)$ .Por tanto $g(n)=n\times f(n)=n\times n!$.

En el problema supongamos que las casillas de las esquinas están pintadas de negro.
Si todas las torres están en casillas negro entonces separamos las casillas de negro en 2 tableros, uno de $5\times 5 y 4\times 4$ (en el tablero de $5\times 5$ están las casillas que están en una fila impar y en el de $4\times 4$ las que están en fila par) es claro que se atacan en los nuevos tableros si y solo si se atacan en el anterior.
Entonces debemos colocar 8 torres entre dichos tableros tal que no se ataquen. Entonces como en un tablero de $n\times n$ se pueden colocar máximo n torres (dado que sino hay al menos 2 torres en alguna una fila por palomar y esas 2 se atacan) solo podemos colocar 5 torres en primer tablero y 3 en el segundo o 4 en ambos, entonces aquí hay $f(5)\times g(4) +g(5)\times f(4)=25920$.

Ahora supongamos que todas las torres están en las casillas blancas.Separamos las casillas como en el caso anterior y nos quedan 2 tableros de $5\times 4$ dado que un lado es 4 entonces en cada uno hay maximo 4 torres tal que no se ataquen. Entonces como debemos poner 4 torres en cada tablero, veamos que pasa con uno. como tienen 5 columnas va a haber una sin casillas esta tiene 5 posibilidades y las torres deben ir en el tablero de $4\times 4$ restante. Entonces en este tablero hay $5\times f(4)=120$ entonces en este caso en total hay $120\times 120=14400$.

Por lo tanto en total hay 25920+14400=40320 formas de hacer esto.
Responder