Further adventures in problems I don’t know the answer to.
Suppose you have a line of buckets in a row. And some of the buckets have various numbers of balls in them. Some are empty. Like so.
Now, starting on the rightmost bucket, you are going to do the following. Take the balls out of the current bucket, and distribute them among the buckets immediately to the right, such that each bucket only has one ball.
So in this case, the right most is empty, so we move to the second bucket. Also empty. So we move to the third, and redistribute the balls like so.
The next bucket over has one ball in it, so we take that ball out and distribute it to the empty bucket immediately to the right.
Skipping empty buckets again, that takes us to the last bucket with 5 balls. Distributing among the empty buckets,
And we have 2 balls left over – no more buckets. We have overflow!
So that is the basic process.
In general, let us assume that you have n+1 many buckets, with ai balls in each bucket.
And we apply the same process, starting from the right and moving to the left.
The question is, what are necessary and sufficient conditions on the sequence of balls such that you do not overflow?
For example, you clearly can have no more than n many balls. You know that the last bucket will always be empty in the end, and at most, every other bucket has one ball. So you have an upper bound of n on the total number of balls. This gives us the necessary condition that
Also, think about the 0th bucket – the first bucket we consider. If there are any balls at all in that bucket, you necessarily overflow, since there are no buckets to put those balls in. Therefore, the 0th bucket must be empty. Similarly, the 1-th bucket can’t have more than one ball in it. You can only distribute balls from bucket 1 to bucket 0, which means that it has at most one ball. Continuing in this way, we get the necessary condition that
Both of these are necessary conditions, but not sufficient – there are distributions of balls that meet both these requirements, but still overflow. So the question I put to you, dear reader, is whether or not there is a sufficient condition. Is it a useful, calculable condition? What other necessary conditions are there? If we bring enough necessary conditions together, can we derive a sufficient condition?
I don’t know. I’m in the middle of finals now, so maybe soon I’ll get some time to sit and think about this.
And, as always, draw yourself a picture!
and 
. These numbers are special, but remember, there really is no ‘goodness’ metric on the reals. So today, let’s consider something else, a little more out there.
be the n’th fibonacci number. The Fibonacci sequence goes, 1, 1, 2, 3, 5, 8, 13, …, where each number is the sum of the two previous. So, 
.
