IMO 1997 - P4

IMO 1997 - P4

UNREAD_POSTpor Violeta » Dom 05 Mar, 2017 4:24 pm

Uno matriz $n \times n$ se llama argentina si para cada $1 \leq i \leq n$, la i-ésima fila e i-ésima columna, juntas, contienen los enteros del $1$ al $2n-1$.

i) Probar que no existe una matriz argentina para $n = 1997$.

ii) Probar que existe una matriz argentina para infinitos $n$.
Para todo $k$, existen $k$ primos en sucesión aritmética.
Avatar de Usuario
Violeta
 
Mensajes: 323
Registrado: Sab 04 Jun, 2016 11:50 pm
Ubicación: Puerto Rico
Medals: 1
OFO - Mención

Re: IMO 1997 - P4

UNREAD_POSTpor Violeta » Dom 05 Mar, 2017 6:08 pm

Parte a:

Spoiler: Mostrar
Probaremos que es imposible para cualquier $n =2m+1$ impar > 3. Llamemos $S_k$ el conjunto de la fila $k$ y la columna $k$. Una matriz es argentina si cada $S_k$ tiene exactamente uno de cada entero del $1$ al $2n-1$.

Si $a_{ij}$, $i \neq j$, $a_{ij} \in S_i$ y $a_{ij} \in S_j$. (O sea, cada elemento que no está la diagonal principal pertenece a dos $S_k$). Como la matriz tiene $n$ espacios en su diagonal principal, hay por lo menos $n-1$ enteros cuyos elementos en la matriz ninguno cae sobre la diagonal principal. Solo necesitamos uno, digamos $x$.

Como $x$ tiene que estar en cada en cada $S_k$, hay por lo menos $m+1$ veces el $x$ en la matriz. Pero como $x$ no está sobre la diagonal, hay $2m+2$ $S_k$ que tienen a $x$. Ya que $2m+2 > n$, hay por lo menos un $S_k$ que tiene dos $x$ en él. Absurdo y no hay una matriz argentina para cualquier impar, específicamente, $1997$.
Para todo $k$, existen $k$ primos en sucesión aritmética.
Avatar de Usuario
Violeta
 
Mensajes: 323
Registrado: Sab 04 Jun, 2016 11:50 pm
Ubicación: Puerto Rico
Medals: 1
OFO - Mención

Re: IMO 1997 - P4

UNREAD_POSTpor Violeta » Lun 06 Mar, 2017 8:16 pm

Parte b:

Spoiler: Mostrar
Se prueba por induccion que si existe una matriz argentina para $n$, existe una para $2n$.

Tomaremos como case base $n=2$ (ya que $n=1$ es poco original). La matriz:

$\left[
\begin{matrix} 
1 & 2 \\
3 & 1
\end{matrix} \right ]$

es argentina.

Ahora, asumimos que existe una matriz argentina $k \times k$ para $k \geq 2$. Entonces, la matriz $2k \times 2k$ se puede particionar en $4$ mini-matrices $k \times k$. En las sub-matrices $k \times k$ superior izquierda e inferior derecha se escriben las matrices argentinas $k \times k$ que ya sabemos existen por la hipotesis inductiva. Ahora, bien, usando la nomenclatura previa de los $S_i$, sabemos que todos los $S_i, 1 \leq i \leq 2k$ tienen exactamente uno de cada entero del $1$ al $2k-1$. Falta colocar los elementos del $2k$ al $4k-1$. En la sub-matriz superior derecha colocamos los numeros del $2n$ al $3n-1$ de tal forma que en cada columna y fila de esta sub-matriz cada entero aparezca una vez. En la sub-matriz inferior izquierda colocamos los numeros del $3n$ al $4n-1$, con la misma condicion que antes. (Estas dos sub-matrices no son dificiles de hacer. En la primera fila se escriben los numeros en orden ascendiente y en la fila siguiente, el elemento en la posicion $i$ ahora se pone en la posicion $i+1$, mirando mod $k$, claro).

Ya que esta nueva matriz cumple la condicion de una matriz argentina, queda probado.
Para todo $k$, existen $k$ primos en sucesión aritmética.
Avatar de Usuario
Violeta
 
Mensajes: 323
Registrado: Sab 04 Jun, 2016 11:50 pm
Ubicación: Puerto Rico
Medals: 1
OFO - Mención


Volver a Combinatoria

¿Quién está conectado?

Usuarios navegando por este Foro: No hay usuarios registrados visitando el Foro y 2 invitados