miércoles, 26 de enero de 2011
Problema del día miércoles 26 de Enero-COM
Dado un número natural $n\neq 1$, encontrar el menor entero positivo $k$ con la siguiente propiedad: Cada conjunto de $k$ cuadritos de un tablero de $n$x$n$ contiene un subconjunto no vacío $S$ tal que en cada fila y cada columna del tablero hay una cantidad par de cuadritos en $S$.
Suscribirse a:
Comentarios de la entrada (Atom)
14 comentarios:
No es cierto lo que dices de que en $S$·siempre hay 4 cuadritos que son las esquinas de un rectángulo. un contraejemplo fácil es con un tablero de 3x3:
XXO
OXX
XOX
Donde los cuaditos con X están en $S$
Si, lo noté pero me fui a dormir y hoy en la mañana tuve examen asi que no tuve tiempo de borrarlo
El mínimo de cuadritos para un tablero de nxn es 2n.
Primero veamos que si tenemos 2n-1 cuadritos no necesariamente funciona, para ver esto elijamos los cuadritos de la primera fila y de la primera columna, estos son 2n-1 cuadritos. Pero cada fila excepto la primera tiene 1 o 0 cuadritos, como tiene que ser par tiene que ser 0, de la misma forma cada columna excepto la primera tiene que tener 0 cuadritos, por lo tanto solo nos queda el cuadrito de la esquina como no lo podemos quitar por que tiene que ser un subconjunto no vacio, entonces la primera fila y columna tienen un numero impar de cuadritos, por lo tanto no cumple.
Ahora probaremos con induccion que con al menos 2n cuadritos si cumple.
Base de inducción n=2 cada fila y coluna tienen 2 por lo tanto si cumple.
Ahora supongamos que si tenemos un tablero de r-1xr-1 con al menos 2(r-1) cuadritos entonces si cumple.
Ahora probaremos que si tenemos un tablero de rxr con 2r cuadritos cumple.
Para esto dividamos en 3 casos
1.-Hay una columna o fila con 0 cuadritos.
2.-Hay una columna o fila con 1 cuadrito.
3.-Todas las columnas o filas tienen al menos dos cuadritos.
1.-Si hay una columna sin cuadritos, entonces como hay 2r cuadritos y hay r filas entonces hay una fila con 2 o menos cuadritos, por lo tanto si quitamos esta fila y la columna sin cuadritos, entonces el tablero que queda de r-1xr-1 tiene al menos 2(r-1) cuadritos, por lo tanto por la induccion acabamos.
2.-Por un argumento similar acabamos.
3.-Si hay al menos 2 cuadritos en cada fila entonces como hay exactamente 2r cuadritos tiene que haber 2 cuadritos exactamente en cada fila y de la misma forma 2 cuadritos exactamente en cada columna, por lo tanto acabamos.
Por lo tanto si es cierto para r+1 y por lo tanto por induccion el minimo es 2n para todos los enteros positivos n. Fin
Bien Georges! La solución que yo hice es con gráficas. Considera la gráfica bipartita $K_{n,n}$ en la que cada arista representa un cuadrito del tablero. Si coloreamos $2n$ aristas va a haber un ciclo y es fácil ver que un ciclo cumple lo que queremos.
Esta padre tu solución!!!! ¿De donde es el problema???
Creo que no entiendo bien lo que pide el problema... si me lo pudieran explicar con manzanas sería bueno :)
@Georges: No puedo decir de dónde es, hasta el domingo...
@Manuel: ¿qué parte es la que no entiendes? Según yo es clara la redacción, leelo de nuevo con calma y si de plano no le entiendes me dices qué parte quieres que te explique.
Bueno, entiendo que se eligen k de $n^{2}$, luego de eso se elige un subconjunto S, pero éste cómo está determinado ¿?
Creo que mi solución estaba mal por la parte del cuadrado pero ahi va de nuevo un poco cambiada:
Podemos ver que 2n-1 no funciona puesto que tomamos toda una fila y una diagonal mayor y habrá a lo más un subconjunto que hace que una fila tenga una cantidad par de cuadritos, pero cada uno de esos cuadritos está contenido en una columna y entonces esas columnas deben tener cuando menos 2 cuadritos y entonces debe haber al menos otra fila con cantidad par de cuadritos distinto de 0 y no hay.
Demostremos por inducción que 2n funciona:
caso base: n=2 funciona.
Supongamos que funciona hasta cierto i.
Veamos qué pasa con i+1:
Quitaremos una fila y una columna que juntos tengan 2 cuadritos o menos y si hay en ese cuadrado cuando menos 2i cuadritos acabaremos puesto que funcionaba para el cuadrado de i X i
tomemos la fila que tenga la menor cantidad de cuadritos y dividamos en casos:
si esta no tiene cuadritos de los seleccionados entonces con una columna que tenga 2 cuadritos o menos, el cual existe ya que como hay 2i+2 cuadritos e i+1 columnas, por el principio de casillas hay al menos uno con 2 o menos y ya.
si esta fila tiene 1 cuadrito, entonces tomamos una columna que tenga 1 cuadrito o ninguno (si existe) y acabamos, en caso contrario, todas las columnas tienen 2 y entonces con la que la fila comparte cuadrito entre los dos tienen 2 cuadritos y ya.
Si ninguna se da entonces todas las filas tienen 2 cuadritos, si una columna no tiene cuadritos, acabamos, si la que tiene menos es uno entonces tomamos esa y la fila que comparte con ella el cuadrito y acabamos, si ninguna pasa, todas las filas y columnas tienen 2 cuadritos y la selección completa es el subocnjunto S y acabamos
Ah, ya entendí, no te preocupes en explicarlo XD
después intento resolverlo
Notemos primeramente que 2n-1 fichas no es suficiente. Para ello, ponemos fichas en los cuadros de una diagonal del cuadro, y el cuadrito continuo a la derecha de cada uno de esa diagonal (excepto uno que no se va a poder, ya que esos cuadros serán una “diagonal” de n-1 cuadritos), y de ninguna manera puede elegirse un subconjunto de esos 2n-1 tq cumplan lo que pide el problema, más aún, con un valor menor, tampoco se podrá. Ahora, demostraré que 2n fichas son suficientes. Para n=2, es notorio que es posible. Ahora, supongamos que para algún $n\geq2$ es suficiente 2n. Ahora por inducción, demostraré que para n+1, 2(n+1) piezas son suficientes. Consideremos un caso en que tomando los 2(n+1) piezas no funcione, entonces sabes que no funciona porque hay una fila o columna con una cantidad impar de cuadros. Si sucede esto, puedes afirmar que hay alguna fila o columna con 0 ó 1 cuadros. SPG supones que es una columna. Entonces ahora dejando de considerar esa columna, en las demás n(n+1) cuadritos, hay al menos 2n+1 piezas. Por casillas, alguna de las filas tiene sólo 1 pieza (a menos que todas tengan dos y la columna que quitamos tuviera 0 piezas, en dado caso tomaré cualquier fila), entonces quitamos dicha fila. Entonces me queda una cuadrícula de nxn, donde hay almenos 2n piezas, lo cual ya estaba demostrado que se podía por hipótesis de inducción.
nos fijamos que en un tablero de 2 filas y n columnas si nos tomamos n+2 cuadritos y nos fijamos en las columnas, por casillas habra dos que contengan 2 cuadritos y al tomarnos esos 4 cuadros del conjunto tendremos un subconjunto con cantidad par de cuadros en cada fila y columna.Esta es nuestra base.
Ahora por induccion sobre m+n probaremos que si tenemos una cuadricula de mxn y nos tomamos cualquier conjunto con al menos m+n cuadros, existira un subconjunto tal que cumpla las condiciones.
Digamos que cumple para toda cuadricula de axb con a,b>1 y a+b=m+n
Veamos que cumple para una cuadicula de axb con a,b>1 y a+b=m+n+1 si alguno de a o b es igual a 2 ya cubrimos el caso con el caso base, si los dos son mayores a 2 entonces nos tomamos cualquier conjunto de a+b cuadritos, y nos fijamos en cualquiera de los cuadrito.
Si en la fila en la que esta ese cuadro no hay ningun otro cuadro del conjunto podemos eliminar esa fila y nos quedara un tablero de cxd con c+d=m+n y con un conjunto de m+n, por inducción habra subconjunto que cumpla las condiciones, y tambien en el de axb,lo mismo pasa si en la mimsa columna en la que esta el cuadro no hay otro.
Entonces al menos debera haber para cada cuadro, otro cuado en su misma columna y otro en su misma fila, entonces nos ponemos en cualquier cuadro y nos vamos al otro q este en su misma fila, de este nos vamos alque este en su misma columna, y de este nuevo al que este en su misma fila, y asi sucesivamente, como siempre habra cuadrito podemos asegurar que siempre podemos seguir haciendo esto,y como hay finitos cuadros en algun momento regresaremos a un cuadro por qel que ya pasamos, y se repetira el ciclo, por lo tanto nos podemos tomar este ciclo y acabamos.
Para ver que en una cuadricula de mxn existe algun conjunto de m+n-1 con el que no se puede. nos tomamos todos los cuadros de una fila y todos los de una columna(habra m+n-1), es facil checar que no cumple, como el subconjunto no puede ser vacio y si existe un cuadro, en su misma fila debe haber al menos dos para ser par,por lo que debera haber al menos 2 cuadros en el subconjunto, alguno sera el que no es la inteseccion de la fila y la columna que escogimos, sin embargo solo habra ese cuadro en su columna (o fila) dependiendo si el cuadro esta respectivamente en la fila(o columna).
con 2n-1 >=k el contraejemplo es Un tablero con la primera columna y fila escogidas. Vere que para k=2n cumple, lo hare por induccion, la base es n=2, que es muy claro. PAra 2n cuadritos, si no hay una fila o columna con menos de dos cuadritos de los seleccionados, entonces todos tienen dos y ese subconjunto funciona, por casillas, hay una fila y una columna con a los mas 2 de los cuadros escogidos. si no hya con 1 o 0 ya vimos que ya acabe. entonces si hay una fila o columna con 0 (sin perdida de generalidad supongamos que es una fila) luego podemos borrarla y quedan 2n cuadros. Luego tomemos la columna con menos cuadros escogidos (ya vimo que tiene a lo mas 2 y a parte le borramos una fila) y si se la borramos queda un tablero de (n-1)*(n-1) con 2n-2 cuadros y entonces por induccion ya acabe. Entonces ahora supongamos que en toda columan hay y en toda fila hay, y que la que menos tiene, tiene 1. Supongamos sin p de g que una fila tiene exactamente 1 cuadro. Luego la borramos, y nos quedan 2n-1 cuadros y n columnas para repartir, entonces por casillas hay una columna con a lo mas 1 cuadro, vimos que si habia una fila/columna sin cuadros ya acababa, entonces supongamos que tiene uno esa columna. Luego borramos esa columan tambien y nos quedan 2n-2 cuadros y un tablero de (n-1)x(n-1) y ya acabamos igual.
Publicar un comentario