Pablo debe elegir nueve números enteros positivos distintos y colocarlos uno en cada casilla de un tablero de $3\times 3$ de manera tal que si dos números están en casillas vecinas entonces uno de ellos es divisor del otro. Determinar el mínimo valor posible del mayor de los nueve números que puede elegir Pablo.
Aclaración: Dos casillas son vecinas si tienen un lado en común.
Sea [math]M el mayor de los nueve números. Entonces como es el más grande, sus casillas adyacentes tienen que dividir a [math]M.Ahora notemos que como son todos los números distintos entonces [math]M\geq 9.
-Si M=9: Notemos que están todos los números del uno al nueve. Luego el siete está en el tablero y entonces va a tener por lo menos dos casillas adyacentes que van a poder valer uno o algún múltiplo de siete, pero como estos no hay ninguno, se llega a una contradicción entonces no es posible dicha configuración.(Esta forma de descartar que el siete no puede estar no la voy a mencionar de nuevo ya que la voy a repetir varias veces y en ese caso voy a decir: "por [math]\bigstar")
-Si M=10: Notemos que por [math]\bigstar el siete no puede estar. Entonces están todos los números del uno al diez excluyendo al siete. Como está el cinco, éste debe estar en una esquina ya que si estuviera en otra posición, tendría por lo menos tres casillas adyacentes y como sólo puede estar al lado del uno o del diez, llegaríamos a una contradicción. Luego el diez va a tener dos casillas adyacentes vacías, y como ya usamos al uno y al cinco, no tenemos con que números completar y resulta imposible la configuración.(Esta forma de descartar al cinco la vamos a nombrar [math]\triangle)
-Si M=11: Como once es primo, el único divisor distinto de once es uno, y como el once tiene por lo menos dos casillas adyacentes vacías, debería tener por los menos dos divisores distintos de once, contradicción. Entonces no existe dicha configuración.
-Si M=12: El siete no puede estar por [math]\bigstar(lo mismo ocurre con el número once). Por [math]\triangle el cinco no puede estar. Luego están todos los números del uno al doce menos el cinco, el siete y el once. Como el diez tiene dos posibles divisores (uno y dos), debe estar en una esquina con uno y dos adyacentes a su lado. Luego como los únicos divisores distintos de nueve son uno y tres, nueve debe estar en una esquina y debe compartir al uno con el diez. Quedaría algo así:
X|3|9
X|X|1
X|2|10
Luego como el doce y el seis son los únicos que puede estar adyacentes al tres tenemos dos casos:
-->Si el doce está en el centro, el seis iría a la esquina y sería adyacente al cuatro o al ocho. Contradicción
-->Si el doce está en la esquina, el seis iría al centro y sería adyacente al cuatro o al ocho. Contradicción
-Si M=13: Al ser primo es igual al caso [math]M=11
-Si M=14: Ni el cinco, ni el once, ni el trece pueden estar por [math]\bigstar. Tampoco puede estar el siete por [math]\triangle. Como el catorce tiene dos posibles divisores (uno y dos), debe estar en una esquina con uno y dos adyacentes a su lado. Luego notemos que el diez no puede estar ya que necesita estar adyacente al uno y al dos entonces debería estar en el centro, contradicción ya que el cinco no puede estar.Por lo tanto el caso es bastante parecido a [math]M=12 ya que nos quedaría:
X|3|9
X|X|1
X|2|14
Y se resuelve exactamente igual. Entonces concluímos que dicha configuración no existe
-Si M=15: Entonces una posible distribución sería:
A priori, los números que podemos usar son $1, 2, \dots, 14$, pues asumimos que el máximo es menor o igual a $14$. Notar que $13$ y $11$ no pueden aparecer, porque al ser primos deberían dividir a alguna casilla vecina, y como $13.2>11.2 = 22 >14$ absurdo.
Veamos de manera similar que $7, 5$ tampoco pueden estar. Esta claro que sí el $7$ aparece, debe estar en una esquina, acompañado de $1$ y $14$ (en caso contrario, tendría al menos $3$ casillas vecinas, de donde debe dividir a algún número mayor a $14$). Sin perdida de generalidad:
Pero entonces, no restan números que dividan a $14$ para ponerlo en sus casillas vecinas. Absurdo. En el caso del $5$ es exactamente lo mismo, cambiando $7$ por $5$ y $14$ por $10$.
Veamos ahora que el $9$ tampoco puede ir. Sus únicos divisores propios son $1$ y $3$, y como $9.2>18$ entonces el $9$ debe ir en una esquina acompañado de $1$ y $3$. Sin perdida de generalidad:
$$\begin{array}{|c|c|c|} \hline
&& \\ \hline
1&& \\ \hline
9 & 3 & \\ \hline
\end{array}$$
Notar que las otras dos casillas libres que acompañan al $3$ deben ser múltiplos de $3$, es decir $6$ y $12$ son las únicas opciones. Separemos en dos casos:
El $12$ puede estar junto a $3, 6, 2, 4, 1$, entonces la casilla compartida por $12$ y $6$ debe llevar un $2$, y por descarte la que esta encima del $12$ el $4$.
Pero el $4$ puede estar acompañado por el $1, 2, 8$, y como el $1$ y el $2$ ya los usamos, este caso nos lleva a un absurdo.
Concluimos que el $9$ no puede aparecer. Se sigue que los números que se pueden usar son $1, 2, 3, 4, 6, 8, 10, 12, 14$ (y al haber $9$ casillas, aparecen todos). Pero notar que $14$ y $10$ deben estar en esquinas distintas, acompañados del $1$ y del $2$, lo que nos lleva a un absurdo, y entonces nos queda que el $14$ y el $10$ no pueden aparecen a la vez. Concluimos que el mínimo es $15$.