riddle of the day

Under its everyday appearance, this problem is an exercise in logical precision. It all depends on reading the rules carefully and not losing track of what happens step by step.

The traffic light that reprograms itself

Curious
Pure logic

Riddle statement

An experimental traffic light has three lights: red \(R\), yellow \(A\) and green \(V\). Each light is worth 1 if it is on and 0 if it is off.

Every minute it is updated with this rule: the red one takes the value of \(\neg A\) (that is, the opposite of \(A\): if \(A=0\), it goes to 1; if \(A=1\), it goes to 0), the yellow one takes the previous value of \(V\), and the green one takes the previous value of \(R\).

If you start at \((R,A,V)=(0,0,0)\), at what minute does that exact same state first appear again?

Show solution

Solution

Answer: minute 6.

The update rules are:

$ R_{t+1}=\neg A_t,\quad A_{t+1}=V_t,\quad V_{t+1}=R_t. $

Applying them from the initial state \((R,A,V)=(0,0,0)\):

  • \(t=0\): \((0,0,0)\)
  • \(t=1\): \((1,0,0)\)
  • \(t=2\): \((1,0,1)\)
  • \(t=3\): \((1,1,1)\)
  • \(t=4\): \((0,1,1)\)
  • \(t=5\): \((0,1,0)\)
  • \(t=6\): \((0,0,0)\)

The first repetition of the initial state occurs at \(t=6\).