4. There is an odd number of people standing in a field. Each person is a different distance away from each other, i.e. there is a unique distance between each person. At precisely the same time, each person flops out a water pistol and shoots and hits the person nearest them. Prove that at least one person will not be shot.
Suppose each person was shot. Draw an arrow from A to B if A shot B. Let n be the number of people. As there are n people and n arrows, that means that each person must have gotten show by a unique person. Let us now look at the connected components of this graph(network). Clearly it can't be the case that each connected component contains 2 people, as otherwise there's an even number of people in total. So consider a connected component with at least three people. Say P1 shot P2 and let Q be a third person in this connected component, clearly P2 couldn't have shot P1 as otherwise P1 and P2 forms a connected component (this is by the uniqueness of murderers for each person) and then Q can't be there. Hence P2 shoots some other person P3 (not P1). So far we have:
P1 -> P2 -> P3
Now P3 didn't shoot P2 since P1 shot P2 (again using uniqueness of murderer) hence P3 must've shot some other person... continuing in this way we form a sequence
P1 -> P2 -> P3 -> ...
eventually it must terminate, and the only way it can is if we eventually hit P1. Hence we have a cycle. Now let d(A,B) denote the distance between A and B, notice that:
d(P1,P2)>d(P2,P3)
since otherwise P2 would have show P1 instead of P3. Continuing in this way we see that as you follow the arrows, the distance d(Pn,P(n+1)) keeps getting smaller (strictly smaller since distances are unique) but this is a contradiction since once you make a full cycle this distances should repeat.
Home
Help
Search
Login
