Bizarre Candy Rationing

Number Theory Level pending

A group of $n \geqslant 3$ children are standing in a circle. They all start with a multiple of 3 candies each (not necessarily equal), and perform the following algorithm:

Step 1. Each child divides their candies equally into 3 piles. Proceed to step 2.

Step 2. Each child gives 1 pile to the person on their left and 1 pile to the person on their right. Keep the last pile. Proceed to step 3.

Step 3. Each child now counts the number of candies they have.

If it's not a multiple of 3, grab candies from the candy bag one by one until it becomes a multiple of 3 and proceed to step 4.

If it's already a multiple of 3, do nothing and proceed to step 4.

Step 4. At this point, if everyone has the same number of candies, stop, or else, repeat from step 1.

Assuming they have an infinite supply of candies from the candy bag, will this algorithm ever end?

Yes No It will end only for some values of

n

It depends on the number of candies each child has

1 solution

Kenneth Tan
Dec 8, 2016

Suppose in one of the iterations, among all children, those who have the most candies have $3M$ candies, and those who have the least candies have $3L$ candies.

Here are 2 facts to fill our tummies!

First, the maximum number of candies that anyone can have in future rounds is capped at $3M$ .

This can be shown as follows: Take any 3 adjacent people, assume they have $3(M-m_1)$ , $3(M-m_2)$ , $3(M-m_3)$ candies, here, $0\leqslant m_1, m_2, m_3\leqslant M$ , after step 2, the one in the middle will have $3M-(m_1+m_2+m_3)\leqslant3M$ candies. They may take extra candies, but it will not exceed $3M$ .

From this, we can conclude that the total number of candies everyone has will not exceed $3M\times n=3Mn$ .

Second, after an iteration, the total number of candies everyone has strictly increases.

To show this, assume the algorithm hasn't end yet, find 3 adjacent people where the one in the middle has $3L$ candies and at least one of the other two has more than $3L$ candies (we can always find these 3 people since if we can't, then everyone must have the same number of candies, which is a contradiction), suppose they have $3l_1$ , $3L$ , $3l_2$ candies, here, at least one of $l_1$ and $l_2$ is strictly greater than $L$ . After step 2, the one in the middle will have $L+l_1+l_2\geqslant3L+1$ candies. They may grab extra candies, but it will not be less than $3L+3$ . This shows that after an iteration, the total number of candies everyone has must at least increase by 3.

Now, if the sequence never ends, then we have a strictly increasing total number of candies that does not go beyond $3Mn$ . This is a contradiction. Hence, the algorithm must end after a certain number of iterations.

Good argument. You raised the relevant points, but they were somewhat hidden in all of the argument. (E.g. We did not need to find someone who has 3M candies, and has neighbors who do not have a total of 6M candies). I suggest simplifying the solution by pulling out the relevant argument in the following way:

Claim: After the first iteration, let the maximum number of candies that a person has be $3M$ . Then, the maximum number of candies that anyone can have in future rounds is capped at $3M$ .
Claim: After the first iteration, if not everyone has the same number of candies, then the total number of candies will strictly increase.
Hence, if the sequence never ends, then we have a strictly increasing sequence of integers that does not go beyond $3 M \times$ (number of children). This is a contradiction.

Calvin Lin Staff - 4 years, 6 months ago

Thanks for the suggestion! :D It's easier and clearer. I've updated my solution.

Kenneth Tan - 4 years, 5 months ago

Looks great now. Much clearer and easier to follow. The bolding of the 2 points also helps present the flow of the argument.

Calvin Lin Staff - 4 years, 5 months ago

Bizarre Candy Rationing

1 solution

0 pending reports