Cake Induction problem

Question

A crowd of at least two people stands in a room and each one holds a cake. At the sound of a whistle, each person throws their cake at the person closest to them. (Before you ask: no one throws cake at himself.) If the number of people in the crowd is odd, then there is someone who does not get a cake thrown at them. Prove this. Assume that all the distances between pairs of people are distinct.

Answer 1

Consider $n \geq 3$ odd.
For a person x, let d(x) be the distance to the closest person, and number the person $x_i$ in increasing order of d ($x_1$ and $x_2$ being the closest, and if two people have the same value of d it does not matter how you number them relatively).
For $i \in \{2,3,...,n-1\}$, we cannot have $d(x_{i-1})=d(x_i)=d(x_{i+1})$
Since n is odd:
1) Either there exists $i \in \{2,3,...,n-1\}$ such that: $d(x_{i-1})<d(x_i)<d(x_{i+1})$, and let m be the maximum m of such i. $x_m$ does not get a cake thrown at him.
2) Or $d(x_{n-1})<d(x_n)$ and then $x_n$ does not get a cake thrown at him.

Answer 2

We will prove this fact by contradiction. Assume we have some configuration of $m$ people, with $m > 1$ odd, such that everyone gets hit by a cake. Assume we chose this configuration so that $m$ is as small as possible.

The first observation is that, since there are only as many cakes as there are people, if everyone gets hit by a cake, everyone gets hit by exactly one cake. (Why?) The second observation is that there is a pair of people that throw cakes at each other: for example, you can look at the pair whose distance is the smallest among all the distances between people.

Given those two observations, we can see that, if we remove those two people (the people who throw cakes at each other) from the configuration, no one else changes who they throw cakes at. That is because that pair wasn't the target of anyone else's cakes (remember everyone gets hit by exactly one cake), so the "closest person" didn't change for anyone.

After removing this pair, we have a new configuration with an odd number of people. If the new configuration has only one person left, we have a contradiction: who threw the cake that hit that person? Otherwise, we have a configuration with an odd number of people, more than one, where everyone gets hit by a cake, contradicting that $m$ was the smallest possible size of such a configuration.

Answer 3

S is a set with an odd number of people such that different pairs of people have a different distance. Find the pair x,y with the minimum distance. x throws to y and y to x in S. The number of people of T:=S{x,y} is odd, too, so there is a z in T such that nobody throws at z with respect to T (induction). Therefore nobody will throw at z with respect to S. Maybe there is an u that throws at v with respect to T but throws at x with respect to S, but that does not change anything for z.