Nacional 2004 N3P3

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Carolang
Mensajes: 65
Registrado: Vie 05 Nov, 2010 12:14 am
Nivel: Exolímpico
Ubicación: Flores

Nacional 2004 N3P3

Mensaje sin leer por Carolang »

Se colocan ceros y unos en cada casillero de un tablero rectangular. Se dice que un tablero así es variado si cada fila contiene al menos un [math] y al menos dos [math]. Dado [math], hallar todos los enteros [math] con la siguiente propiedad:

Las columnas de cada tablero variado de [math] filas y [math] columnas se pueden permutar de manera que en cada fila del nuevo tablero los [math] no formen un bloque (es decir, haya al menos dos [math] que están separados por uno o más [math]).
Imagen Azúcar, flores y muchos colores.
Avatar de Usuario
Ivan

Colaborador-Varias
Mensajes: 1023
Registrado: Vie 15 Oct, 2010 7:18 pm
Medallas: 1
Nivel: Exolímpico

Re: Nacional 2004 N3P3

Mensaje sin leer por Ivan »

Algunas ideas que pueden servir:
  • Si [math] tiene la propiedad, entonces todos los números [math] también tienen la propiedad.
  • Si [math] NO tiene la propiedad, ningún [math] tiene la propiedad (el contraejemplo se extiende a uno con más filas).
  • Suena razonable buscar algún [math] que cumpla la propiedad y tal que [math] no cumpla la propiedad (basta exhibir un contraejemplo).
Es fácil ver que [math] no cumple la propiedad, este es un contraejemplo (lo escribi para [math], pero anda en general):

[math]

Veamos que [math] tampoco cumple la propiedad. Consideremos el ejemplo anterior pero dupliquemos la ultima columna:

[math]

En una permutación de las columnas, las primeras [math] columnas no pueden estar en los bordes. Pero entonces las dos últimas columnas son las de los bordes. Sigue que los [math] en la última fila forman un bloque. Entonces es un contraejemplo.
Guía de $\LaTeX$ (sirve para escribir ecuaciones como $2^{3\times 2}+1=13\cdot 5$)
Avatar de Usuario
Ivan

Colaborador-Varias
Mensajes: 1023
Registrado: Vie 15 Oct, 2010 7:18 pm
Medallas: 1
Nivel: Exolímpico

Re: Nacional 2004 N3P3

Mensaje sin leer por Ivan »

Bueno ahora sí, vamos a probar que [math] cumple la propiedad.

Observación: si un tablero cumple la propiedad y insertamos una columna cualquiera en el medio sigue cumpliendo la propiedad.

Afirmación: Dado [math], se tiene que [math] cumple la propiedad.

Lo probamos por inducción en [math]. Supongamos que vale para [math]. Existe una columna del tablero tal que su última casilla es un [math]. Separemos esta columna. Ahora el resto de las columnas se pueden permutar de modo que las primeras [math] filas cumplan la propiedad. Puede ocurrir que en este tablero de [math] la última fila no cumpla la propiedad, o sea que los [math] formen un bloque. Pero ahora basta con insertar la columna que separamos en el medio del bloque de unos. O sea que vale para [math]. Con esto probamos el paso inductivo.

Para [math] tenemos el caso base: la única posibilidad para el tablero es [math].

Entonces probamos que el mayor [math] que cumple la propiedad es [math], ya que [math] no la cumple.

Resumiendo: dado [math], los [math] que cumplen la propiedad son [math].
Guía de $\LaTeX$ (sirve para escribir ecuaciones como $2^{3\times 2}+1=13\cdot 5$)
juandodyk

OFO - Medalla de Oro-OFO 2022 OFO - Medalla de Oro-OFO 2023 OFO - Mención-OFO 2024
Mensajes: 42
Registrado: Mar 26 Jun, 2018 1:59 am
Medallas: 3
Nivel: Exolímpico

Re: Nacional 2004 N3P3

Mensaje sin leer por juandodyk »

Ivan escribió: Jue 27 Oct, 2011 5:36 pm Lo probamos por inducción en $n$. Supongamos que vale para $n-1$. Existe una columna del tablero tal que su última casilla es un $0$. Separemos esta columna. Ahora el resto de las columnas se pueden permutar de modo que las primeras $k-1=n-3=(n-1)-2$ filas cumplan la propiedad. Puede ocurrir que en este tablero de $n\times(k-1)$ la última fila no cumpla la propiedad, o sea que los $1$ formen un bloque. Pero ahora basta con insertar la columna que separamos en el medio del bloque de unos. O sea que vale para $n$. Con esto probamos el paso inductivo.
Al separar esa columna el tablero te puede quedar no variado (porque eliminaste un 0 de una fila con un solo 0, o eliminaste un 1 de una fila con sólo dos 1s). Así que no podés aplicar la hipótesis inductiva. Yo creo que sale, pero es bastante más complicado que eso.
1  
Responder