Página 1 de 1
Nacional 2004 N3P3
Publicado: Jue 27 Oct, 2011 2:54 pm
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]0 y al menos dos [math]1. Dado [math]n\geq 3, hallar todos los enteros [math]k>1 con la siguiente propiedad:
Las columnas de cada tablero variado de [math]k filas y [math]n columnas se pueden permutar de manera que en cada fila del nuevo tablero los [math]1 no formen un bloque (es decir, haya al menos dos [math]1 que están separados por uno o más [math]0).
Re: Nacional 2004 N3P3
Publicado: Jue 27 Oct, 2011 4:36 pm
por Ivan
Algunas ideas que pueden servir:
- Si [math]k tiene la propiedad, entonces todos los números [math]1<k'\leq k también tienen la propiedad.
- Si [math]k NO tiene la propiedad, ningún [math]k'>k tiene la propiedad (el contraejemplo se extiende a uno con más filas).
- Suena razonable buscar algún [math]k que cumpla la propiedad y tal que [math]k+1 no cumpla la propiedad (basta exhibir un contraejemplo).
Es fácil ver que
[math]k=n no cumple la propiedad, este es un contraejemplo (lo escribi para
[math]n=4, pero anda en general):
[math]\begin{array}{clcr} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{array}
Veamos que
[math]n-1 tampoco cumple la propiedad. Consideremos el ejemplo anterior pero dupliquemos la ultima columna:
[math]\begin{array}{ccccc} 0&1&1&1&1 \\ 1&0&1&1&1 \\ 1&1&0&1&1 \\ 1&1&1&0&0 \end{array}
En una permutación de las columnas, las primeras
[math]n-2 columnas no pueden estar en los bordes. Pero entonces las dos últimas columnas son las de los bordes. Sigue que los
[math]1 en la última fila forman un bloque. Entonces es un contraejemplo.
Re: Nacional 2004 N3P3
Publicado: Jue 27 Oct, 2011 5:36 pm
por Ivan
Bueno ahora sí, vamos a probar que [math]k=n-2 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]n, se tiene que [math]k=n-2 cumple la propiedad.
Lo probamos por inducción en [math]n. Supongamos que vale para [math]n-1. Existe una columna del tablero tal que su última casilla es un [math]0. Separemos esta columna. Ahora el resto de las columnas se pueden permutar de modo que las primeras [math]k-1=n-3=(n-1)-2 filas cumplan la propiedad. Puede ocurrir que en este tablero de [math]n\times(k-1) la última fila no cumpla la propiedad, o sea que los [math]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 [math]n. Con esto probamos el paso inductivo.
Para [math]n=3 tenemos el caso base: la única posibilidad para el tablero es [math]\begin{array}{ccc} 1&0&1 \end{array}.
Entonces probamos que el mayor [math]k que cumple la propiedad es [math]n-2, ya que [math]n-1 no la cumple.
Resumiendo: dado [math]n, los [math]k que cumplen la propiedad son [math]n-2\geq k\geq1.
Re: Nacional 2004 N3P3
Publicado: Dom 15 Jul, 2018 4:27 am
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.