Let be a positive integer. There are towns arranged on a East-West road. Each town has two rhinoceroses, one heading East from the town, and the other heading West from the town (rhinoceroses cannot turn into another direction.) These rhinoceroses all have different sizes. When two rhinoceroses confront face to face, the larger one would knock the smaller one out of the road. However, if a rhinoceros is bumped by another from its rear end, the bumped rhinoceros is knocked out of the road, regardless of their sizes.
Let and be two towns, with being East to . We say that tramples , if the East-heading rhinoceros of can reach by knocking off all rhinoceroses in between. Similarly, we say that tramples if the West-heading rhinoceros of can reach by knocking off all rhinoceroses in between.
Prove that these is exactly one town that would not be trambled by any other town.
Solution
We induct on . When the claim is obviously true.
Suppose the original claim holds for all . When , apart from the West-heading rhinoceros of the westernmost town and the East-heading rhinoceros of the easternmost town (which have no function), consider the largest among the remaining rhinoceroses; without loss of generality, suppose the largest rhinoceros is the East-heading rhinoceros of the -th town counted from the west, where (since we do not consider the East-heading rhinoceros of the easternmost town).
Clearly, all towns east of the -th town will be trampled by the -th town; and none of the towns east of the -th town can trample the -th town or any town to its west, since they are all blocked by this largest rhinoceros. Therefore we may discard all the towns east of the -th town. Since , by the induction hypothesis, among the remaining towns there is exactly one that is not trampled by any other town, which completes the proof.