Note that cases with 1 or 2 buckets can be reduced to a single bucket (trivially).

We define a cycle as taking coins out from all the (remaining) buckets exactly once (with the cycle ending when coins are put in the bucket that already has coins taken out).

Now we split buckets (with more than 2 coins) into 2 cases - whether they are odd or even initially. We set a "first" bucket for convenience sake.

If they're odd, the first two buckets will be left with 0 coins. After which, buckets will experience a loss of (-1,-2,-1,...,-2,-1) and gain of (+1,+1,+2,+1,...+1,+2), so the net change would be (0,-1,+1,-1,+1,...-1,+1). But we have 2 coins from the initial second bucket back to the current first bucket, so the total net change would be (+3,-1,+1,...-1,+1), and so we have (3,2...2) coins in the remaining buckets. If initially we have 2k+1 buckets, now we have k buckets left.

If they're even, the result is similar, with loss of (-1,-2...,-2) and gain of (+2,+1,...+2,+1), so we have a total net change of (+4,-1,+1,...+1,-1), and thus we are left with (4,2,...2) coins in the remaining buckets. If initially we have 2k buckets, now we have k-1 buckets left.

After a cycle, we can split them into whether they have odd or even buckets again.

If they have odd number of buckets (say 2k'+1), we count the loss [either A:(-1,-2,...-1) or B:(-2,-1,...-2)] or gain [either A:(+1,+1,+2,..+1,+2) or B:(+2,+2,+1,...+2,+1) depending on the loss] after a cycle. Then, we can arrive at a net change - A:(0,-1,+1,...-1,+1) or B:(0,+1,-1,...+1,-1). Note that the number of buckets does not change as each buckets initially have at least 2 coins (and the first bucket have at least 3). Now we count another cycle, and we find that if A occurred just now then B must have occurred now, and vice versa. Note that those buckets with 1 coin left all experienced a net gain (+2 coins first then -1), so at no point in time are they ever empty. We count these 2 cycles, and find that the net change is (0,0,...0). Therefore, we just formed a loop of 2k'+1 buckets (k' non-negative).

If we have an even number of buckets (say 2k'), we count the loss [either A:(-1,-2,...-2) or B:(-2,-1,..-1)] or gain [either A:(+2,+1,...+2,+1) or B:(+1,+2,...+1,+2)] to obtain the net change [either A:(+1,-1,..+1,-1) or B:(-1,+1,...-1,+1)] after a cycle. We then note that if A first occur then it'll keep occurring, and this applies to B as well. For A, this will happen till all the even-numbered buckets have 0 coins. For B, all the odd-numbered buckets will have 0 coins (note: the last coin will not go into the first bucket since it is already empty; it will go into the second). In any case, k' buckets will be left.

The remaining buckets all have at least 2 coins each (with the first bucket having at least 3). Therefore, we can apply the above algorithm repeatedly till we get a loop. In particular, we are finding loops of 1 bucket each. Therefore, after the first cycle, the number of remaining buckets should be in the form of $2^a, a>0$ . So, before the first cycle, the number of buckets must be in the form of $2^a+1$ or $2^a+2$ . For $n<1000$ , we have $0<a<10$ , so we get a total of 18 values. Cases with 1 or 2 buckets fits the bill as well, so we have a final total of 20 values.

A little testing easily shows that the lowest number for which this fails is $7$ . It will also fail for $8$ , and then succeed for $9$ and $10$ . The rest of the argument will assume a larger number of buckets. (This is purely a matter of convinience; during my argument I will assume that we play the game a until a certain point, and if $n$ is too small, we will never reach said point. The resulting classification of values of $n$ for which we do eventually end up with a single bucket will still be valid for these low values.)

If we colour the first token we move red, and let it be one of the tokens being moved at each step, we see that we can consider it more of a "guide", taking one token from every other bucket and putting it into the next (non-empty) bucket, then going to the next after that and so on.

This means the rules of the game have changed slightly. We now take the red token from bukcet number 1, let it "pick up" one token from bucket no. 1, and put it down in bucket no. 2, then it takes one token from bucket no. 3, puts it into no. 4 and so on, going around the circle when applicable.

After going one full round we have a bunch of buckets with 2 tokens in them (not counting the red token, but possibly $3$ in the bucjet where the red token is, depending on the parity of $n$ , but this matters little). Following the rules of the game, it will now play out as follows: If there are an odd number of buckets left, then we will be back where we were at the beginning of this paragraph, and the game will just continue in this stalemate for ever. If there are an even number of buckets left, after going two more rounds half of the buckets will have had their tokens moved to the bucket next to it, making it so that we have a number of buckets with $4$ (possibly one with $5$ ) tokens in them.

And here the pattern emerges. If the number of buckets left is even, then four turns around the ring of buckets will once again halve the number of buckets with tokens in them, while if there is an odd number of buckets, two rounds (and thus also four) will take us back to where we were.

Each time we successfully halve the number of remaining buckets, we are stuck if that remaining number is odd, and we can halve the number of buckets left if that number is even. The number of buckets we have after the first round is $\left\lfloor \displaystyle\frac{n-1}{2}\right\rfloor$ . If we write that as $2^ik$ for some non-negative $i$ , and with $k$ odd, then we will reach a stalemate when there are $k$ buckets left. We want that number to be $1$ . The values of $n$ which permits this are numbers of the form $2^j + 1$ or $2^j + 2$ for non-negative $j$ .

Let as split the process into laps. After first lap there will remain floor((n-1)/2) bins of 2 tokens each and 1 or 2 tokens in our hand. After that, if there is even number m of remaining bins, we will drain half of them by 1 token and add 1 token to the other half. So it would proceed till one half of bins are completely drained and the other half - doubled. If the number m of the remaining bins is odd, m > 1, and numbers of tokens in each of them >= 2, then each of the following laps would drain about half of them by 1 token and add 1 token to the rest, while the next lap do reverse job, so the process will loop forever. That is, process finishes iff floor((n-1)/2) has no even divisors but 1, that is n=2 k+1 or n=2 k+2. Cases n=1 and n=2 are degenerate, and work as well. So we have k in [1:9] plus n=1, n=2, totally 20 cases.

We number the bucket 1,2,3...n. When we play the game, after the first round, the first bucket will be gone, and so does all the even-numbered buckets. The number of buckets left will be (n-1)/2 if n is odd and (n-2)/2 if n is even.

Now we see that the game will not terminate if we get an odd number of buckets remaining. If there is an even number 2k of buckets remaining, the game will continue until k of the buckets are eliminated and we are left with k buckets.

When we are left with k buckets, we can apply the same reasoning process (game will not terminate if k is odd, if not, consider k/2)

Thus, the game only terminates if the number of buckets left is a power of 2. In other words (n-1)/2 is a power of 2 or (n-2)/2 is a power of 2.

Thus the possible values of n are 1,2, 3,4, 5,6, 9,10, 17,18, 33,34, 65,66, 129,130, 257,258, 513,514.

Therefore there are 20 values of n

First, we can examine small cases separately - for $n \leq 6$ , all the tokens do end up in a single bucket, whereas they do not if $n$ is $7$ or $8$ .

Now, think about the problem slightly differently: we have $n-1 = k$ buckets, and we alternate between taking a token out and putting one in. It is easy to see that this is the same problem.

In the case when $k = 2r$ is even, we will run around and have $r$ buckets, each with two tokens in. Clearly, if $r$ is odd, then two successive circuits will cancel and we will not reach one bucket, but if it is even, then two successive circuits will halve $r$ and there will be four tokens per bucket.

Then, we will continually run around and as long as there is never an odd number of buckets (after a number of circuits) we will reach one bucket, but if there is an odd number, then we will terminate.

The only way we can reduce the number of buckets is to halve it, so the cases that we will reach one bucket is if $r$ is a power of two - i.e. $n$ is 9, 17, 33, 65, 129, 257 or 513.

If $k = 2r + 1$ is odd, then we will run around and have $r$ buckets, each with two tokens except the last which will have three. This is one we're adding into, so it is easy to see why this case will turn out to be the same as the previous case - we will terminate iff $r$ is a power of 2. This corresponds to $n$ is 10, 18, 34, 66, 130, 258 or 514.

Thus there are a total of 6+7+7=20 possibilities for $n$ .

Label the buckets counterclockwise as $1,2,\ldots,n.$ By symmetry, the choice of starting bucket does not matter, so we will assume that we started by moving the token from bucket 1 to bucket 2. After the first $n$ moves, bucket 1 and all even numbered buckets have become empty. Each odd numbered bucket will contain 2 tokens, except for bucket 3, which will contain 3 tokens if $n$ is odd and 4 tokens if $n$ is even.

The number of remaining buckets is $\lfloor \frac{n-1}{2}\rfloor.$ If this is an odd number of buckets (aside from 1), then performing the next $2\lfloor \frac{n-1}{2}\rfloor$ moves, will not change the number of tokens in the bucket. If there are an even number of buckets left, say $1,2,\ldots k,$ performing the next $k$ moves will remove 1 token from each bucket in an even position and add 1 to each bucket in an odd position. Doing this twice will leave us with half the number of buckets, with bucket 1 containing 5 or 6 tokens and each other bucket containing 2.

This gives rise to a general observation that when every bucket aside from the one we are going to move from has $m$ tokens and the bucket we are going to remove from has more than $m$ tokens, then we are able to eliminate some buckets from the circle if and only if the number of buckets is even. This follows by performing either $2k$ moves or $mk$ moves, where $k$ is the number of remaining buckets, with the number of moves depending on the parity of $k.$

Thus, we see that we will eventually eliminate all buckets except 1 if and only if $\lfloor\frac{n-1}{2}\rfloor$ is a power of 2, or $n = 1$ . In other words, $n=1$ , $n = 2^{a} + 1$ or $n = 2^a + 2$ for some value of $a.$ This gives $1, 2, 3, 5, 9, 17, 33, 65, 129, 257, 513, 4, 6, 10, 18, 34, 66, 130, 258, 514$ as possible values of $n.$ There is a total of $20$ values.

It seems that the answer is 20, but I can't prove it without simulation.

include <cstdio>

include <deque>

include <set>

include <utility>

using namespace std;

int remaining(int N) { //Set to store all the encountered states with current length //Note that state is not just the current sequence of buckets //but also includes whether the last move was 1 or 2 set<pair<deque<int>,int> > seen;

//Current sequence of buckets deque<int> cur(N,1);

for(int i=1;;i=3-i) { if(cur.size()==1)return 1;

//Take i tokens from the last bucket and add them to the penultimate one
int n=cur.back();
cur.pop_back();
int m=cur.back();
cur.pop_back();
cur.push_back(m+i);

if(i==n)      
{
  //Size of bucket sequence has reduced by 1
  //So no need to keep the existing "seen" states
  seen.clear();
  seen.insert(make_pair(cur,i));
}
else
{
  //Push the bucket from which coins were taken to the end
  cur.push_front(n-i);
  if(seen.count(make_pair(cur,i)))return cur.size();
  seen.insert(make_pair(cur,i));
}

} }

int main() { for(int i=1;i<=1000;i++) printf("%d %d\n",i,remaining(i)); return 0; }

Looking at the output of the code, I hit upon the following method to calculate the final remaining number of buckets for N > 2 : Cancel off all the powers of two from . Here is a function that does the same:

int closedform(int N) { if(N>2)N=(N-1)>>1; while(!(N&1))N>>=1; return N; }

It was verified that the two functions give the same solution for all N under 1000. Thus, the remaining number of buckets is 1 if N is of the form or . There are 20 such numbers since there are 10 powers of 2 under 1000.

I am unable to see why my method to calculate the solution works though. In any case, the code gives the answer as 20.

I have done it using a c++ program.

Here's my mathematical approach.

The possible number of buckets can only be $1,2$ or $2^k +1$ or $2^k + 2$

We know: $2^1=2,2^2=4\cdots ,2^9=512, 2^{10}=1024$

So, there are 9 such numbers such that $2^k\leq1000$

So, the total number of possibilities is $9*2+2=20$ .

Now, the first two buckets will always get discarded at beginning.

So, certainly we have {1,2} in our solution set.

To check if we can have more than these two choices:

After the first two buckets get emptied the next buckets will have alternately $2$ or $0$ tokens ( Some hit n' trial needed here).

The basket will be considered empty $*iff*$ the number of baskets is even because then, after every round the same no. of tokens will be withdrawn.

Suppose, if 6 tokens were removed from a basket then the next time too \(6 tokens will be taken from the basket.

After sufficient number of rounds the basket will get emptied and so will all the alternate baskets.

This implies that we must have \(2a\) or $2a -1$ baskets in order to empty some of them. The last basket will get emptied always. We have got the number of buckets left. We need two more in each case.

When half the buckets get emptied, the remaining buckets should have to be even to complete this process of work.

This process is repeated over and over, alternating moving one token and then two tokens.

So $a = 2b$ $\implies b = 2l$

Hence, $c = 2^k$ or $c = 2^k - 1$

As we have stated earlier above that, numbers of bucket required = $2^k +2$ or $2^k + 1$

Hence, all the positive integer values of $n\lt1000$ for which all the tokens eventually end up in a single bucket are:

$1, 2, 3, 4, 5, 6, 9, 10, 17, 18, 33, 34,$ $65, 66, 129, 130, 257, 258, 513, 514$