There is a group of N soldiers arranged in a straight line, standing side by side. Soldier number 1 is at the extreme left and soldier "N" is at the extreme right. Each soldier has a rifle that can be fired only once, a primitive timer, understands a finite list of commands, and can exist in a finite number of states, like a finite state machine.

Each soldier has the ability to communicate only with the two adjacent soldiers, and has no means of communication with more distant soldiers. The i-th soldier can not see or hear any signals given by the (i+2)th soldier, for example. There are no radios, cell phones, or megaphones.

Your mission as the commander is to devise an algorithm by which all soldiers fire their weapons simultaneously. Soldiers 1 and N are aware of the fact that they are "different" in that they each have only one neighbor. Other than that, however, the soldiers are initially all identical. The algorithm has to work for any value of N>2.

The primitive timers are synchronized and tick off once a second. Once a soldier receives new information, the earliest he can respond in any way is on the next tick of the clock. (I would say he/she, except that they are all identical). A soldier can give a signal to each neighbor simultaneously, based on the information he received one tick earlier. Whenever a soldier's state changes, his neighbors are aware of this one tick later. At time=0, soldier 1 is given the command to start the firing procedure

1. Devise an algorithm that results in all N soldiers firing simultaneously
2. As a function of N, how many clock ticks does this take?

I don't know if this solution works (I hope it follows all the rules – that I didn't make a mistake), and it most likely isn't the fastest solution, but here goes:

At time 0 the command I will give to solder 1 is:

Your rank is 1
If you have no neighbor to your left then
   Calculate X as 2 times your rank, minus 1 (X = 2N-1)
   Say to your neighbor "Fire at time" X "and repeat this message to your neighbors."

Else
   State your rank (so say "My rank is" R)
   Tell your left neighbor his rank (so say "Your rank is" R+1)
   Repeat the If/Else statement to this neighbor."

So this would mean that everyone would fire at time 2N-1 (in other words, it would take 2N-1 clock ticks for the firing to occur).

Basically, at time 1, Soldier 1 hears the instructions, and makes his appropriate statement. At time 2, Solder 2 hears the instructions and makes his appropriate statement. And so on until time N when Soldier N hears the instructions and makes the statement "Fire at time 2N-1 and repeat this message to your neighbors.

Then at time N+1, Soldier N-1 will hear this message and repeat it. At time N+2, Solder N-2 will hear this message and repeat it. (So generally speaking at time N+A, Solder N-A will hear and repeat the message). And so on until at time N+(N-2) (also known as 2N-2), Soldier N-(N-2) (also known as Soldier 2) hears this message and repeats it. So Solder 1 will hear the message at time 2N-2+1 = 2N-1 and will realize it's time to fire, and then will fire with everyone else.

I'm not sure if Solder 1 hearing the command "Fire at time 2N-1" actually AT time 2N-1 means he will have enough time to respond and fire with everyone else AT time 2N-1. If that doesn't count, then just change X to equal 2N. Then it would take 2N ticks for everything to happen.

(fixing formatting errors)

Edited on August 25, 2004, 2:08 pm

Posted by nikki on 2004-08-25 14:01:38