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?

(In reply to More Information by Larry)

Larry, thank you for the clarification. I still have one question though. Is there a difference between "hearing a response" and "becoming aware of your neighbors change of state"? The reason I ask is because of the statement:

"Whenever a soldier's state changes, his neighbors are aware of this one tick later"

Even knowing that the communication follows scenario B, this statement still causes confusion. Here are some interpretations I had. I’m sorry for being so picky, but otherwise I know I’ll go down the wrong path.

Scenario X:

T+0: Soldier 1 says "Do what I do, and repeat this message to your neighbor." Soldier 1 turns around. Soldier 2 hears this command, but is unaware of Soldier 1’s change of state.

T+1: Soldier 2 says "Do what I do, and repeat this message to your neighbor." Soldier 2 is now aware of Soldier 1’s change of state but can’t act on it yet because he just got this information. Soldier 3 hears the command.

T+2: Soldier 3 says "Do what I do, and repeat this message to your neighbor." Soldier 2 turns around, but Soldier 3 is unaware of Soldier 2’s change of state. Soldier 4 hears the command.

T+3: Soldier 4 says "Do what I do, and repeat this message to your neighbor." Soldier 3 is now aware of Soldier 2’s change of state but can’t act on it yet because he just got this information. Soldier 5 hears the command.

T+4: Soldier 5 says "Do what I do, and repeat this message to your neighbor." Soldier 3 turns around, but Soldier 4 is unaware of Soldier 3’s change of state. Soldier 6 hears the command.

In this one, information gets passed on twice as fast as awareness&response to state changes. This is because a Soldier can hear information in the same tick, and must wait a tick to act on said information. But when a neighbor’s state changes, it takes the Soldier a tick to become aware of it, and then another tick to act on it.

Scenario Y:

T+0: Soldier 1 says "Do what I do, and repeat this message to your neighbor." Soldier 1 turns around. Soldier 2 hears this command, but is unaware of Soldier 1’s change of state.

T+1: Soldier 2 says "Do what I do, and repeat this message to your neighbor." Soldier 2 is now aware of Soldier 1’s change of state and turns around. Soldier 3 hears the command, but is unaware of Soldier 2’s change of state.

T+2: Soldier 3 says "Do what I do, and repeat this message to your neighbor." Soldier 3 is now aware of Soldier 2’s change of state and turns around. Soldier 4 hears the command, but is unaware of Soldier 3’s change of state.

This one seems like passing information and being aware of/responding to state changes are the same, but they are a little different. A Soldier hears information in the same tick, but must wait a tick to respond to it. But for state changes, a Soldier must wait a tick to become aware of it, but can act on it in the same tick.

I probably will never get the answer, but I know I won’t get it if I stay confused =)

Posted by nikki on 2004-08-27 13:57:42