On a circular table sit $\displaystyle {n> 2}$ students. First, each student has just one candy. At each step, each student chooses one of the following actions: (A) Gives a candy to the student sitting on his left or to the student sitting on his right. (B) Separates all its candies in two, possibly empty, sets and gives one set to the student sitting on his left and the other to the student sitting on his right. At each step, students perform the actions they have chosen at the same time. A distribution of candy is called legitimate if it can occur after a finite number of steps. Find the number of legitimate distributions. (Two distributions are different if there is a student who has a different number of candy in each of these distributions.) (Forgive my poor English)
Problem
Source:
Tags: combination, algebra
04.05.2017 17:35
It was proposed by Cyprus .
04.05.2017 21:25
I hope this is correct. What do you think? : First, kid = student, configuration = distribution. Here we go: For n odd all the distributions are possible so a total of ${2n-1}\choose {n-1}$ distributions (since it's the number of ways you can write n as sum of n non-negative integers) For n even all the distributions are possible except the ones that have 0s in all even position or all odd positions. That would make a total of ${2n-1}\choose {n-1}$ $- 2$ ${n+\frac{n}{2}-1}\choose {\frac{n}{2}-1}$ distributions. For n odd I will prove by induction that from any initial distribution with $k\leq n$ candies we can arrive at any other distribution with $k$ candies: For $n=3$, the only distribution harder to achieve is for $k=3$: 3 0 0 which comes from 2 1 0 by moving the 2 and the 1 to the 3rd position by using b). Also, 2 1 0 comes trivially from 1 1 1 using a). Now suppose "everything works" for n and we I will prove for n+2: We have a configuration with sum k and we want to arrive at another configuration with sum k (I will call it final configuration) Label the positions with numbers form 1 to n+2. It is not that hard to see that we can make positions n+1 and n+2 in the final configuration identical to the ones in the starting configuration. Using the induction hypothesis we can solve for positions 1 to n. The only problem is that we need to able to apply a) and b) as if positions n and 1 would be next to each other without changing the values in n+1 and n+2. This can be done by as follows: Between every step given by the induction hypothesis we insert two more steps: -In both steps the kids in positions (n, n-1), (n-2, n-3), (n-4, n-5),.... swap their values (using (B) ) -In the first step the kids in position the kids (n+2, n+1) also swap their values -In the first step the kid 1 (who is the only one we didn't give something to do in the first step) gives all the candies to 2. -In the second step the kid 2 returns the candies from 1 and gives the other candies back to 3. -In the second step the kid n+1 gives the candies n+2 received form 1 before the first step to n and the kid n+2 gives the candies n+1 received form n before the first step to 1. By doing all this stuff we created a "bridge" between the kids n and 1 so we are all right. Finally, if in the end the kids (n+1, n+2) don't have the correct values (they are swapped because of the parity of the number of steps we made) we can add two more steps to swap them back: -In the first step n+1 gives his candies to n+2, n+2 gives one candy to n+1 -In the second step n+2 gives the right amount of candies to n+1 and n+1 give that 1 candy back to n+2 -1 to n can remain unchanged by using the same strategy we used before. This will swap n+1 and n+2 unless together they have a total of one candy. But in that case we could have chosen n+1 and n+2 (by rotating the table) so that in the final configuration they have either 0 or at least 2 candies. This can be done unless the final configuration is 0, 1, 0, 1,.... but this requires n to be even (false) We conclude that for n odd we can obtain any configuration. For n even we do the same thing just that in the base of the induction for n=2, k=2, from the configuration 1 1 we cannot obtain 2 0 (or vice-versa). which will result in the all the configurations being obtainable except for the ones that have 0s in all the even positions or 0s in all the odd positions. Sorry for all the typos!
04.05.2017 21:40
The proposer is Demetres Christofides. (Demetres here in Aops)
04.05.2017 22:17
What a masterpiece! Amazing problem, congrats to Demetres!
05.05.2017 02:27
Snip long quote. Thank ioanandrei.
08.05.2017 18:43
21.10.2017 01:18
what if each student just can do first move? or just second?
19.01.2025 17:26
I wont forgive your english