The soldier riddle

[Studente Anonimo]

The following problem is taken from Peter Mann Winkler's book "Mathematical Puzzles: A connoisseur's collection".

Enjoy

[Principe2]

That's exactly the kind of solution I was thinking of while being at the grocery store!

[Rigel1]

Let us consider the two soldiers \(A\) and \(B\) at the minimal pairwise distance. Clearly \(A\) is watching \(B\) and \(B\) is watching \(A\). If nobody else is watching \(A\) or \(B\), we remove both soldiers from our set of soldiers.
We repeat this process until it is possible to remove such pairs of soldiers.
At the end we remain with an odd number of soldiers; it is clear that this number must be \(\geq 3\).
So we have the two soldiers \(A\) and \(B\) at the minimal pairwise distance, and there is (at least) a third soldier \(C\) which is watching \(A\) or \(B\). Since the number of "arrows" (an arrow goes from \(D\) to \(E\) if \(D\) is watching \(E\)) is equal to the number of soldiers, and there is at least one soldier (\(A\) or \(B\)) with at least two ingoing arrows, then there is at least one soldier without any ingoing arrow.

[Studente Anonimo]

"Valerio Capraro":the distance is symmetric, so, if $A$ watches $B$, then $B$ watches $A$ as well.

False: take for example the case in which A,B,C lie on the same line and [tex]d(A,B) = 2[/tex], [tex]d(B,C)=1[/tex]. Clearly A watches B but B watches C.

[Principe2]

Closest soldiers watch to each other!

More formally:

A) the distance is symmetric, so, if $A$ watches $B$, then $B$ watches $A$ as well.
B) the distances are pairwise distinct. Therefore, if $A$ watches $B$, then he can't watch anyone else.

Conclusion: one can group pairs of soldiers if they watch to each other. Since the number of soldiers is odd, there is at least one soldier out of this grouping; i.e. not being watched.