Entrenamiento Cono 2018 P24

Matías

OFO - Medalla de Bronce FOFO Pascua 2017 - Medalla OFO - Medalla de Plata
Mensajes: 157
Registrado: Mar 06 Oct, 2015 7:59 pm
Medallas: 4
Nivel: 2

Entrenamiento Cono 2018 P24

Mensaje sin leer por Matías » Sab 11 Ago, 2018 4:57 pm

Llamamos a un tablero de $1\times k$ guayaco sí cumple las siguientes condiciones:
i. Cada una de las casillas del tablero es pintada con exactamente uno de $k$ colores disponibles.
ii. Si el $dcm(i,k)>1$, entonces la $i$-ésima casilla comparte color con la $(i-1)$-ésima casilla.
iii. Si el $dcm(i,k)=1$, entonces la $i$-ésima casilla comparte color con la $(k-i)$-ésima casilla.
Sebastián escoge un entero positivo $a$ y calcula la cantidad de tableros de $1\times a$ que son guayacos. Luego de esto, David escoge un entero positivo $b$ y calcula la cantidad de tableros de $1\times b$ que son guayacos. David gana si ambos calcularon la misma cantidad de tableros, caso contrario Sebastián gana. Hallar todas las parejas $(a,b)$ para las cuales David gana.

Matías

OFO - Medalla de Bronce FOFO Pascua 2017 - Medalla OFO - Medalla de Plata
Mensajes: 157
Registrado: Mar 06 Oct, 2015 7:59 pm
Medallas: 4
Nivel: 2

Re: Entrenamiento Cono 2018 P24

Mensaje sin leer por Matías » Mié 03 Oct, 2018 9:00 pm

Spoiler: mostrar
Veamos que la cantidad de tableros de $1\times k$ guayacos es $1$ si $k=1$, $2$ si $k=2$, o $k^{\frac{\phi(k)}{2}}$ si $k\geq 3$ (siendo $\phi(k)$ la función phi de Euler, la cantidad de números naturales coprimos con $k$ y menores a $k$).

Si $k=1$ tenemos que la única opción es pintar a la $1$-ésima casilla con el único color disponible, entonces hay un solo tablero.
Si $k=2$, como $dcm(2,2)=2>1$ entonces la $2$-ésima casilla comparte color con la $1$-ésima casilla, y tenemos $2$ colores disponibles, así que hay $2$ tableros.
Si $k\geq 3$, tenemos que si un número $i$ no es coprimo con $k$ ($dcm(i,k)>1$) la $i$-ésima casilla comparte color con la $(i-1)$-ésima casilla, y esta, en caso de ser $dcm(i-1,k)>1$, va a compartir color con la $(i-2)$-ésima casilla, y así siguiendo, entonces la $i$-ésima casilla va a compartir color con la $j$-ésima casilla, siendo $j$ el mayor número coprimo con $k$ y menor a $i$.
Notemos que, en caso de ser $k$ par, va a ser $dcm(k,\frac{k}{2})=\frac{k}{2}>1$ (ya que $k\geq 3$).
También tenemos que si $dcm(i,k)=1$ e $i>\frac{k}{2}$ entonces la $i$-ésima casilla comparte color con la $k-i$-ésima casilla (tenemos que $dcm(k-i,k)=1$ y $k-i<\frac{k}{2}$).
Por lo tanto, tenemos que la coloración del tablero depende únicamente de las coloraciones de las casillas cuyos números son coprimos a $k$ y menores a $\frac{k}{2}$ (las cuales son independientes entre sí), es decir, si coloreamos a todas esas casillas implicamos las coloraciones de las demás casillas del tablero.
Ahora bien, la cantidad de números coprimos a $k$ y menores a $\frac{k}{2}$ es la mitad de la cantidad de números coprimos a $k$ y menores a $k$ (o sea, $\phi(k)$) (ya que $dcm(i,k)=1\Leftrightarrow dcm(k-i,i)=1$). Por lo tanto la cantidad de tableros guayacos es $k^{\frac{\phi(k)}{2}}$ (ya que tenemos $k$ colores disponibles).

Para todo número natural $n>1$ tenemos que si su factorización en primos es $n=\prod_{i=1}^{m} p_i^{\alpha_i}$ entonces $\phi(n)=\prod_{i=1}^{m} (p_i-1)p_i^{\alpha_i-1}$. (Ver https://omaforos.com.ar/viewtopic.php?f ... uler#p6391).

Tenemos que con toda pareja $(a,a)$ va a ganar David. En caso de que $a\neq b$, si $k\geq 3$ tenemos que $k^{\frac{\phi(k)}{2}}\geq k\geq 3>2$, por lo tanto $a,b\geq 3$.
Supongamos que existen dos números $a$ y $b$ ($a\neq b$, $a,b\geq 3$) tales que $a^{\frac{\phi(a)}{2}}=b^{\frac{\phi(b)}{2}}$. Luego, tenemos que $a$ y $b$ tienen exactamente los mismos factores primos $p_1$, $p_2$, $\ldots$, $p_n$, así que $a=\prod_{i=1}^{n} p_i^{\alpha_i}$ y $b=\prod_{i=1}^{n} p_i^{\beta_i}$.
Entonces tenemos que
$a^{\frac{\phi(a)}{2}}=b^{\frac{\phi(b)}{2}}$
$a^{\phi(a)}=b^{\phi(b)}$
$a^{\prod_{i=1}^{n} (p_i-1)p_i^{\alpha_i-1}}=b^{\prod_{i=1}^{n} (p_i-1)p_i^{\beta_i-1}}$
$a^{\prod_{i=1}^{n} p_i^{\alpha_i-1}}=b^{\prod_{i=1}^{n} p_i^{\beta_i-1}}$
$a^{\prod_{i=1}^{n} p_i^{\alpha_i}}=b^{\prod_{i=1}^{n} p_i^{\beta_i}}$
$a^a=b^b$
$a=b$ (absurdo)

Por lo tanto concluimos que las parejas para las cuales David gana son $(a,a)$ $\forall a\in N$.

Responder