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
