Un museo está equipado con 16 cámaras de vigilancia CCTV, cada una de las cuales se enciende o apaga con un interruptor diferente.
Digamos, el interruptor 1 controla la cámara CCTV-1, el interruptor 2 controla la cámara CCTV-2,… y el interruptor 16 controla la cámara CCTV-16.
Cada región separada del museo está cubierta por múltiples cámaras CCTV de las requeridas y esa configuración no se puede cambiar ahora.
En aras de cumplir con los límites de almacenamiento de datos sin comprometer la vigilancia de cualquier área del museo, y debido a otras limitaciones, el administrador de vigilancia creó un plan para alternar (encender o apagar) las cámaras al comienzo de cualquier día como se explica a continuación con la ayuda de una tabla de 4×4 de los interruptores 1 a 16:
(i) Inicio de cualquier día, los interruptores en cualquiera de las filas o columnas elegidas al azar en la tabla que se muestra arriba se pueden alternar todos a la vez (alternar aquí significa que si estaban ENCENDIDOS ayer, estarán APAGADOS hoy y viceversa). O bien, ninguno de ellos puede alternarse en absoluto.
(ii) No se puede cambiar durante el día.
Ejemplo-1:
Suponiendo que en un día ‘n’ todas las dieciséis cámaras están ENCENDIDAS, al día siguiente ‘n+1’, las cámaras 5, 6, 7 y 8 pueden estar APAGADAS mientras que todas las cámaras restantes pueden estar ENCENDIDAS. En este caso, la segunda fila se elige para alternar al comienzo del día ‘n+1’.
Ejemplo-2:
Suponiendo que en un día ‘n’ las cámaras 1 y 5 están ENCENDIDAS y todas las demás están APAGADAS, luego en el día siguiente ‘n+1’, las cámaras 9 y 13 pueden estar ENCENDIDAS mientras que todas las cámaras restantes pueden estar APAGADAS . En este caso, la primera columna se elige para alternar al comienzo del día ‘n+1’.
El gerente de vigilancia había comenzado el primer día de operación (la condición inicial) con las cámaras 1, 7 y 14 apagadas mientras que todas las demás cámaras estaban encendidas.
Pregunta:
a) ¿Es posible que después de algunos días, las cámaras 10, 11, 12 y 13 estén ENCENDIDAS mientras que todas las demás cámaras están APAGADAS?
b) ¿Es posible que después de algunos días, las cámaras 1, 2, 3, 4, 5, 6 y 7 estén APAGADAS mientras que todas las demás están ENCENDIDAS?
Responder:
a) No
b) No
Solución:
aplicar cada cambio seleccionando una fila o columna e intentar llegar a las condiciones finales dadas como en las preguntas a) y b) es una gran tarea y, por lo tanto, nos vemos obligados a pensar en una estrategia y observar cuidadosamente lo que sucede después de cada cambio. y si puede obtener algunas pistas, eso será de ayuda para nosotros.
Como cada interruptor solo puede estar ENCENDIDO o APAGADO, tendemos a resolver el problema denotando ENCENDIDO y APAGADO con 1 y 0 o signos + y – y observando qué sucede con la suma de valores o el producto de los signos después de cada cambio.
Ahora nos damos cuenta de que + y – son más útiles ya que la cantidad de elementos en cualquier fila o columna es un número par (4). Porque alternar todos los signos de una colección de algunos signos positivos y algunos signos negativos que suman un número par no cambiará el signo resultante de su producto. Examinemos más a fondo esta estrategia.
Ejemplo – 1 : El producto de los signos en la colección {+, -} es -ve. Después de alternar, se convierte en {-, +} y el producto de los signos en la colección sigue siendo el mismo.
Ejemplo – 2 : El producto de los signos en la colección {+, -, +, -} es +ve. Después de un cambio, se convierte en {+, -, +, -} y el producto de los signos en la colección sigue siendo el mismo.
Ejemplo – 3 : El producto de los signos en la colección {-, -, +, +, +, +, +, -} es -ve. Después de un cambio, se convierte en {+, +, -, -, -, -, -, +} y el producto de los signos en la colección sigue siendo el mismo.
Asignemos signo positivo a un interruptor que está ENCENDIDO y signo negativo a un interruptor que está APAGADO. Entonces la configuración inicial dada es como se muestra a continuación:
Sabemos que la única alternancia válida de los interruptores/cámaras es elegir una fila o columna y alternar todos los interruptores en esa fila o columna. Como el número de cambios en cualquier fila o columna es par , un cambio válido no cambiará el producto de los signos de la fila o columna elegida en comparación con el producto de los signos en esa fila o columna que existía el día anterior.
Observamos que el producto de los signos de todos los interruptores en la tabla 4×4 no es más que el producto de los signos de los productos de las cuatro filas o, de manera equivalente, las cuatro columnas. Por lo tanto, también podemos deducir que el producto de los signos de todos los cambios en la tabla completa antes y después de un cambio válido sigue siendo el mismo.
Esto se ilustra con un ejemplo en el siguiente diagrama:
Para responder a) , observamos que en la configuración inicial dada el producto de signos de toda la tabla es -ve como se muestra en el lado izquierdo de la figura anterior.
La configuración final buscada tiene las cámaras 10, 11, 12 y 13 encendidas y todas las demás apagadas. Eso se puede ilustrar siguiendo nuestra estrategia de asignación de signos como se muestra a continuación:
Como se muestra arriba, el producto de los signos de toda la tabla es +ve.
Entonces, no importa cuántos días (cuántos conmutadores válidos), no se puede obtener la configuración final ya que el producto inicial de los signos de toda la tabla es -ve y el producto final de los signos de toda la tabla es +ve .
Para responder b) , si probamos el método anterior de producto de signos de toda la tabla, no sirve porque 1, 2, .., 7 están APAGADOS y todos los demás están ENCENDIDOS. Significa que la configuración final tiene el producto de los signos de toda la tabla es -ve , que es lo mismo que el producto de los signos de toda la tabla de la configuración inicial. Entonces, parece que es posible obtener la configuración en b), pero para demostrar que necesitamos encontrar una secuencia de alternancia que lo logre. Pero antes de emprender esa tarea, intentemos encontrar una colección diferente de interruptores que no cambie su producto de signos y que ayude a resolver esta parte del problema.
Podemos pensar en una colección de filas alternativas como candidato para nuestra elección. Es decir, todos los signos de la Fila-1 y la Fila-3 se denominan colección impar y todos los signos de la Fila-2 y la Fila-4 se denominan colección par. Aunque una alternancia válida no cambia el producto de todos los signos de esa colección, estas colecciones tienen un inconveniente. Por ejemplo, alternar la fila 2 no tiene ningún impacto en la colección impar.
Entonces, pensemos en formar dos regiones como en el patrón del tablero de ajedrez. Como tenemos 4 interruptores en cada fila y columna, el número de interruptores del mismo color en cada fila o columna es dos, lo que nuevamente es par . Entonces, este proceso de pensamiento puede ser útil. La tabla completa se divide en dos regiones , ‘región blanca’ y ‘región verde’, como se muestra a continuación.
Podemos observar que
i) Cualquier cambio válido no cambia el producto de todos los signos de la región blanca
i) Cualquier cambio válido no cambia el producto de todos los signos de la región verde
Esto se ilustra con un ejemplo de alternar una columna en la siguiente figura.
La configuración de la izquierda de la figura anterior en realidad corresponde a la configuración inicial, que tiene un signo + en la región VERDE y un signo – en la región BLANCA .
La configuración final requerida de la parte b) (las cámaras 1, 2, 3, 4, 5, 6 y 7 están APAGADAS mientras que todas las demás están ENCENDIDAS) tiene un signo – en la región VERDE y un signo + en la región BLANCA como se muestra a continuación :
Como la región VERDE tiene diferentes signos en las configuraciones inicial y final y la región BLANCA también tiene diferentes signos en las configuraciones inicial y final, esta configuración final no se puede obtener después de cualquier número de días.
Este problema y solución se basan en el ‘ principio de invariancia ‘.
Cuando las cosas aparentemente cambian continuamente, busque qué valores centrales (aunque ocultos) no están cambiando.