Buckets of fish!

Let me tell you about the game Buckets of fishReef_shark_beneath_a_school_of_jack_fish 4096

This is a two-player game played with finitely many buckets in a line on the beach, each containing a finite number of fish. There is also a large supply of additional fish available nearby, fresh off the boats.

Taking turns, each player selects a bucket and removes exactly one fish from it and then, if desired, adds any finite number of fish from the nearby supply to the buckets to the left.

For example, if we label the buckets from the left as 1, 2, 3 and so on, then a legal move would be to take one fish from bucket 4 and then add ten fish to bucket 1, no fish to bucket 2, and ninety-four fish to bucket 3. The winner is whoever takes the very last fish from the buckets, leaving them empty.

Since huge numbers of fish can often be added to the buckets during play, thereby prolonging the length of play, a skeptical reader may wonder whether the game will necessarily come to an end. Perhaps the players can prolong the game indefinitely? Or must it always come to an end?

Question. Does every play of the game Buckets of fish necessarily come to an end?

The answer is yes, every game must eventually come to a completion. I shall give several arguments.

Theorem. Every play of the game Buckets of fish ends in finitely many moves. All the fish in the buckets, including all the new fish that may have been added during play, will eventually run out by some finite stage during play.

That is, no matter how the players add fish to the buckets during play, even with an endless supply of fish from the boats, they will eventually run out of fish in the buckets and one of the players will take the last fish.

First proof. We prove the claim by (nested) induction on the number of buckets. If there is only one bucket, then there are no buckets to the left of it, and so there is no possibility in this case to add fish to the game. If the one bucket contains $k$ fish, then the game clearly ends in $k$ moves. Assume by induction that all plays using $n$ buckets end in finitely many moves, and suppose that we have a game situation with $n+1$ buckets, with $k$ fish in bucket $n+1$. We now prove by induction on $k$ that all such games terminate. This argument is therefore an instance of nested induction, since we are currently inside our proof by induction on $n$, in the induction step of that proof, and in order to complete it, we are undertaking a separate full induction on $k$. If $k=0$, then there are no fish in bucket $n+1$, and so the game amounts really to a game with only $n$ buckets, which terminates in finitely many steps by our induction hypothesis on $n$. So, let us assume that all plays with $k$ fish in bucket $n+1$ terminate in finitely many moves. Consider a situation where there are $k+1$ many fish in that bucket. I claim that eventually, one of those fish must be taken, since otherwise all the moves will be only on the first $n$ buckets, and all plays on only $n$ buckets terminate in finitely many moves. So at some point, one of the players will take a fish from bucket $n+1$, possibly adding additional fish to the earlier buckets. But this produces a situation with only $k$ fish in bucket $n+1$, which by our induction assumption on $k$ we know will terminate in finitely many steps. So we have proved that no matter how many fish are in bucket $n+1$, the game will end in finitely many moves, and so the original claim is true for $n+1$ buckets. Thus, the theorem is true for any finite number of buckets. QED

A second proof. Let me now give another proof, following an idea arising in a conversation with Miha Habič. We want to prove that there is no infinitely long play of the game Buckets of fish. Suppose toward contradiction that there is a way for the players to conspire to produce an infinite play, starting from some configuration of some finite number $n$ of buckets, each with finitely many fish in them. Fix the particular infinitely long play. Let $m$ be the right-most bucket from which a fish was taken infinitely often during that infinite course of play. It follows, for example, that $m<n$, since the top bucket can be used only finitely often, as it never gets replenished. Since bucket $m$ starts with only finitely many fish in it, and each time it is replenished, it is replenished with only finitely many fish, it follows that in order to have been used infinitely many times, it must also have been replenished infinitely often. But each time it was replenished, it was because there was some bucket further to the right that had been used. Since there are only finitely many buckets to the right of bucket $m$, it follows that one of them must have been used infinitely often. This contradicts the choice of $m$ as the right-most bucket that was used infinitely often. QED

A third proof. Let me now give a third proof, using ordinals. We shall associate with each Buckets-of-fish position a certain ordinal. With the position $$7\quad 2\quad 5\quad 24,$$ for example, we associate the ordinal $$\omega^3\cdot 24+\omega^2\cdot 5+\omega\cdot 2+7.$$ More generally, the number of fish in each bucket of a position becomes the coefficient of the corresponding power of $\omega$, using higher powers for the buckets further to the right. The key observation to make is that these associated ordinals strictly descend for every move of the game, since one is reducing a higher-power coefficient and increasing only lower-power coefficients. Since there is no infinite descending sequence of ordinals, it follows that there is no infinite play in the game Buckets of fish. This idea also shows that the ordinal game values of positions in this game are bounded above by $\omega^\omega$, and every ordinal less than $\omega^\omega$ is realized by some position. QED

OK, fine, so now we know that the game always ends. But how shall we play? What is the winning strategy? Say you are faced with buckets having fish in the amounts: $$4\quad 5\quad 2\quad 0\quad 7\quad 4$$ What is your winning move? Please give it some thought before reading further.

 

 

 

The winning strategy turns out to be simpler than you might have expected.

Theorem. The winning strategy in the game Buckets of fish is to play so as to ensure that every bucket has an even number of fish.

Proof. Notice first, as a warm-up, that in the case that there is only one bucket containing an even number of fish, then the second player will win, since the first player will necessarily make it odd, and then the second player will make it even again, and so on. So it will be the second player who will make it zero, winning the game. So with one bucket, the player who can make the bucket even will be the winner.

Next, notice that if you play so as to give your opponent an even number of fish in every bucket, then whatever move your opponent makes will result in an odd number of fish in the bucket from which he or she takes a fish (and possibly also an odd number of fish in some of the earlier buckets as well, if they happen to add an odd number of fish to some of them). So if you give your opponent an all-even position, then they cannot give you back an all-even position.

Finally, notice that if you are faced with a position that is not all-even, then you can simply take a fish from the right-most odd bucket, thereby making it even, and add fish if necessary to the earlier buckets so as to make them all even. In this way, you can turn any position that is not all-even into an all-even position in one move.

By following this strategy, a player will ensure that he or she will take the last fish, since the winning move is to make the all-zero position, which is an all-even position, and the opponent cannot produce an all-even position. QED

In the particular position of the game mentioned before the theorem, therefore, the winning move is to take a fish from the bucket with 7 fish and add an odd number of fish to the bucket with 5 fish, thereby producing an all-even position.

Finally, let’s consider a few variations of the game. It is clear that the all-even strategy works in the versions of the game where one is limited to add at most one fish to each of the earlier buckets, and this version of the game is actually playable, since the number of fish does not grow too much. A similar variation arises where one can either or add or remove any number of fish (or just at most one) from any of the earlier buckets, or where one can, say, add either 5 or 6 fish only to each of the earlier buckets. What is important in the argument is simply that one should be able to ensure the all-even nature of the buckets.

For a more interesting variation, consider what I call the Take 3 version of the game, where one can take either one, two or three fish from any bucket and then add any number of fish to the earlier buckets. The game must still eventually end, but what is the winning strategy?

Question. What is your strategy in the Take 3 variation of Buckets of fish?

Please post your answers in the comments, and I’ll post an answer later. One can generalize this to the Take $n$ variation, where on each turn, the player is allowed to take between 1 and $n$ fish from any bucket, and add as many fish as desired to the earlier buckets.

Another puzzling variation is where each player can take any number of fish from a bucket, and then add any number of fish to earlier buckets. Can you find a strategy for this version of the game? Please post in the comments.

11 thoughts on “Buckets of fish!

    • Yes, because the ordinal is only $\omega^\omega$, rather than $\epsilon_0$. For example, the nested induction proof can be undertaken directly in PA. Shall we try to design a version of Buckets of fish with ordinal value $\epsilon_0$? Then we can hope for an independence result about it.

      • Here’s a suggestion for Buckets Of Fish with ordinal-indexed buckets. Since we remove at most one fish at a time, in order to guarantee termination, we must insist that the total number of fish in the buckets is finite at each point of the game. This leads to the following rules:

        1. At the beginning, there total number of fish in all the buckets is finite.
        2. In each step, you pick a non-empty bucket, remove one fish, take a finite number of fish from the boat, and distribute them to the buckets to the left (ie buckets indexed by ordinals smaller than the one corresponding to the current bucket).

        Since the total number of non-empty buckets is finite, the strategy “keep all buckets even” works, and the proof is similar (there’s always the unique non-empty bucket with the largest index).

        Termination:

        Start with all buckets “uncovered”.

        Pick the non-empty uncovered bucket with the largest index. If such a bucket doesn’t exist: stop. As the game progresses, the number of fish in that bucket can only decrease. After some finite number of turns (maybe 0) the number of fish in that bucket will have changed for the last time ever. When this happens, cover the bucket and repeat the process described in this paragraph.

        Each iteration of the previous paragraph takes a finite number of turns. The indexes of the buckets considered form a decreasing sequence of ordinals, so the number of iterations must be finite as well. After all these iterations, all non-covered buckets are empty. Also, each covered bucket was covered after the number of fish in it changed for the last time. So there are no moves available, so all buckets must be empty.

        • Nice! One can also prove termination by associating to each position the corresponding ordinal $\omega^\alpha\cdot n$, where bucket $\alpha$ has $n$ fish, and using the Cantor normal form just as with finitely many buckets. Then the ordinals descend on each step.

          Yesterday in our discussions at the Graduate Center we talked about allowing infinitely many fish in the buckets, but well-ordered, so that it is like transfinite Nim: http://jdh.hamkins.org/transfinite-nim/.

          • Nice, the proof based on the Cantor normal form proof is much shorter.

            I guess in the version with the infinitely many well-ordered fish in the bucket, the move is to decrease the number of fish in one bucket by any amount, and then add any number of fish to the buckets to the left? I think to terminate, we still need the restriction that the number of non-empty buckets at any stage of the game is finite.

            I think the winning strategy for this game is to make sure that after your move, the first two buckets (0 and 1) have the same number of fish, same for buckets 2 and 3, 4 and 5, etc.

      • Here’s one idea, you’re allowed to replicate one of the existing buckets. Namely, in your turn you are allowed to create a new bucket and put an amount of fish like one in the pre-existing buckets.

        I’m not sure this game will halt, though.

  1. For the Take 3 version of the game, instead of ensuring an even number of fishes in each bucket at the end of my turn, I should probably try to ensure that the number of fishes in each bucket is divisible by 4 after my turn. If I can maintain that, I suppose this would be a winning strategy.

    • And indeed you can maintain that, since when the other player moves, they reduce a bucket by either one, two or three (and adjust the lower buckets), and so on your turn you can take respectively three, two or one to maintain the multiple of four feature in that bucket, and then adjust all the lower buckets to still be a multiple of four. Furthermore, if a position is not all-multiples-of-four, then one can always find a move that makes them all multiples of four, by working on the largest non-multiple-of-four bucket, which will have a residue of one, two or three. So this is indeed a winning strategy. Or one should say winning policy, since there is a choice of how to implement it, since one can add extra fish to the lower buckets. Indeed, it is the unique maximal winning policy for the Take 3 variation, since if a move ever violates the multiple-of-four condition, then the opponent can win by immediately adopting it. So to violate this policy is losing in every instance. Very good!

  2. Pingback: Buckets of Fish and Defeating Hydras | Mike's Math Page

  3. For the last variation (where you could take any number of fish), I think the losing states are those where buckets 2i+1 and 2i+2 have an equal number of fish. Is that right?

    I also found interesting patterns on the Grundy numbers of different positions in this variation. I couldn’t generalize them, though.

Leave a Reply to PiotrCancel reply