Solución del problema de Marzo del 2004

Esta es la forma en que los semáforos funcionarían si los matemáticos estuvieran encargados de ellos. Los colores rojo, amarillo y verde de un semáforo están controlados por tres switches con 3-posiciones. Las tres posiciones de cada switch están marcadas con 0, 1, y 2, y los switches siguen dos reglas:

  1. El color de la luz que se muestra depende solamente de las
    posiciones de los switches.
  2. Si usted cambia las posiciones de los tres switches al mismo tiempo, entonces el color de la luz cambia.


Al principio la luz del semáforo es roja y todos los otros switches
están en la posición 0.

Switch A

Switch B

Switch C


Usted cambia el switch A a la posición 1, y la luz cambia a amarilla.

Switch A

Switch B

Switch C


¿ Qué pasa si ahora mueve el segundo switch a la posición 2?

Switch A

Switch B

Switch C


Mas generalmente, explique cual posición de los switches corresponde a que color de la luz del semáforo.

Este problema del mes esta basado en un problema básico publicado en “ Graph Products, Fourier Analysis, and Spectral Techniques,” por Alon, Dinur, Friedgut, and Sudakov.

 

Solución de MP40

Recibimos soluciones de Pierre Bornsztein (Francia), Gilles Feyrit (Francia), Wolfgang Kais (Alemania), Patrick LoPresti (Estados Unidos), Antoine Merle (Francia), y Juan Mir Pieras (España).  La respuesta es

Las luces permanecen amarillas cuando se cambia el segundo switch a la posición 2! El color de la luz depende solamente de la posición del primer switch.

Este problema del mes pudiera explicar porque se necesitan tantos matemáticos para cambiar una bombilla eléctrica.

Las soluciones enviadas solo se diferencian en notación. Bornsztein y Kais discutieron el problema en términos de una gráfica que tiene 27 vértices denotados por ABC: Cada A, B y C representan 0, 1 o 2, donde A es la posición del primer switch, B del segundo, y C del tercero. Dos vértices de la gráfica están conectados por una arista cuando sus vértices son diferentes en sus tres componentes. El uso de gráficas hace que algunas relaciones sean más fáciles de establecer, pero no parece simplificar la solución. Enlistamos los 27 estados y ponemos una X en la columna de cualquier color que es eliminado por la regla 2. Empezamos con 000 – el estado inicial, en el cual todos los tres swiches están en posición 0 – teniendo una R en la columna roja, y 100 con una Y en la columna amarilla.

Por la regla 2, un estado con un dígito no-cero en todos los tres lugares se le asigna una X en la columna roja – estas no pueden corresponder a una luz roja. Similarmente, aquellos estados con un número diferente del 1 en el primer lugar y un dígito no-cero en los otros dos se le asigna una X en la columna amarilla. Aquí esta entonces nuestro estado inicial conocido:

R

Y

G

 

R

Y

G

 

R

Y

G

000

R

    

100

  

Y

  

200

      

001

      

101

      

201

      

002

      

102

      

202

      

010

      

110

      

210

      

011

  

X

  

111

X

    

211

X

X

G

012

  

X

  

112

X

    

212

X

X

G

020

      

120

      

220

      

021

  

X

  

121

X

    

221

X

X

G

022

  

X

  

122

X

    

222

X

X

G

Tabla 1

Ya que 211, 212, 221, y 222 no pueden ser ni rojo ni Amarillo, estos estados deben producir una luz verde; esto es, a ellos se les asigna una G en la columna verde.

Tenemos ahora cuatro estados verdes conocidos 2BC; cada uno de estos nos permite deducir que muchos estados no pueden ser verdes, a saber 0(B ± 1)(C ± 1) y 1(B ± 1)(C ± 1), donde las sumas son reducidas módulo 3. En efecto estos son todos los estados que empiezan con 0 o con 1 – concluimos que cualquier estado que empieza con 0 o 1 no pueden ser verde.

R

Y

G

 

R

Y

G

 

R

Y

G

000

R
X

100

  

Y
X

200

      

001

  
X

101

    
X

201

      

002

  
X

102

    
X

202

      

010

  
X

110

    
X

210

      

011
R

X
X

111

X
Y
X

211

X

X

G

012
R

X
X

112

X
Y
X

212

X

X

G

020

  
X

120

    
X

220

      

021
R

X
X

121

X
Y
X

221

X

X

G

022
R

X
X

122

X
Y
X

222

X

X

G

Tabla 2

Esto nos permite concluir que 011, 012, 021, y 022 deben representar rojo, y 111, 112, 121, y 122 representan amarillo.

            Nuestro nueva información nos permite deducir que cualquier triple que empieza con 1 o 2 no puede ser rojo (ya que 100, 102, y 120 son diferentes de 011 y todos los tres lugares, mientras que 101 y 110 son diferentes del 022 in todos los tres lugares, y  lo mismo con 200, 202, 220, 201, y 210).  Similarmente, cualquier triple que empieza con un 0 o 2 no puede ser amarillo. Esto nos lleva a la conclusión

Si el primer switch esta en la posición 0 la luz será roja, si la posición es 1 la luz será amarilla, y si la posición es 2 la luz será verde.

En particular, cuando el segundo switch se mueve a la posición 2 del estado 100, la luz permanece amarilla.

            Gilles Feyrit notó que hay una simetría que nos permite una conclusión más general. Lo que en realidad hemos demostrado es que tan pronto como sabemos los dos estados que corresponden a diferentes colores y aún mas, estos estados son diferentes en la posición de un switch mientras que coinciden en los otros dos, entonces sabemos que solamente el switch diferente controla los colores. Por ejemplo, si hubiéramos sabido solamente que 211 y 200 ambos corresponden a verde, entonces habríamos necesitado mas información. De la misma manera, de habernos dicho que 211 es verde mientras que 110 es amarillo no sería suficiente. El enunciado del problema de Aon et al. era más general. Permite para cualquier número de switches controlar los colores rojo-verde-amarillo para un semáforo de 3-posiciones.

Se le ha dicho que siempre que las posiciones de todos los switches sean cambiados entonces el color de la luz cambia; uno puede entonces probar que, en efecto, la luz es controlada por solamente uno de los switches. Aparentemente este fue un problema de origen desconocido que circuló en Hungría en los 70´s.