$101$ gunmen stand in a field. At high noon, everyone shoots the gunman standing closest to him. If there are several gunmen who are equally close, they shoot the tallest one of them. No two gunmen are the same height.
Prove that there will be a man left standing. In other words, prove that someone will not get shot.
Answer
Create a functional graph with an edge from each shooter to each victim. A source-free functional graph must be a disjoint union of oriented, possibly degenerate (i.e., 1- or 2-vertex) cycles. This one must contain at least one odd cycle because there are an odd number of vertices. And that cycle is not a 1-cycle because no gunman shoots himself. Call it $(v_0,v_1,\ldots,v_n,v_0)$.
Now either distance or height causes the $v_0$ gunman to prefer $v_1$ over $v_n$; the edge $(v_0,v_1)$ represents a distance no longer than that of $(v_0,v_n)$, and an analogous argument can be applied around the cycle. Thus, by transitivity, all edges represent equal distance. But then shots must have been decided by height, and $v_1$ is taller than $v_n$. Again, this argument can be carried around the cycle (twice because it depends on a relationship between vertices two edges apart, two fortunately not having any common factors with the cycle length) to conclude that all gunmen in the cycle are of equal height. But this contradicts the problem statement, so source-freeness is impossible.
No comments:
Post a Comment