Sel Ibero 2000 Problema 1

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

Colaborador-Varias OFO - Jurado-OFO 2015
Mensajes: 401
Registrado: Sab 18 Dic, 2010 8:52 pm
Medallas: 2

Sel Ibero 2000 Problema 1

Mensaje sin leer por Prillo »

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.
ktc123

OFO - Medalla de Plata-OFO 2015 OFO - Medalla de Plata-OFO 2016 OFO - Medalla de Bronce-OFO 2017 OFO - Mención-OFO 2019 OFO - Medalla de Plata-OFO 2020
OFO - Mención-OFO 2021
Mensajes: 204
Registrado: Jue 21 Jun, 2012 9:09 pm
Medallas: 6
Nivel: Exolímpico
Ubicación: La Plata, Buenos Aires

Re: Sel Ibero 2000 Problema 1

Mensaje sin leer por ktc123 »

Spoiler: mostrar
Sea [math] el mayor de los nueve números. Entonces como es el más grande, sus casillas adyacentes tienen que dividir a [math].Ahora notemos que como son todos los números distintos entonces [math].


-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]")


-Si M=10: Notemos que por [math] 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])


-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](lo mismo ocurre con el número once). Por [math] 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]


-Si M=14: Ni el cinco, ni el once, ni el trece pueden estar por [math]. Tampoco puede estar el siete por [math]. 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] 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:

6|3|15
12|1|5
4|2|10
1  
¨Todos somos muy ignorantes. Lo que ocurre es que no todos ignoramos las mismas cosas¨. Contacto: [email protected]
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 FOFO 14 años - Mención-FOFO 14 años
Mensajes: 1272
Registrado: Sab 21 May, 2022 12:41 pm
Medallas: 4
Nivel: Exolímpico
Contactar:

Till kingdom come

Mensaje sin leer por drynshock »

Spoiler: mostrar
Apostamos que el mínimo es $15$.
Ejemplo:

$$\begin{array}{|c|c|c|} \hline
12&4&8 \\ \hline
3&1&2 \\ \hline
15 & 5 & 10 \\ \hline
\end{array}$$

Demostración de que no se puede con menos:

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:

$$\begin{array}{|c|c|c|} \hline
&& \\ \hline
1&& \\ \hline
7 & 14 & \\ \hline
\end{array}$$

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:

Caso 1
$$\begin{array}{|c|c|c|} \hline
&& \\ \hline
1&6& \\ \hline
9 & 3 &12 \\ \hline
\end{array}$$

Pero el $6$ solo puede estar acompañado del $1, 2, 3, 12$, de donde al estar en el medio, nos queda una casilla libre. Absurdo.

Caso 2
$$\begin{array}{|c|c|c|} \hline
&& \\ \hline
1&12& \\ \hline
9 & 3 &6 \\ \hline
\end{array}$$

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$.

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

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$.
@Bauti.md ig
Winning is first place, anything else is losing.
"Alexandra Trusova"
Responder