A problem from the 2002 Moscow Mathematical Olympiad:
A group of recruits stand in a line facing their corporal. They are, unfortunately, rather poorly trained: At the command “Left turn!”, some of them turn left, some turn right, and some turn to face away from the corporal. Is it always possible for the corporal to insert himself in the line so that an equal number of recruits are facing him on his left and on his right?
Yes. When the corporal has taken a place in the line, let l denote the number of recruits to his left and facing him, and let r denote the number of recruits to his right and facing him.
If the corporal takes the leftmost place in line, then there’s no one to his left (l = 0). If no one to his right happens to be facing him either, then the problem is solved. Otherwise r > 0. Now suppose the corporal moves gradually rightward, one position at a time. If he passes a recruit who is facing right (that is, whose back had been to him), then l increases by 1 and r doesn’t change. If he passes a recruit who’s facing left, l doesn’t change and r decreases by 1. And if he passes a recruit who’s facing the back of the parade ground, then neither l nor r changes.
Now consider what happens to the difference l – r as the corporal moves along the line. At first it’s negative (because r is positive and l is 0). As the corporal moves down the line, l – r changes by at most 1 as he passes each soldier. When he reaches the right end of the line, r will be 0 and so l – r will be nonnegative. So we’ve started with a negative number, set it increasing and decreasing by 1 several times, and arrived at a nonnegative number. At some point, then, the difference must have been 0. At that moment l = r, and the corporal has an equal number of soldiers facing him on both sides.
