IMO 1997 - P4

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

OFO - Mención-OFO 2017 FOFO 7 años - Medalla Especial-FOFO 7 años OFO - Medalla de Bronce-OFO 2018 FOFO 8 años - Mención Especial-FOFO 8 años OFO - Medalla de Plata-OFO 2019
Mensajes: 405
Registrado: Sab 04 Jun, 2016 11:50 pm
Medallas: 5
Ubicación: Puerto Rico

IMO 1997 - P4

Mensaje sin leer por Violeta »

Uno matriz [math] se llama argentina si para cada [math], la i-ésima fila e i-ésima columna, juntas, contienen los enteros del [math] al [math].

i) Probar que no existe una matriz argentina para [math].

ii) Probar que existe una matriz argentina para infinitos [math].
Para todo [math], existen [math] primos en sucesión aritmética.
Avatar de Usuario
Violeta

OFO - Mención-OFO 2017 FOFO 7 años - Medalla Especial-FOFO 7 años OFO - Medalla de Bronce-OFO 2018 FOFO 8 años - Mención Especial-FOFO 8 años OFO - Medalla de Plata-OFO 2019
Mensajes: 405
Registrado: Sab 04 Jun, 2016 11:50 pm
Medallas: 5
Ubicación: Puerto Rico

Re: IMO 1997 - P4

Mensaje sin leer por Violeta »

Parte a:
Spoiler: mostrar
Probaremos que es imposible para cualquier [math] impar > 3. Llamemos [math] el conjunto de la fila [math] y la columna [math]. Una matriz es argentina si cada [math] tiene exactamente uno de cada entero del [math] al [math].

Si [math], [math], [math] y [math]. (O sea, cada elemento que no está la diagonal principal pertenece a dos [math]). Como la matriz tiene [math] espacios en su diagonal principal, hay por lo menos [math] enteros cuyos elementos en la matriz ninguno cae sobre la diagonal principal. Solo necesitamos uno, digamos [math].

Como [math] tiene que estar en cada en cada [math], hay por lo menos [math] veces el [math] en la matriz. Pero como [math] no está sobre la diagonal, hay [math] [math] que tienen a [math]. Ya que [math], hay por lo menos un [math] que tiene dos [math] en él. Absurdo y no hay una matriz argentina para cualquier impar, específicamente, [math].
Para todo [math], existen [math] primos en sucesión aritmética.
Avatar de Usuario
Violeta

OFO - Mención-OFO 2017 FOFO 7 años - Medalla Especial-FOFO 7 años OFO - Medalla de Bronce-OFO 2018 FOFO 8 años - Mención Especial-FOFO 8 años OFO - Medalla de Plata-OFO 2019
Mensajes: 405
Registrado: Sab 04 Jun, 2016 11:50 pm
Medallas: 5
Ubicación: Puerto Rico

Re: IMO 1997 - P4

Mensaje sin leer por Violeta »

Parte b:
Spoiler: mostrar
Se prueba por induccion que si existe una matriz argentina para [math], existe una para [math].

Tomaremos como case base [math] (ya que [math] es poco original). La matriz:

[math]

es argentina.

Ahora, asumimos que existe una matriz argentina [math] para [math]. Entonces, la matriz [math] se puede particionar en [math] mini-matrices [math]. En las sub-matrices [math] superior izquierda e inferior derecha se escriben las matrices argentinas [math] que ya sabemos existen por la hipotesis inductiva. Ahora, bien, usando la nomenclatura previa de los [math], sabemos que todos los [math] tienen exactamente uno de cada entero del [math] al [math]. Falta colocar los elementos del [math] al [math]. En la sub-matriz superior derecha colocamos los numeros del [math] al [math] 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 [math] al [math], 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 [math] ahora se pone en la posicion [math], mirando mod [math], claro).

Ya que esta nueva matriz cumple la condicion de una matriz argentina, queda probado.
Para todo [math], existen [math] primos en sucesión aritmética.
Responder