Confused Soldiers

Question

A squad has $n$ soldiers. Their impatient commander yells at them to form a line going East to West, with everyone facing East. They quickly manage to form an East/West line, but some soldiers are confused, so some are facing East and some are facing West.

To remedy the situation, any soldier who sees the face of their neighbor assumes they were facing the wrong direction, and turns around. This takes one second. The same process happens every second until no two soldiers face each other.

What's the maximum length of time it will take for the soldiers to stop turning?

Answer 1

The following proof relies heavily on Lawrence's insight that we can think of the soldiers as swapping positions instead of turning around. However, I hope it is a bit more rigorous in terms of handling all possible cases. I also think it differs enough from Mike Earnest's solution to be worth posting.

---

Assume soldiers march passed each other instead of turning around. So the east facing soldiers stay east facing and slowly march east, and the west facing soldiers stay west facing, and slowly march west. We will prove this by induction on $n$.

Let Brittney (good soldier name!) be the west facing soldier farthest to the east, and let Adam be the west facing soldier next farthest to the east. Consider an alternate dimension where Brittney is removed from the line. Once all the east facing soldiers pass Adam in the line, then the whole thing is over. By induction, this takes at most $n-2$ seconds.

Going back to reality, let's assume Brittney is in the line. We see that Brittney doesn't really affect anything that is happening west of Adam, and therefore it will still take at most $n-2$ seconds for all the east facers to pass Adam. We then just have to wait for all those east facers to pass Brittney. How long will that take? Well, there are really only two cases to consider.

1. If at some point Brittney is right behind Adam, then she must stay pretty close to Adam. Adam may move one step forward while she stands still, but then she'll either keep pace with Adam or catch up. So there will be at most one east facer between her and Adam from then on. Therefore, once all the east facers have passed Adam, there is at most one east facer that needs to pass Brittney. This gives an upper bound of $n-2 + 1 = n-1$ seconds.

2. If Brittney never catches up to Adam (or if there is no Adam at all!), she'll spend the whole time moving forward. This clearly will take at most $n-1$ seconds to resolve.

Answer 2

Treat each soldier as a binary digit, $1$ if facing east and $0$ if facing west, and order them from west to east (i.e. left to right). We start off with a random $n$-digit binary number, and the algorithm is:

every time $10$ appears in the number, replace it by $01$.

The process can only end when the number is a string of $0$'s followed by a string of $1$'s, i.e. it is one less than a power of two. Its digit sum remains constant throughout.
The optimal initial state is a string of $1$'s followed by a string of $0$'s. The $10$ at the gap 'propagates' out in both directions simultaneously and then back again once it has reached the end. To demonstrate (with $n=9$):

$111110000$
$111101000$
$111010100$
$110101010$ (right end reached)
$101010101$ (left end reached)
$010101011$
$001010111$
$000101111$
$000011111$

With $n=10$:

$1110000000$
$1101000000$
$1010100000$ (left end reached)
$0101010000$
$0010101000$
$0001010100$
$0000101010$ (right end reached)
$0000010101$
$0000001011$
$0000000111$

It's now clear that the answer is

$n-1$ seconds.

To prove this, say we start off with $m$ ones followed by $k$ zeros (so that $m+k=n$). It takes $m$ steps to turn the leftmost digit into a zero, $k$ steps to turn the rightmost digit into a one, and $min(k,m)-1$ steps to reach the desired end state after both of these have been achieved, giving a total of $m+k-1=n-1$ steps.

Answer 3

A series of variants of this puzzle came up in one of the trade magazines - possibly Communications of the ACM.

When two soldiers face each other, they are required to turn around. Assuming the soldiers are considered to be interchangeable, this is equivalent to the soldiers marching 'through' each other (or swapping positions, if you prefer).

In this formulation, the worst case would require a soldier at one end to march all the way to the other end, e.g. when the $n/2$ soldiers on the West end face East, and the others face West.

This requires $n-1$ moves.

Answer 4

Though it could use a bit of further justification, my answer is:

$n-1$ seconds

I say this purely based on brute force for the first five or so values of $n$. Essentially the worst case as far as I can tell occurs when

All soldiers are facing the same way - say east, except for the one that is at the end to which the rest are facing. This soldier would face the opposite way.

To demonstrate, lets say $n=4$ solders, you would get the following sequence:

t=0: > < < <
t=1: < > < <
t=2: < < > <
t=3: < < < >
(where '>' is a soldier facing east, and '<' is a soldier facing west)

You can extend that sequence for any value of $n$ meaning that the maximum time the sequence could go on for must be at least my answer in terms of seconds.

Whether or not this is the true maximum I believe it is, but I could be wrong. It would be good to see a formal proof or anyone that finds a sequence that lasts longer.

Answer 5

The hard part of this puzzle is proving that every configuration stabilizes after $n-1$ seconds.

Numbering the soldiers $1$ to $n$ from west to east, let $E(k)$ be a function which counts the number of East facing soldiers among soldiers $1$ through $k$. Define $W(k)$ similarly. This means $W(k)+E(k)=k$. Then, let $$ f(k) = W(k) - E(k) $$ For example, below is a potential soldier line (> means facing east, < west), followed by the resulting graph $f(k)$. Though $f$ is only defined for integers, I've connected the graph of $f$ with straight lines.

Two observations: first, the number of west (east) facing soldiers doesn't change over time. Call these numbers $W$ and $E$. It will always be true that $$ -E\le f(k)\le W \tag1 $$ Secondly, the function $f(k)$ has a "valley" whenever there are two soldiers facing each other. To be precise, a valley is a point on the graph $(k,f(k))$ where $f(k-1)=f(k+1)=f(k)+1$. The valleys are colored above.

Let's see what happens to the graph $f(k)$ after one second:

Notice that all of the valleys got flipped up to be peaks. Since the passage of time raises valleys, it follows that the height of the lowest valley increases over time. We will use this quantity to prove the desired upper bound.

In light of these observations, at any time $t$ where the configuration is unstable, let $h(t)$ be the height of the lowest valley, so $h(t) = \min_{0\le k\le n} \{f_t(k):(k,f_t(k))$ is a valley$\}$. This means $h(t)$ is undefined if there are no valleys, though the only configuration with no valleys is the final one.

Then $$-E\le h(t)\le W-2.$$ The lower bound follows from (1). To get the upper bound, consider the graph one second later. If there is was a valley at height $h(t)$, then one second later, there will be a peak at height $h(t)+2$. Using (1), we see that $h(t)+2\le W$.

Since there are $n-1$ numbers in the range $\{-E,-E+1,\dots,W-2\}$ (recalling that $E+W=n$), it follows that $h(t)$ can take at most $n-1$ values while the soldiers are unstable. Since $h(t)$ must increase as $t$ increases, after $n-1$ seconds, we can be sure the soldiers are stable.

Finally, we know there are arrangements which do take this maximum time of $n-1$ seconds (for example, when the westmost soldier faces east, and all others west).