Ken's POTW


Firing Squad
N soldiers stand in a row, shoulder to shoulder, facing the same direction.

The first soldier on the right is the drummer. Every second, the drummer gives a beat, heard by all the soldiers. On that beat, the soldiers modify their state based solely upon their current state and the state of their nearest neighbors. (Perhaps the state of a soldier is noticeable by their posture, stance, or some other visual clue.)

Currently, all the soldiers are in a quiescent state, awaiting orders.

The first soldier on the left is the General. The General changes his state to give the command "Fire!" Each second, the command is passed on, perhaps in both directions as needed. Some time later, all N soldiers fire at the same time.
  1. How could this occur? I'm only looking for a theoretical answer here. What would the algorithm be to get them all to fire at the same time?
  2. Each soldier is an agent, with its own rules for state-changes. Obviously, the General and the drummer will have special rules, since they have only one neighbor, but the rest should share the same set of rules. Can you determine a rule set (a state machine) for the General, drummer, and soldiers? How many states are needed? Can the state machines work for any N?

Source: Homework problem in a CompSci Agents course at Stanford University, Fall, 1991.

Solution:
Received May 6, 1997 from Robert A. Pease (author of several Machine Design articles, including the April series "What's All This Puzzle Stuff Anyhow?" and "What's All This Solution Stuff Anyhow?"

[I haven't checked it completely but it seems to answer both questions above. I'd be interested if anyone does write a program to test this and if there are any discrepancies for particular values of N.] 
Hello, Ken, 
   Here's a solution to your PUZZLE with the General and the Drummer. 
I think this one's really easy. It reminds me of a dual-slope or 
triple-slope ADC.  
   
  THE GENERAL has to do some planning, before the time of the Attack, 
just as a real General does. See below. 

  The DRUMMER has to keep beating the drum, one beat per second, 
uniformly, or at the required rate. It would be wise if he keeps on 
beating all the time, even when there are no orders to be passed. 
(Although the general might arrange for a BACKUP who can substitute 
in so the Drummer can go to the John before his work becomes 
critical.) 
   The DRUMMER must also pass the ORDER on to his left or right, per 
the procedure as stated below for the men.  
   The INFANTRYMEN have simple tasks: 

   1. Pass the ORDER: If the man receives an ORDER on the left, he 
must pass it to the man on the right, on the next drum beat, for a 
delay of exactly one drum beat. If he cannot pass it to the right, 
because there is no-one there, he must pass it back to the left. (If 
he receives orders on the RIGHT, then VICE VERSA of above.)    
   2. Count. The first time he gets an ORDER, he must COUNT until he 
gets the ORDER back again. Then he must REMEMBER that count, N. 
   3. The THIRD time he gets the order, he must start counting DOWN 
from (N/2 + 1). When his count gets to ZERO, he must FIRE. (Note, if 
he whispers his countdown out loud, he can hear his comrades on each 
side, counting down just the same.)

   The GENERAL must send out the first ORDER at a suitable early 
time before the ATTACK. He must count the number of Drum beats M 
until he gets the ORDER repeated back, on the Left (ML) and on the 
Right (MR). He must remember these counts.  (an Odd number, each.)
   When he is ready to call an attack at time T, he must send out the 
ORDER to the left at a time t = T - ML/2 -1/2. He must likewise send out an 
ORDER to the right at a time t = T - MR/2 - 1/2. After that delay, 
everybody will fire at time = T.  (Option, everybody counts down from 
N/2 + 2) for best precision. Start sending out the orders to start firing        at t = T - M/2 -1.5 )
   It's hard to think of any procedure much simpler (or quicker) than 
that. Any good software writer could write that one. Even I could 
write that one - in BASIC.
    
   Best regards/ rap
Mail to Ken