Buckets of Fish!

Can you take the last fish from the buckets? Or the last coin in the game of Whim?

The game I call Buckets of Fish is played, even if mainly in the imagination, on the beach with finitely many buckets in a line—some of the buckets hold some freshly caught fish, and there is an endless supply of more fish fresh off the boats. Players take turns, and on each turn one fish is removed from one bucket and then as many new fish as desired (or none) are added to buckets to the left.

Whoever takes the very last fish overall wins the game. Perhaps the buckets currently hold the following numbers of fish:

\( 2\qquad 5\qquad 0\qquad 3\qquad 21\qquad 4 \)

What is your winning move? Is there any winning move? Perhaps the game will proceed indefinitely with no winner.

Interlude

Must the game end?

Before investigating the possibility of winning moves, it seems urgent to address the more fundamental issue whether the game indeed will necessarily come to an end at all. After all, huge numbers of fish can often be added to the buckets during play (let us imagine the buckets as extremely capacious), but only one fish is removed each turn, and so a skeptical reader could reasonably wonder whether in fact the game will always have a winner.

Perhaps by adding fish in a suitable manner, the players may conspire to prolong the game indefinitely. Is it possible? Or perhaps every play of the game eventually finds its completion. In short, the question is whether Buckets of Fish is a finite-play game.

Can you make an argument one way or the other? If you think the game does not necessarily end, then you should aim to provide a specific infinite play that never ends. What are the moves exactly? Alternatively, if you think all plays of Buckets of Fish eventually come to an end, then what is the proof?

Interlude

The answer is that, indeed, Buckets of Fish is a finite-play game—every play of the game eventually comes to an end. Regardless of how the players might conspire to add fish to the buckets during play, even with an endless supply of fish from the boats, nevertheless they will inevitably run out of fish in the buckets.

But how can this be? After all, can't we always add more fish to the buckets than we remove? By doing so, wouldn't this lead to a nonterminating infinite play?

One way to reply to this objection is point out that the expectation that on any given turn we can always add huge numbers of fish to the buckets isn't strictly true. Consider what happens, for example, when we elect to remove a fish from the leftmost bucket. In this case, since there are no buckets to the left of it, there is no possibility of adding fish to any buckets on such a turn. So it just isn't true that after taking a fish we can always necessarily add huge numbers of fish.

A further subtle observation about this matter is that even on turns when we are adding huge numbers of fish to the buckets, the fish that we do add are always necessarily closer to the leftmost bucket than the fish we removed. Those fish are consequently less powerful, in a sense we shall make precise, in terms of their ability to cause additional fish in the buckets. Ultimately this way of thinking provides some insight into our later use of transfinite ordinals to measure in a game-value sense how far a position is from completion, since fish further left contribute a smaller ordinal sum to this value.

After proving that the game will always terminate in finitely many steps, we shall present a winning strategy for the game, telling you exactly how you can ensure a win. In a pleasant twist, the winning strategy turns out to be extremely simple—who would have guessed that it could be so easy?

After giving an account of the winning strategy, we shall similarly analyze a number of natural variations of the game, Give-or-take Buckets of Fish, Give-or-take-one, Cascade of Fish, Free-fish Buckets of Fish, and One-fish-at-a-time Buckets of Fish, which will themselves lead to several further interesting games, including a Nim-variant game I call Whim, which is like Nim, but which turns out to be a disguised form of Buckets of Fish.

Let’s get into it!