2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.