One way to solve the problem is to have the excited state shoot out two projectiles, one of which moves at speed 1 and one of which moves at speed 1/3. If the speed 1 projectile is made to bounce off the row's end, these projectiles will meet in the middle of the row. The row can then be bisected, and this bisection step can be repeated to quadrisect, 8-sect, etc., the row. When all these segments vanish (which will happen simultaneously), the soldiers should enter their firing state.

Here
is such a solution, with 13 states, and
here is an illustration of the solution running for
20,
40,
80,
and
160
soldiers. (In these pictures, and all succeeding pictures, the
quiescent state is black, the excited state is yellow, and the firing
state is white.)
Bisecting a row of length N by this method
will take around *3N/2* time steps, so the whole solution will take
about *3N/2+3N/4+...=3N* time steps.

How little time can a solution take? It takes *2N-2* time steps
just for a signal to pass from one end of the row to the other and back,
so any solution must take at least this much time. In fact there are
solutions that take just *2N-2* time steps.
Here
is a minimal-time solution by
Abraham Waksman (Information and Control 9 (1966), 66-78), and
here are runs of it for
48,
96,
192,
384,
and
768
soldiers.

Waksman's solution uses 16 states. Here is a minimal-time solution with 11 states (David Karr, 1999) and runs of it for 20, 40, 80, and 160 soldiers; and here is a minimal-time solution by Robert Balzer with 8 states (Information and Control 10 (1967), 22-42) and runs of it for 20, 40, 80, and 160 soldiers. Finally, here is a minimal-time solution with just six states by Jacques Mazoyer (Theoretical Computer Science 50 (1987), 183-238), and runs of it for 40, 200, 500, and 1000 soldiers.

Obviously, any solution must have at least three states; in fact, it is known (see Balzer's paper) that any minimal-time solution must have at least 5 states. It is not known whether there exists a minimal-time solution with exactly 5 states.

Back to the home page

David Moews ( dmoews@fastmail.fm )

Last significant update 20-IX-2004