Six nervous young recruits stand in a single line for their first
drill session. They face the gruff drill sergeant, who barks out
their first order—"Left Face"—and in one second they do
this:
Oops! Not all of them got it right. But what
now? All of the recruits are nervous. When two soldiers
see that they are face to face, they both
assume they are wrong and (in exactly one second!) turn the other
way. After one second, the soldiers look like this:
Each second, they react the same way. The sergeant rolls
his eyes and decides to wait for them to settle down before giving
another order. How long will it take before that next order can
be given? What if a different recruit—say one at the end of the
line—turns right instead of left? How long could it take? What
initial setups take the longest to settle down? What
if more than one recruit turns the wrong way? Is it possible to
predict the final configuration just by looking at
the starting position? What if there are 10 recruits? Or
just 3? How would your answers to the previous questions change,
depending on the number of recruits?