En cada casilla de un tablero $ n\times n $hay un foco. Inicialmente todos los focos están apagados. En un paso, se permite cambiar el estado de todos los focos en una fila o de todos los focos en una columna (los focos prendidos se apagan y los focos apagados se prenden). Muestra que si después de cierta cantidad de pasos hay uno o más focos prendidos entonces en ese momento hay al menos n focos prendidos.
Enlaces:
[1] https://www.matetam.com/print/problemas/combinatoria/cambios-estado-focos-un-tablero-p2#comment-2001
[2] https://www.matetam.com/print/problemas/combinatoria/cambios-estado-focos-un-tablero-p2#comment-2933
[3] https://www.matetam.com/problemas/combinatoria
[4] https://www.matetam.com/categoria/nivel/avanzado
[5] https://www.matetam.com/problemas/categoria/olimpiada-mexicana-matematicas/xxiv-omm-2010
No se que tan bien esté esta
No se que tan bien esté esta solución:
Aparte de la conmutatividad de los movimientos, se puede ver que después de cierta cantidad de pasos solo importa la paridad del número de veces que se cambió el estado de una fila (o columna): su fue un número par entonces es como si nunca se hubiera cambiado de estado esa fila (o columna) o si fue un número impar es como si se hubiera cambiado de estado solo una vez. Entonces cada fila y cada columna solo tiene dos opciones: ser o no ser cambiada.
Ahora supongamos que después de realizar los pasos una columa del tablero está completamente apagada. Esto se puede lograr de dos formas:
1.- Que esa columna no se cambió de estado y que todas las filas tampoco cambiaron de estado
2.- Que esa columa cambió de estado y que todas las filas también cambiaron de estado.
En el caso 1 tenemos entonces que para que haya al menos un foco prendido entonces debe seleccionarse alguna columna en la cual prender sus focos, lo cual genera n focos prendidos (ya que ninguna fila será cambiada de estado), lo que concluye el problema. En el caso 2 tenemos que todo el tablero estará prendido a excepción de una columna, es decir n(n-1) focos prendidos, y solo podemos bajar el número de focos prendidos de n en n (escogiendo otras columnas en las cuales cambiar de estado), asi que la cantidad de focos prendidos iría como n(n-1), n(n-2), ..., 2n, n, 0, lo cual concluye el problema otra vez.
Con esto demostramos que si hay alguna columna completamente apagada entonces se cumple lo pedido en el problema. Ahora si no hay ninguna columna completamente apagada también se cumple lo del problema, ya que cada columna tendría al menos 1 foco prendido, teniendo al menos n focos prendidos (excluyendo el caso en el que todos estén apagados).
¿Algo malo?
No, nada malo!!! Me gustó [1]
No, nada malo!!!
Me gustó sobre todo el último argumento "cada columna tendría al menos 1 foco prendido, teniendo al menos n focos prendidos", no me lo esperaba.
Por otro lado, ¿cómo justificas lo de la conmutatividad? Yo tengo una forma, pero no me gusta, es muy de matemático. Sobre todo, no imagino qué tanto peso le dieron los jueces a esa observación. ¿Bastaba decirlo o había que justificarlo? ¿Tu no sabes reno?O, ¿podrías platícanos tu justificación?
Saludos
Buen día! Una propuesta de [2]
Buen día!
Una propuesta de solución:
Supongamos que en algún momento llegamos a que hay k focos encendidos con 0<k<n.
Por principio de casillas, hay al menos una columna sin focos encendidos (pues a lo más hay n-1 focos encendidos), de la misma manera se tiene que hay al menos una fila sin focos encendidos. Sean éstas la columna m y la fila n.
También, como 0<k, hay al menos un foco encendido en alguna columna p (diferente de m) y fila q (diferente de n).
Llamemos a,b,c,d a la cantidad de veces que cambiaron de estado p,q,m,n respectivamente.
Como el foco en (p,q) está encendido, a+b es impar, de aquí que alguno entre a y b es impar y el otro es par.
Como el foco en (m,n) está apagado, c+d es par, de aquí que ambos c,d tienen la misma paridad.
Como alguno entre c+b y a+d es impar, la casilla (m,q) ó la casilla (p,n) está encendida, lo cual es una contradicción, pues la columna m y la fila n tenian todos sus focos apagados.
Concluimos entonces que no es posible que se tengan k focos encendidos con 0<k<n.
Saludos!