Browse · MathNet
PrintBMO 2017
2017 counting and probability
Problem
We have students sitting at a round table. Initially each student is given one candy. At each step each student having candies either picks one of its candies and gives it to one of its neighbouring students, or distributes all of its candies to its neighbouring students in any way he wishes. A distribution of candies is called legal if it can be reached from the initial distribution via a sequence of steps. Determine the number of legal distributions. (All the candies are identical.)
Solution
The answer turns out to be if is odd and if is even.
Case 1. Suppose is odd, say . In this case we will show that any distribution of candies is legal. Thus the number of legal distributions is indeed .
In this case we can achieve the above claim by letting each student to always distribute all of its candies to its two neighbouring students in some way. Thus at each step each candy will move either one position clockwise or one anticlockwise.
We now look at the initial distribution of candies and the required final distribution. We specify arbitrarily for each candy in the initial distribution, the position we wish this candy to end up in the required final distribution. Because is odd, either the clockwise distance or the anticlockwise distance between the initial position of the candy and the required final position is even and at most .
Thus after an even number of steps (at most ) we can move each candy to its required final position. (Note that if the candy reaches the required position earlier, we can move it back and forth until all candies reach their required position.) This completes the proof of our claim in this case.
Case 2. Suppose is even, say . Let be the students in this cyclic order.
Observe that initially the students with even indices (even students) have at least one candy in total, and so do the students with odd indices (odd students). This property is preserved after each step.
We will show that every distribution in which the even students have at least one candy in total and the odd students also have at least one candy in total is legal.
Let us suppose that the required final distribution has candies in odd positions and candies in even positions. (Where .) It will be enough to reach any position with candies in even positions and candies in odd positions as then we can follow the same approach as in Case 1.
To achieve this we will first move all candies to students and . This is easy by specifying that at each step moves all of its candies to while for student moves all of its candies to .
Suppose that we now have candies at and candies at where without loss of generality . If we have reached our target. If not, in the next step moves a candy to and moves a candy to . In the next step (it still has candies) moves a candy to , moves a candy to and moves a candy to . We now have candies in and in . Repeating this process another times we end up with candies in and candies in as required.
It remains to count the total number of legal configurations in this case. This is indeed equal to as counts the total number of configurations while counts the number of illegal configurations where either all candies belong to the odd positions or all candies belong to the even positions.
Case 1. Suppose is odd, say . In this case we will show that any distribution of candies is legal. Thus the number of legal distributions is indeed .
In this case we can achieve the above claim by letting each student to always distribute all of its candies to its two neighbouring students in some way. Thus at each step each candy will move either one position clockwise or one anticlockwise.
We now look at the initial distribution of candies and the required final distribution. We specify arbitrarily for each candy in the initial distribution, the position we wish this candy to end up in the required final distribution. Because is odd, either the clockwise distance or the anticlockwise distance between the initial position of the candy and the required final position is even and at most .
Thus after an even number of steps (at most ) we can move each candy to its required final position. (Note that if the candy reaches the required position earlier, we can move it back and forth until all candies reach their required position.) This completes the proof of our claim in this case.
Case 2. Suppose is even, say . Let be the students in this cyclic order.
Observe that initially the students with even indices (even students) have at least one candy in total, and so do the students with odd indices (odd students). This property is preserved after each step.
We will show that every distribution in which the even students have at least one candy in total and the odd students also have at least one candy in total is legal.
Let us suppose that the required final distribution has candies in odd positions and candies in even positions. (Where .) It will be enough to reach any position with candies in even positions and candies in odd positions as then we can follow the same approach as in Case 1.
To achieve this we will first move all candies to students and . This is easy by specifying that at each step moves all of its candies to while for student moves all of its candies to .
Suppose that we now have candies at and candies at where without loss of generality . If we have reached our target. If not, in the next step moves a candy to and moves a candy to . In the next step (it still has candies) moves a candy to , moves a candy to and moves a candy to . We now have candies in and in . Repeating this process another times we end up with candies in and candies in as required.
It remains to count the total number of legal configurations in this case. This is indeed equal to as counts the total number of configurations while counts the number of illegal configurations where either all candies belong to the odd positions or all candies belong to the even positions.
Final answer
If n is odd: C(2n−1, n). If n is even: C(2n−1, n) − 2·C(3n−1, n).
Techniques
Invariants / monovariantsInclusion-exclusionCounting two ways