Solution

There are ten soldiers, an even number. The leader's plan is based on establishing parity.

The leader, being the last one in the column, can see the colour of the caps of all the nine (odd number) soldiers in front of him. Since there are an odd number of soldiers in front of him, there cannot be an even distribution of the red and black caps - there would be an odd number of soldiers wearing caps of one colour and an even number of soldiers wearing caps of the other colour. There cannot be an equal number of soldiers wearing caps of both colours. Thus, all the nine soldiers in front of the leader may be wearing red colour caps and none wearing a black colour cap, or there may be only one soldier wearing a black colour cap and all the eight others wearing red caps, and so on. Thus, if we represent the black cap wearers and red cap wearers as the ordered pair (black, red), then any of the following options would be possible: (0, 9), (1, 8), (2, 7), (3, 6), (4, 5), (5, 4), (6, 3), (7, 2), (8, 1), (9, 0). So, there would always be odd number of soldiers wearing one colour of cap and an even number of soldiers wearing the other colour.

The leader's strategy is to call out the colour of the cap which, say, has an odd number of wearers; he may call out the colour of the cap which has an even number of wearers if he chooses. But, whether the leader calls out the colour of the cap with an odd number or even number of wearers should be known to all beforehand. Let's say, for instance, that it has been decided to call out the colour of the cap with an odd number of wearers and everyone knows this. The leader calls out "Black" because he sees an odd number of his men wearing caps of that colour.

From there on, it becomes easy for the others to tell with certainty the colour of the cap they are wearing; they just have to keep in mind the colour called out by the leader, and track the changes as it keeps varying between odd and even. In this case, they have to keep track of "Black", while keeping in mind that odd + 1 (or - 1) = even (for example, 5 + 1 or 5 - 1 are both even).

Let's see how this works out. Let's have the following arrangement of caps. The colour of the leader's cap has not been indicated because he cannot identitfy the colour with certainty. He is marked "L" and stands at the tail of the queue and will be the first to call out the colour. The rest of the men are "A", "B", "C", "D", "E", "F", "G", "H" and "I". "I" stands at the head of the queue and will be the last to identify the colour of his cap. Let's have "A", "B", "F" and "H" wear red caps, and the others wear black caps. Of course, they don't yet know the colour of the cap they are wearing, but can see the colour of the caps of the men in front of them. "I", of course, has no one in front of him and, therefore, cannot seen anybody's cap. So, here is the arrangement:

The leader sees an odd number of black caps (five, in this case) and an even number of red caps (four) in front of him, and calls out "Black".

Every man knows that the leader has seen an odd number of black caps in front of him. So, initially, Black = odd.

After the leader, it is A's turn to identify the colour of his cap. "A" sees five black caps in front of him - an odd number; so, his cap has to be red. He says "Red".

Since "A" has called out "Red", there has been no change in the number of black caps. Thus Black = odd - 0 = odd.

"B", thus, knows that starting with him till "I" there are odd number of black caps. He also sees five (odd) black caps in front of him, so his cap also has to be red. He calls out "Red". There has, again, been no change in the number of black caps, so we still have Black = odd - 0 = odd.

It is now C's turn. "C" sees four black caps in front of him. Since the number of black caps is odd, his cap has to be black. He calls out "Black". Now, black caps have been reduced by one, so Black = odd - 1 = even. There are now an even number of black caps.

"D" realises that there are an even number of black caps now. He sees three black caps in front of him - an odd number. His cap is, therefore, black so as to get an even score. He calls out "Black". Black has further reduced by one, so now we have Black = even - 1 = odd; there are now an odd number of black caps starting with "E".

"E" realises this. He sees two (even) black caps in front of him. His cap, therefore, has to be black to get an odd number. He calls out "Black" . There is a reduction in the number of black caps here, so now we have Black = odd - 1 = even. So, starting with "F" there are an even number of black caps.

"F", having kept track of the reductions, knows this. He sees two black caps in front of him, an even number. So, his cap has to be red. He calls out "Red". There is no change in the number of black caps, and we have Black = even - 0 = even.

"G" knows, starting with him, there are an even number of black caps. He sees only one (odd) black cap in front of him. His cap, therefore, has to be black. He calls out "Black". There is a reduction in black caps, so now we have Black = even - 1 = odd.

"H" realises that starting with him there are an odd number of black caps. He sees one black cap in front of him (odd). His cap, therefore, has to be red. He calls out "Red". There has been no reduction in black caps, so Black = odd - 0 = odd.

"I" knows staring with him there are an odd number of black caps. However, he has no one in front of him. So, he must be wearing a black cap. He calls out "Black".

Did I get it right?