sábado, 5 de diciembre de 2009

Problema del Día

Trataré de empezar a poner problemas que me gustan en el blog. Me gustaría que los intentaran y comentaran sobre el problema.
Ya que hace poco puse el problema 6 del nacional de Morelia, ahora pondré el 5 de ese mismo nacional. En lo personal me parece casi de la misma dificultad y me dio gusto intentarlo hace 3 días. No lo había revisitado desde mi nacional y me dio gusto que ahora si me salió. Además siento que el problema en sí es muy bonito.
Allí les va:

Se tiene un tablero de n x n pintado como tablero de ajedrez. Está permitido efectuar la siguiente operación en el tablero:
Escoger un rectángulo en la cuadrícula tal que las longitudes de sus lados sean ambas pares o ambas impares, pero que no sean las dos iguales a 1 al mismo tiempo, e invertir los colores de los cuadritos de ese rectángulo (es decir, los cuadritos del rectángulo que eran negros se convierten en blancos y los que eran blancos, se convierten en negros).

Encuentra para que n's es posible lograr que todos los cuadritos queden de un mismo color después de haber efectuado la operación el número de veces que sea necesario.
Nota: Las dimensiones de los rectángulos que se escogen pueden ir cambiando.

11 comentarios:

  1. intentare el problema.. jeje.

    aki va uno de nuevo leon:

    Demuestra que si
    a²+b²+c²=1
    entonces

    -1/2 <= ab + bc + ac <= 1

    ResponderBorrar
  2. Bueno supongo que si, pues lo de -1/2 no tendria sentido xD

    ResponderBorrar
  3. *** SPOILER DEL PROBLEMA DE DANIEL***

    -1/2 <= ab + bc + ac <= 1
    <->
    0<= ab + bc + ac +1\2 <= 3\2

    Primero demostremos
    0<= ab + bc + ac +1\2


    como (a²+b²+c²)/2=1/2

    ab + bc + ac + 1\2 =
    ab + ac + bc + (a²+b²+c²)/2 =
    (2(ab+ac+bc)+ (a²+b²+c²)/2 =
    (a+b+c)²/2 >= 0

    Ahora demostremos
    ab + bc + ac +1\2 <= 3\2
    que es equivalente a demostrar
    (a+b+c)²/2<=3/2
    (a+b+c)²<=3

    De la desigualdad del triangulo tenemos que:
    |a+b+c|<=|a|+|b|+|c|
    elevando al cuadrado:
    (a+b+c)²<=(|a|+|b|+|c|)²
    Ahora hacemos la sustitucion(solo para mas comodidad):
    x=|a|
    y=|b|
    z=|c|

    entonces
    (a+b+c)²<=(x+y+z)²

    y la condicion se transforma en:
    x²+y²+z²=1

    dividiendo entre 3 y luego sacando raiz a la condicion y luego aplicando mc-ma tenemos que:

    sqrt((x²+y²+z²)/3)= 1/sqrt(3)=sqrt(3)/3 >= (x+y+z)/3

    elevamos al cuadrado y tenemos que:
    3/9>=(x+y+z)²/9
    (x+y+z)²<=3

    Por lo tanto:
    (a+b+c)²<=(x+y+z)²<=3
    que era lo que queriamos demostar.

    *** FIN DEL SPOILER PROBLEMA DE DANIEL ***

    ResponderBorrar
  4. MI SOLUCION>

    Tenemos 0<= ab+bc+ac+1/2
    1/2=(a²+b²+c²)/2
    asi tenemos :
    P.D.
    0<=ab+bc+ac+a²/2+b²/2+c²/2
    si multiplicamos todo por 2 tenemos
    0<=2ab+2bc+2ac+a²+b²+c²
    y pues eso es (a+b+c)² que obviamente es NO NEGATIVO o >=0.


    la segunda parte.. tenia un error en la solucion(se me esta haciendo costumbre) lo intentare esta noche ia con mas calma)

    ResponderBorrar
  5. lol, tu primera parte de la solucion de la desigualdad es identica a la mia xD

    ResponderBorrar
  6. solucionando el problema de Quike:

    Se puede para toda n distinta de 1 y 2.

    Demostracion:

    en la cuadricula de nxn,con n impar, basta con seleccionar las columnas en posiciones pares e invertirles el color. asi nos quedará una cuadricula con un renglon de un color y el siguiente del otro. Entonces seguimos por cambiar los renglones que son de color negro es decir.. de tamaño nx1 e invertirles nuevamente el color. Asi nos quedará una cuadricula de nxn con TODOS sus cuadritos de color blanco.

    para nxn con n = potencia de 2, basta con demostrar el caso para n=4, ya que siendo n una potencia de dos, podemos seccionar la cuadricula en regiones de 4x4.
    n=4:
    tomamos rectangulos de 2x4. en este caso tomamos las primeras dos columnas y les cambiamos el color. luego tomamos las 2 columnas del centro y nuevamente les invertimos el color para obtener renglones de color uniforme. Procedemos a tomar los dos ultimos renglones para cambiarles el color y asi tener solo los dos rengloens del centro de color diferente. El siguiente paso se los dejamos a su imaginacion: jajaja. XD.

    para nxn con n par y sin ser potencia de 2 se prosigue asi:

    sea 2^k la potencia de 2 mas grande que divide a n y r=n/2^k. Sabemos entonces que r es impar. por lo que dividiremos nuestra cuadricula en secciones de rxr y proseguiremos a cambiar el color de la forma en que lo hicimos para n impar.

    Conclusion:
    CUMPLE TODA n A EXCEPCION DE n=1,2. (es facil ver porque esas n´s no cumplen:
    N=1: La condicion nos dice que no pueden ser rectangulos de 1x1,por lo tanto no se puede cambiar)
    N=2: La condicion del problema indica que podemos seleccionar rectangulos con el ancho de la misma paridad que el largo, en la cuadricula de 2x2, el unico rectangulo que puede cambiarse es el de 2x2, pero al hacer esto, nunca cambiaremos la cantidad de cuadritos blancos y de negros.)


    wow.. si hayalgun error avisenme.. jeje como les digo, iia c sta haciendo costumbre..

    ResponderBorrar
  7. Tu solución es correcta Daniel. Buen trabajo.

    SPOILER:
    A mi me tomó mucho tiempo hacerla. Primero vi que 8 cumplía y luego los impares y me tomó mucho tiempo ver que el 4 cumplía, de hecho intente demostrar que no cumplía.

    ResponderBorrar
  8. pues.. entonces como resolviste el de n=8 de tal forma que no lo relacionaras con n=4?...

    ResponderBorrar
  9. Pues en el de 4x4 demostré que podías llegar a todo blanco excepto una esquina (la esquina que quisieras), entonces dividía el 8x8 en 4 de 4x4 y en cada uno escogí la esquina de tal manera que el de 8x8 es todo blanco excepto por un cuadradito de 2x2 en el centro y pues agarras ese y listo, tienes el de 8x8 blanco.

    ResponderBorrar
  10. ah ia c como.. mmmm tomas 3x3 luego 1x3 y 1x3 y ya te keda una esquina

    ResponderBorrar