Zonal 2022 - N3 P3

[Gianni De Rico]

Alex y Bea, cada uno por su cuenta, marcaron las casillas de un tablero de $21$ filas y $37$ columnas con los números enteros desde $1$ hasta $777$, escribiendo un número en cada casilla, comenzando en la esquina superior izquierda.
Alex escribió en la primera fila los números $1,2,3,\ldots ,37$, en la segunda fila escribió $38,39,\ldots ,74$ y así siguiendo completó las $21$ filas.
Bea escribió en la primera columna los números $1,2,3,\ldots ,21$, en la segunda columna escribió $22,23,\ldots ,42$ y así siguiendo completó las $37$ columnas.
Hubo unas pocas casillas en las que las dos numeraciones coincidieron, por ejemplo en la primera fila de la primera columna ambas tienen $1$ y en la última fila de la última columna ambas tienen $777$.
Determinar las casillas en las que coincidieron las dos numeraciones en indicar en cada caso cuál es el número escrito.

[RamiroS]

Spoiler: mostrar

Lo que yo hice es lo siguiente:
-En contrar dos formulas, una para Alex y una para Bea que dado un casillero MxN (siendo m la columna y n la fila), de como resultado el numero que se encuentra en ese casillero.
-Para Alex:
$(n-1)\cdot 37+m$
Esta formula sive ya que $(n-1)\cdot 37$ lo que hace es contar todos los numeros que ya escribimos en las filas anteriores, por eso esta multiplicado por 37; y por otra parte el $+m$ es para que sume los numeros que ya pasamos dentro de la misma fila.
-Para Bea:
$(m-1)\cdot 21+n$
La explicacion de porque la formula funciona es casi igual a la de alex, solo que las filas cambia por las columnas, y cambia el $37$ por $21$ ya que hay 21 filas.

-Si en una posicion Alex y Bea tienen el mismo numero lo que podemos hacer es igualar las fórmulas

$(n-1)\cdot 37+m = (m-1)\cdot 21+n$
$37n-37+m=21m-21+n$
$36n=20m+16$
$9n=5m+4$ (Acá dividi ambos lados entre 4)
$\frac{9n-4}{5} =m$ (Despejo m)

-Armo una tabla con esta ecuacion:

$\frac{9n-4}{5}$ | $m$
n=1$ \Rightarrow $ m=1
n=2 $ \Rightarrow $ m=2,8
n=3 $ \Rightarrow $m=4,6
n=4 $ \Rightarrow $m=6,4
n=5 $ \Rightarrow $m=8,2
n=6 $ \Rightarrow $ m=10
n=7$ \Rightarrow $ m=11,8
n=8 $ \Rightarrow $m=13,6
n=9 $ \Rightarrow $m=15,4
n=10 $ \Rightarrow $m=17,2
n=11$ \Rightarrow $ m=19
n=12$ \Rightarrow $ m=20,8
n=13$ \Rightarrow $ m=22,6
n=14$ \Rightarrow $ m=24,4
n=15$ \Rightarrow $m=26,2
n=16$ \Rightarrow $ m=28
n=17$ \Rightarrow $m=29,8
n=18$ \Rightarrow $ m=31,6
n=19$ \Rightarrow $ m=33,4
n=20$ \Rightarrow $ m=35,2
n=21$ \Rightarrow $ m=37

Los valores que sirven son los que tanto m como n son enteros por los que las casillas que coinciden son las siguientes:
(m;n) , (1;1) , (10;6) , (19;11) , (28;16) , (37;21)
Y si calculan con las formulas del principio los numeros de cada casillero son:
1 ; 195 ; 389 ; 583 ; 777

[FabriATK]

Spoiler: mostrar

$\frac{9n-4}{5}$ | $m$
n=1$ \Rightarrow $ m=1
n=2 $ \Rightarrow $ m=2,8
n=3 $ \Rightarrow $m=4,6
n=4 $ \Rightarrow $m=6,4
n=5 $ \Rightarrow $m=8,2
n=6 $ \Rightarrow $ m=10
n=7$ \Rightarrow $ m=11,8
n=8 $ \Rightarrow $m=13,6
n=9 $ \Rightarrow $m=15,4
n=10 $ \Rightarrow $m=17,2
n=11$ \Rightarrow $ m=19
n=12$ \Rightarrow $ m=20,8
n=13$ \Rightarrow $ m=22,6
n=14$ \Rightarrow $ m=24,4
n=15$ \Rightarrow $m=26,2
n=16$ \Rightarrow $ m=28
n=17$ \Rightarrow $m=29,8
n=18$ \Rightarrow $ m=31,6
n=19$ \Rightarrow $ m=33,4
n=20$ \Rightarrow $ m=35,2
n=21$ \Rightarrow $ m=37

Te podías ahorrar varios de esos cálculos:

Spoiler: mostrar

Cómo $\frac{9n-4}{5} = m$ y $m$ es entero tenés que $5\mid 9n-4 \Rightarrow 9n - 4 \equiv 0 \pmod{5} \Rightarrow -n \equiv 4\pmod{5} \Rightarrow n \equiv 1\pmod{5}$
Entonces solo tenés que mirar los $n = 5k+1$

[Renzo Gemma]

Spoiler: mostrar

Primero fabriqué 2 ecuaciones, respecto de Alex y Bea para hallar un número $Z$ respecto a la columna y fila en cada caso.
Para A hallé que $Z= 21(n-1)+p$ siendo $n$ el número de fila y $p$ el de columna.
Analogamente para B tenemos $Z=(m-1)37+w$ con $m$ el de columna y $w$ siendo el numero de fila.

Veamos que la "coincidencia" de la cual habla el problema es que para una misma fila y columna de cada caso tenemos el mismo número. Luego $p=m$ y $w=n$
Como tiene que dar el mismo número, igualamos:

$(m-1)37+n=(n-1)21+m$
Desarrollando y simplificando llegamos a algo como

$9m-5n=4$

Obtuvimos una ecuación diofántica, resta parametrizar $m$ y $n$ respecto a un $k$ entero.

Por identidad de Bezoút sabemos que si $mcd(a,b)=d$ entonces existen enteros $x,y$ tales que $ax+by=d$ y la forma de la solución está dada de la siguiente forma:
$x=x_0+ \frac{b}{d} k$
$y=y_0+ \frac{a}{d} k$

Esta es un herramienta sorpresa que nos ayudará mas tarde

Aplicando al problema tenemos que $mcd(9,5)=1$
Por lo que $9x+5y=1$

Intuitivamente podemos hallar los iniciales $x,y$ que satisfacen

$9(-1)+5(2)=1$

Por lo que la solución deberá estar dada del siguiente modo:

$x=-1+5k$
$y=2-9k$

(en cuanto si en los cálculos, a la hora de resolver y comprobar estas conclusiones, se halla un parámetro $-k$ o $k$ hay que tener en claro que son técnicamente lo mismo porque $k$ es una variable entera y es posible hacer cambios de variables del tipo $-k=q$ o similares)
Edit:

Spoiler: mostrar

Para poder hallar el caso que nos importa a nosotros (no la base de la identidad de Bezoút) debemos aplicar unas fórmulas muy parecidas.
Para $ax+by=c$ se sabe que $x,y$ deben estar dadas de la siguiente forma:

$x=x_0c'+ \frac{b}{d} k$
$y=y_0c'+ \frac{a}{d} k$

Con $c'=\frac{c}{d}$

Veamos que es exactamente la misma fórmula solo que le multiplicamos por $c'$ que es lo que le falta a $d$ para que sea la constante de nuestra ecuación, solo que en lugar de amplificar a toda la expresión lo hacemos en $x_0,y_0$ debido a que la parte parametrizada, al siempre terminarse simplificando al reemplazar, puede ser cuán pequeño queramos, que es lo que nos sirve para ir encontrando todas y cada una de las soluciones

Ahora para pasar de $9x+5y=1$ a $9m-5n=4$ (que podría reescribirse "$9m+5(-n)=4$")hay que reemplazar en las formulitas que detallé antes.

Luego
$m=-4+5k$
$-n=8-9k$

Ahora solo toca ir "jugando" con $k$ para hallar todos los pares de solución. Aunque como creo que hemos llegado de forma analítica hasta acá mejor rematemos de forma analítica

$1≤m≤21$
$1≤n≤37$

$1≤-4+5k≤21$
$1≤-8+9k≤37$

$1≤k≤5$
$1≤k≤5$

$k={1,2,3,4,5}$ son soluciones

$(m,n,z)=(1,1,1);(6,10,195);(11,19,389),(16,28,583),(21,37,777)$

[Villarg]

Podemos realizar un camino mucho más sencillo y corto que en las otras resoluciones:

Spoiler: mostrar

Anoten las primeras 3 columnas, en total son 63 casillas. Eso para estar seguros, matemáticamente con las primeras dos alcanza.
Anoten tanto los números de Alex como de Bea. Resten los valores de los números de Bea menos los de Alex para cada casilla.
Siguiendo cada fila de izquierda a derecha, van a tener cada resultado. Si toman un número D como la diferencia entre B (valores de Bea) - A (valores de Alex), de modo que B - A = D Van a encontrar un patrón: de izquierda a derecha los números crecen de a veinte.

Entonces, con los valores de cada fila de las dos o tres columnas anotadas, fíjense aquellas cuyo valor de D en módulo sea múltiplo de veinte.
Todas las filas que lo cumplan van a tener solo UN valor, ya que solo las casillas de diferencia 0 nos servirán (pues son los casos A = B).

Así, van a encontrar que son 5 casos, incluyendo la primera casilla y la última. A partir de ahí, solo completen la fila hasta llegar a la correcta.

Es más rápido e igual de correcto. Saludos.

[drynshock]

HEAR ME OUT:

Spoiler: mostrar

Lo primero que tenemos que encontrar es la formula del numero de cada casilla:

Para Alex)
El numero de columna mas 37 por la fila: $C + 37(F-1)$ restamos 1 ya que la Fila empieza en 1 pero los múltiplos de 37 recién en la segunda.

Spoiler: mostrar

Si no logran entenderlo piénsenlo así: Cuando se llega a la ultima casilla de una fila pasaron 37 números, entonces la próxima casilla, la cual empieza una fila mas abajo, va a ser un múltiplo de 37 +1, luego +2, +3... y así dependiendo del numero de columna.

Para Bea)
Lo mismo pero con el pensamiento sobre las filas: $F + 21(C-1)$

Como queremos que el numero coincida en ambas debemos igualar ambas funciones:
$F + 21(C-1) = C + 37(F-1)$
$F + 21C-21 = C + 37F-37$
$20C+4 = 36F$
$16 = 36F - 20C$

$4 = 9F - 5C$

Ahora como se resuelve esto?
Se llama ecuación diofántica lineal y tenemos que seguir el siguiente procedimiento:

Primero encontramos una solución, la cual ya nos la da el enunciado: (F,C) = (1,1)

Ahora reescribimos esa solución de la siguiente manera:
(F,C) = (1 + a.k, 1 -b.k)

"a" va a tomar el valor del coeficiente de C
"b" va a tomar el valor del coeficiente de F

(F,C) = (1 + 5k, 1 +9k)

Ahora F y C van a estar determinados por K, así que con esto ya tenemos todas las soluciones.

Spoiler: mostrar

Esto funciona ya que al desarrollar F y C en la ecuación, los valores de K se cancelan:
$4 = 9F - 5C$
$4 = 9(1+5k) - 5(1+9k)$
$4 = 9+45k - 5-45k$
$4 = 9-5$
$4 = 4$
Por lo que para cualquier K esto cumple.

Si nos ponemos a ver los valores de k vemos que pueden ser 0, 1, 2, 3, 4 y hasta ahí para no pasarse, entonces las soluciones completas serian:
(F, C) = {(1, 1) ; (6, 10) ; (11, 19) ; (16, 28) ; (21, 37)}