# How would I go about solving this tricky induction problem?

"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. 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."

So far, I think I should use n = 3 as the base case (not sure about any others) and then do the inductive step with n + 2 from the base case (all odd numbers I believe). My only problem is, how would I prove things like a cake not being thrown at a person and how could I apply this for odd numbers. And also, if I need one, how would I state the induction hypotheses?

Any help would be highly appreciated!

Base case $k=3$. There are $A, B, C$ people three pairs of people $AB, BC, AC$ and three distances between the pairs and the distance are all different. Let's label the distance and relabel the people so that the distance $d$ so that $d$ is the distance between the two closest people. We'll call the third person not in this pair $Z$. We'll call the person in this pair who is closest to $Z$ as $Y$ and say this distance $YZ$ is $e > d$. And other person in the pair is $X$ and the distance $XZ$ is $f > e=YZ > d = XY$. So $X$ throws the cake at $Y$ and $Y$ throws to cake at $X$ and $Z$ throws at $Y$. Noone throws at $Z$.

So the induction step. Suppose there are $k+2$ odd people and we know $k$ people will have one person uncaked. In the $k+2$ people remove the two people who are closest together. Of the remaining $k$ people if they were to toss cakes one would be uncaked. Call that person $Z$. Now add the two people we are closest together. Call them $A$ and $B$. They will cake each other. Everyone else will either cake the person they caked before, or they will cake one of these two added $A$ and $B$ if one of them is closer than the person they originally caked. What will not happen is that by adding $A$ and $B$ into the mix, $Z$ will somehow magically become closer than $Z$ was before. So if they didn't cake $Z$ before, they won't cake $Z$ now. So $Z$ remains uncaked.

Your method is correct.

1. From the rules of the cake battle it follows that a person $A$ will not be thrown a cake at if and only if for each person $B \neq A$ there is another person $C \neq B$ such that $d(B, C) < d(B, A)$ (where $d(X, Y)$ denotes the distance between $X$ and $Y$), so $B$ prefers to throw their bakings at $C$ rather than at $A$.

2. The odd number of people is hidden in the induction step being $n \mapsto n+2$ and base being $3$, so you don't have to worry about it while proving the step itself.

3. The induction hypothesis $\varphi(n)$ is as follows: for any arrangement of $n$ people such that all distances between two of them are distinct, there is a person that will be left intact after everybody has thrown their cakes (which is done in compliance with the rules of the event).

Hint to the inductive step:

From the arrangement of $n+2$ people try removing the two that are the least distance apart.