I still don't get it because for me the minimal time is n.
The general pass a note with the value n to the firts squad, which decrease it by one and pass it to the next squad, etc.
If passing the note to the next squad is performed at each clock beat and each suqad decrements the value he got, then they will all reach 0 at the same time.
I guess I'm missing some constrains because I don't see why I don't get 2n-2 as minimal time.
IIUC the idea is that they want a fixed number of states, that doesn’t depend of n.
Another idea is that nobody knows the exact value of n, so the first task of the soldiers is to count themselves. Then the idea is that a signal propagates form one end of the line to the other end and back, and the time is ~2n. Using two signals that propagate with different velocities they can “count” with a finite number of states.
For example, see the fist graphic “Anonymous, 3n time, 160 soldiers, 13 states” in http://www-cs-faculty.stanford.edu/~eroberts/courses/soco/pr... . They first find the middle of the line, and hen they continue doing binary partitions until all the partitions have length 1, and then they fire. The final step is local, each one has to check that they local partition has length 1 and the nearby partitions have length 1, but the binary split is responsible for making all the partitions of roughly the same size.
