Starting with the original problems, you can go in many directions. Here are just a few examples. If you use your imagination you will probably find may more!
Can you predict how many seconds a given configuration will take to settle down without actually carrying out the simulation?
Besides the worst case, consider the average time it takes for the recruits to settle down would be of interest.
What if you change the rules for what the each recruit does? For example, suppose he can see everyone in front of him and only turns around if more recruits are facing toward him than away from him.
How about two dimensions? Suppose there are 30 recruits arranged in a five by six rectangular pattern. What rules would be reasonable to expect our recruits to follow? What would happen if they start in random directions?
Start with a line of individuals facing forward and then tell them all to shake hands with their neighbors. At one second intervals, each person randomly moves to a direction of a handshake that hasn't happened yet. How long do you think it might take to finish this? One variation would be to start the people in a circle so that everyone has two neighbors. Also, you could start with a rectangular arrangement of people. In this two dimensional case, assume that adjacent means in front of, behind, to the left and to the right. Of course not everyone will have a neighbor in each of these directions.
Can you predict how many seconds a given configuration will take to settle down without actually carrying out the simulation?
Besides the worst case, consider the average time it takes for the recruits to settle down would be of interest. 
What if you change the rules for what the each recruit does? For example, suppose he can see everyone in front of him and only turns around if more recruits are facing toward him than away from him.
How about two dimensions? Suppose there are 30 recruits arranged in a five by six rectangular pattern. What rules would be reasonable to expect our recruits to follow? What would happen if they start in random directions? 
Start with a line of individuals facing forward and then tell them all to shake hands with their neighbors. At one second intervals, each person randomly moves to a direction of a handshake that hasn't happened yet. How long do you think it might take to finish this? One variation would be to start the people in a circle so that everyone has two neighbors. Also, you could start with a rectangular arrangement of people. In this two dimensional case, assume that adjacent means in front of, behind, to the left and to the right. Of course not everyone will have a neighbor in each of these directions.
