FOFO de Pascua 2024 Problema 3

Problemas que aparecen en el Archivo de Enunciados.
Felibauk

COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Bronce-OFO 2020 COFFEE - Mención-COFFEE Carolina González COFFEE - Mención-COFFEE Ariel Zylber COFFEE - Mención-COFFEE Iván Sadofschi
FOFO 10 años - Medalla-FOFO 10 años OFO - Medalla de Plata-OFO 2021 OFO - Medalla de Oro-OFO 2022 FOFO Pascua 2022 - Medalla-FOFO Pascua 2022 OFO - Medalla de Oro-OFO 2023
FOFO 13 años - Medalla-FOFO 13 años OFO - Oro perfecto-OFO 2024 FOFO Pascua 2024 - Jurado-FOFO Pascua 2024
Mensajes: 73
Registrado: Dom 19 Ene, 2020 12:43 am
Medallas: 13
Nivel: 1

FOFO de Pascua 2024 Problema 3

Mensaje sin leer por Felibauk »

Sea $n\geq 2$ un entero. En un tablero de $n\times n$ hay $n$ torres distribuidas de modo que ninguna torre ataca a otra. En un determinado momento, todas las torres se mueven al mismo tiempo a una casilla adyacente (que comparte un lado) a la casilla en la que se encuentra. Determinar todos los $n$ tales que es posible colocar las torres de modo que luego del movimiento ninguna torre ataque a otra.
1  
"La matemática es para pensar. El fútbol es para sacar mi instinto animal y decirle al árbitro hdp te voy a m4t4r." Anónimo
Felibauk

COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Bronce-OFO 2020 COFFEE - Mención-COFFEE Carolina González COFFEE - Mención-COFFEE Ariel Zylber COFFEE - Mención-COFFEE Iván Sadofschi
FOFO 10 años - Medalla-FOFO 10 años OFO - Medalla de Plata-OFO 2021 OFO - Medalla de Oro-OFO 2022 FOFO Pascua 2022 - Medalla-FOFO Pascua 2022 OFO - Medalla de Oro-OFO 2023
FOFO 13 años - Medalla-FOFO 13 años OFO - Oro perfecto-OFO 2024 FOFO Pascua 2024 - Jurado-FOFO Pascua 2024
Mensajes: 73
Registrado: Dom 19 Ene, 2020 12:43 am
Medallas: 13
Nivel: 1

Re: FOFO de Pascua 2024 Problema 3

Mensaje sin leer por Felibauk »

Solución oficial:
Spoiler: mostrar
Como las $n$ torres no se atacan, cualesquiera dos de ellas no comparten ni fila, ni columna. Como hay exactamente $n$ filas y $n$ columnas, concluimos que habrá exactamente una torre por columna y por fila.

Digamos que una torre se mueve de la columna $i$ a la $i-1$ (numeradas de izquierda a derecha). Notemos luego que la torre que inicialmente se encuentra en la columna $i-1$ no puede cambiar de fila puesto que, luego de los movimientos, habría dos torres en la fila $i-1$, absurdo. Si se mueve a la columna $i-2$, entonces podemos fijarnos en la cantidad de torres que terminan en alguna columna desde la $1$ hasta la $i-1$. Sabemos que esta cantidad será exactamente $i$, dado que toda torre en la columna $i-x$, con $x \geq 2$, puede llegar a lo sumo a la columna $i-x+1 \leq i-1$, y además, las que inicialmente se hallaban en las columnas $i-1$ e $i$, luego de sus movidas quedaron entre las primeras $i-1$ columnas. No obstante, como en $i-1$ columnas se hallan $i$ torres, podemos concluir por Palomar que habrá al menos dos de ellas que comparten columna, que se están atacando, absurdo. El procedimiento para cualquier otro movimiento posible es análogo por simetría.

De este modo, es posible afirmar que si una torre en la columna $i$ se mueve a la $i-1$, luego la torre en la columna $i-1$ se mueve a la $i$. Por ende, podemos considerar las parejas de piezas que "intercambian" de línea (fila o columna). No hay una torre en dos parejas distintas y cualquiera de ellas debe pertenecer a alguna pareja, por lo tanto, se sigue que la cantidad de torres debe ser el doble de la cantidad de parejas, es decir que $n=2k$, para algún $k$ natural.

Si $n=2k$, en efecto es posible lograr lo buscado: ubicamos las torres en las casillas de fila $j$ y columna $j, \ 1 \leq j \leq 2k$. Las torres en filas $2m-1$ las movemos a las filas $2m$ y viceversa, $1 \leq m \leq n$, por lo que sigue habiendo una torre por cada columna y cada fila pierda una y gana otra, cumpliendo con la condición del enunciado.

RTA: los $n$ para los cuales es posible son todos los pares.
Última edición por Felibauk el Sab 20 Abr, 2024 8:39 pm, editado 1 vez en total.
"La matemática es para pensar. El fútbol es para sacar mi instinto animal y decirle al árbitro hdp te voy a m4t4r." Anónimo
Avatar de Usuario
BR1

OFO - Medalla de Bronce-OFO 2024 FOFO Pascua 2024 - Medalla-FOFO Pascua 2024
Mensajes: 414
Registrado: Sab 28 Oct, 2023 1:33 pm
Medallas: 2
Nivel: 1

Re: FOFO de Pascua 2024 Problema 3

Mensaje sin leer por BR1 »

Mi solución al problema $3$
FOFO2024P3.pdf
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
ACLARACIÓN: $1$ no es primo
Avatar de Usuario
drynshock

FOFO 13 años - Mención-FOFO 13 años OFO - Medalla de Bronce-OFO 2024 FOFO Pascua 2024 - Copa-FOFO Pascua 2024
Mensajes: 738
Registrado: Sab 21 May, 2022 12:41 pm
Medallas: 3
Nivel: 3
Contactar:

Re: FOFO de Pascua 2024 Problema 3

Mensaje sin leer por drynshock »

Spoiler: mostrar
Introducción
Para empezar voy a hacer una pequeña mención al diccionario del problema. Cuando hablo de "distribución valida" me refiero a una distribución de torres de tal manera que no se ataquen entre ellas. Luego, cuando digo "movimiento valido" o "jugada valida" me refiero a cambiar de una "distribución valida" a otra moviendo cada torre exactamente una casilla (como menciona el problema).

Primero veamos el caso de $n = 2$

$
\begin{array}{| c | c |}
\hline
O & \\ \hline
& O \\ \hline
\end{array}
$

Y mediante una jugada valida podemos llegar a.

$
\begin{array}{| c | c |}
\hline
& O \\ \hline
O & \\ \hline
\end{array}
$

Lo cual se puede generalizar para cualquier $n = 2k, k \in \mathbb Z^+$ de la siguiente manera:


Caso $n = 2k$

$
\begin{array}{| c | c | c | c | c | c | c |}
\hline
O&&&& \dotsb \\ \hline
&O&&& \dotsb \\ \hline
&&O&& \dotsb \\ \hline
&&&O& \dotsb \\ \hline
\vdots & \vdots & \vdots & \vdots & \ddots \\ \hline
&&&&&O& \\ \hline
&&&&&&O \\ \hline
\end{array}
$

Y de la misma manera que hicimos con $n = 2$ podemos trabajar en tableritos de $2$x$2$ para hacer una jugada valida.

$
\begin{array}{| c | c | c | c | c | c | c |}
\hline
&O&&& \dotsb \\ \hline
O&&&& \dotsb \\ \hline
&&&O& \dotsb \\ \hline
&&O&& \dotsb \\ \hline
\vdots & \vdots & \vdots & \vdots & \ddots \\ \hline
&&&&&&O \\ \hline
&&&&&O& \\ \hline
\end{array}
$

$\blacksquare$

¿$n$ impar?

Ahora analicemos el caso de los impares. Para eso pongamos como ejemplo $n = 3$ y numeremos las casillas del 1 al 9 como se ve en la tabla:

$
\begin{array}{| c | c | c |}
\hline
1 & 2 & 3 \\ \hline
4 & 5 & 6 \\ \hline
7 & 8 & 9 \\ \hline
\end{array}
$

Notemos que la siguiente distribución es valida y la suma de sus casillas es 15.

$
\begin{array}{| c | c | c |}
\hline
1 & 2 & O \\ \hline
4 & O & 6 \\ \hline
O & 8 & 9 \\ \hline
\end{array}
$

Esta es otra distribución y su suma también da 15.

$
\begin{array}{| c | c | c |}
\hline
1 & O & 3 \\ \hline
4 & 5 & O \\ \hline
O & 8 & 9 \\ \hline
\end{array}
$

En general parece que la suma es invariante, sin embargo debemos demostrarlo primero. Para eso veremos que para cada combinación de distribuciones validas, siempre podemos hacer una transformación a una distribución con todas sus torres ubicadas en alguna diagonal sin variar la suma.

La suma es invariante
Demostración:
Consideremos el tablero:

$
\begin{array}{| c | c | c | c | c | c |}
\hline
(x, y) &1&2&3&4& \dotsb & n \\ \hline
1&1&2&3&4& \dotsb & n \\ \hline
2&n+1&n+2&n+3&n+4& \dotsb & 2n \\ \hline
3&2n+1&2n+2&2n+3&2n+4& \dotsb & 3n \\ \hline
4&3n+1&3n+2&3n+3&3n+4& \dotsb & 4n \\ \hline
&\vdots & \vdots & \vdots & \vdots & \ddots \\ \hline
n&n(n-1)+1&n(n-1)+2&n(n-1)+2&n(n-1)&&n^2 \\ \hline
\end{array}
$

Digamos que una torre ocupa la posición $(a, b)$ y sin perdida de generalidad digamos que $a > b$. Si desplazamos $(a, b) = x \rightarrow (b, b) = y$ la suma disminuye en $a-b = x-y$ unidades. Sin embargo la torre que desplazamos ahora se ve amenazada por la torre que estaba en su misma columna $(b, b')$, la cual la podemos desplazar por su misma fila $a-b$ unidades hacia la derecha, por lo cual terminamos en la casilla $(a, b')$ y por lo tanto tenemos la misma suma pero con un elemento mas en la diagonal.

En resumen, la torre que esta en $(a, b) \rightarrow (b, b)$ desplazándose $|a-b|$ unidades, y esta torre la cual amenaza a otra torre en $(b, b') \rightarrow (a, b')$ desplazándose $|a-b|$ unidades.

Repitiendo este proceso podemos terminar con todas las torres en la diagonal, lo cual implica que la suma es invariante ya que la suma de la diagonal es fija.

Visualmente:

$
\begin{array}{| c | c | c | c | }
\hline
&& \dotsb \\ \hline
&(b, b') \rightarrow & \dotsb & (a, b') \\ \hline
& \vdots & & \vdots \\ \hline
&(b, b) & \dotsb & \leftarrow (a, b) \\ \hline
& & \vdots & & \\ \hline
\end{array}
$

$\blacksquare$

$n$ no puede ser impar
Ahora que sabemos que la suma es invariante, demostremos por contradicción que $n \neq 2k + 1, k \in \mathbb Z^+$. Por contraposición, digamos que $n = 2k + 1$.

$
\begin{array}{| c | c | c | c | c | c |}
\hline
1&2&3&4& \dotsb & n \\ \hline
n+1&n+2&n+3&n+4& \dotsb & 2n \\ \hline
2n+1&2n+2&2n+3&2n+4& \dotsb & 3n \\ \hline
3n+1&3n+2&3n+3&3n+4& \dotsb & 4n \\ \hline
\vdots & \vdots & \vdots & \vdots & \ddots \\ \hline
n(n-1)+1&n(n-1)+2&n(n-1)+2&n(n-1)&&n^2 \\ \hline
\end{array}
$

Notemos que no importa donde pongamos la primera ficha, luego de una jugada valida el numero de casilla cambia de paridad. La demostración es bastante simple ya que para moverse a la casilla de la izquierda debemos restar $1$, para moverse a la de la derecha debemos sumar $1$, para moverse hacia arriba debemos restar $n$ (el cual es impar), y para moverse hacia abajo hay que sumar $n$.

Entonces, una jugada valida implica que el numero de la casilla de cada torre varia en $2m - 1$ unidades ($m \in \mathbb Z)$.

Siguiendo, digamos que $S(n) = C_1 + C_2 + ... + C_n$, donde $S(n)$ es la suma total y $C_i$ es el numero de la casilla donde esta cada torre. Entonces luego de una jugada valida obtenemos que: $S(n) = (C_1 + V_1) + (C_2 + V_2) + ... + (C_n + V_n)$ donde $V_i$ representa la variación del numero de la casilla donde estaba la torre $i$ (recordemos que $V_i = 2m_i + 1$).
Simplificando obtenemos que $V_1 + V_2 + ... + V_n = 0 \Rightarrow (2m_1+1) + (2m_2+1) + ... + (2m_n+1) = 0$.

Notemos que al ser $n$ impar, entonces:
$\underbrace{(2m_1+1) + (2m_2+1) + ... + (2m_n+1)}_{2k+1} = 0 \therefore$
$2(m_1 + m_2 + ... + m_n) + 1(2k+1) \equiv 0 (mod 2) \Rightarrow 1 \equiv 0 (mod 2)$
$\Rightarrow \Leftarrow$

Entonces llegamos a un absurdo que se da al suponer que $n = 2k+1 \therefore n \neq 2k + 1$. Concluimos entonces que todos los $n$ que cumplen son de la forma:
$n = 2k, k \in \mathbb Z^+$
$\blacksquare$
@Bauti.md ig
First place is winning, anything else is losing.
"Alexandra Trusova"
Avatar de Usuario
magnus

OFO - Mención-OFO 2024 FOFO Pascua 2024 - Mención-FOFO Pascua 2024
Mensajes: 101
Registrado: Sab 12 Nov, 2022 5:50 pm
Medallas: 2
Nivel: 2

Re: FOFO de Pascua 2024 Problema 3

Mensaje sin leer por magnus »

Spoiler: mostrar
Para el caso de $n$ par se puede hacer lo que dijo drynshock arriba.

Mi demostración que con $n$ impar no se puede:
Tenemos que solo puede haber una torre por columna o fila. Como el tablero es de $n\times n$ hay $n$ filas y $n$ columnas entonces tenemos que como hay $n$ torres va a haber una por fila y una por columna.

Digamos que para $n>1$ al lado de cada columna y cada fila tenemos un contador que nos va diciendo cuantas torres hay respectivamente. Si lo escribimos en un conjunto al comenzar se vería algo así: $F={1;1;\dots ;1;1}, C={1;1;\dots;1;1}$.
$Aclaración:$ los elementos del conjunto estan en orden, es decir, que el primer elemento del conjunto representa a la cantidad de torres en la fila o columna $1$, el segundo elemento representa a la cantidad de torres en la fila o columa $2$ y así hasta el enésimo elemento que representa la cantidad de torres en la fila o columna $n$

Supongamos que empezamos moviendo una torre de fila (que como el tablero es de $n\times n$ es indiferente las filas de las columnas porque podemos rotar el tablero y las columnas pasan a ser filas las filas pasan a ser columnas). Llamo a las filas como $f_1,f_2, \dots ,f_n$ y a las torres como $t_1,1_2, \dots, t_n$.

Digamos que tenemos una torre cualquiera $t_k$ en la fila $f_k$ y muevo la torre $t_k$ a la fila $f_{k+1}$. Así nos queda un conjunto $F$ tal que así: $F={1;1;\dots;0;2;\dots;1;1}$. Así en la fila $f_{k+1}$ están las torres $t_k$ y $t_{k+1}$ y la torre $t_k$ ya queda fija ahí porque ya se movió. La torre $t_{k+1}$ va a tener que moverse de fila, porque si se mueve de columna se va a quedar en la misma fila, que como ya hay otra torre en esa fila no es posible. Entonces la torre $t_{k+1}$ va a tener que moverse a la fila $f_{k}$ o $f_{k+2}$.

Supongamos que la torre $t_{k+1}$ se mueve a la fila $f_{k+2}$. Así nos queda la fila $f_{k+2}$ con la torre $t_{k+1}$ que ya queda fija ahí y la $t_{k+2}$ que debe moverse. La torre $t_{k+2}$ como ya desarrollamos debe moverse de fila, como en la fila $f_{k+1}$ ya está la torre $f_k$ fija entonces $t_{k+2}$ deberá moverse a la fila $f_{k+3}$.
Y así, la torre $t_{k+4}$ deberá moverse a la fila $f_{k+5}$, la torre $t_{k+5}$ deberá moverse a la fila $f_{k+6}$ y así. Entonces la torre $t_{n-1}$ deberá moverse a la fila $f_{n}$. Pero en ese fila ya está la torre $t_n$ y no puede moverse a la fila $f_{n-1}$ ya que ahí ya está fija la torre $t_{n-2}$. Entonces la torre $t_{k+1}$ deberá moverse a la fila $t_k$. Así por cada torre que se mueva a una casilla adyacente, la torre que a se encuentra en esa casilla deberá moverse a la casilla de la torre anterior. Entonces en cada fila la cantidad de movimientos será $2x$ para $x$ cantidad de pares de torres que "intercambian entre sí su lugar".

Como el mismo análisis aplica para las columnas por lo ya dicho en las columnas se harán $2y$ para $y$ cantidad de pares de torres que "intercambian entre sí su lugar".

Así $n=2x+2y\Rightarrow n=2(x+y) \Rightarrow 2|n$ entonces $n$ no puede ser impar.


1  
estudiar es temporal, la play es ETERNA
Responder