Kalah Always Ends

Kalah is a game in the mancala family, whose rules can be seen in the given Wikipedia link.

Theorem A game of Kalah always ends, no matter how the players play. In fact, this can be generalized heavily: no matter what the initial distribution of stones is, no matter how many houses are in each row, no matter how the players play, a game of such generalized Kalah always ends (although probably will take a long time).

The proof is actually pretty simple, and is inspired from Goodstein’s theorem.

First, observe that a stone that falls to a house will never move back out. Thus we have a monovariant: the total number of stones in the houses will never increase. For simplicity, let the number of stones in the houses (not in the store) be called the free count (for count of free stones); the monovariant says that the free count will never increase.

Also, one seemingly moot but important point is that the free count is a natural number (a non-negative integer). Why does that matter? Because armed with that, we can invoke a powerful theorem, the well-ordering theorem: any set of natural numbers has a smallest element. Or in other words, any decreasing sequence of natural numbers will eventually reach zero.

Why does that matter? Well, let’s suppose we can show that the free count cannot last the same forever. That is, at some point it must change. It doesn’t matter how long it is until the change, and how big the change, as long as it eventually changes. Due to the monovariant above, it cannot become larger, and thus it must become smaller. Now we can use the same argument again to show that the free count will become smaller again, and then even smaller, and so on. This naturally is a sequence of free counts, which means a sequence of natural numbers, and a decreasing sequence at that! Which by well-ordering theorem above means it will eventually reach zero. The free count will eventually reach zero. This means there are no stones in play, so the game ends. (The game could have ended earlier, when one player has more stones than the opponent or when one player has no stones in houses, but that doesn’t matter, since it still means the game ends.)

Good, now we get almost everything! Only that we’re missing the key argument: how do we prove that the free count cannot last the same forever? Well, now here’s where my inspiration from Goodstein’s theorem comes in.

Take one player. Label their houses as 0, 1, 2, \ldots, k from the closest to their store, and the stones in it a_0, a_1, a_2, \ldots, a_k respectively. Now suppose \omega is some sufficiently large number (in fact, two suffices, but I originally thought about the smallest infinite ordinal (the next number that comes after all natural numbers; you can go scour ordinal number about it)). Consider the number A = a_0 \omega^0 + a_1 \omega^1 + a_2 \omega^2 + \ldots + a_k \omega^k. What happens after a move by this player?

There are two cases. The first case, the move passes the store or makes a capture, so the free count decreases and we’re done (remember that we now want to prove that the free count must decrease at some point). The second case, the move doesn’t pass the store. This means A decreases by a_n \omega^n, where n is the hole where the move is taken, and increases by \omega^{n-1} + \omega^{n-2} + \omega^{n-3} + \ldots + \omega^{n-a_n} (because the move doesn’t reach the store). The key is, the former is greater than the latter! You can show this easily:
\omega^{n-1} + \omega^{n-2} + \omega^{n-3} + \ldots + \omega^{n-a_n}
\le \omega^{n-1} + \omega^{n-1} + \omega^{n-1} + \ldots + \omega^{n-1}
= a_n \omega^{n-1}
< a_n \omega^n

Thus A decreases.

Remember about well-ordering theorem above? True: after each of this player’s move, A decreases, and it is a natural number! Thus at some point is must be zero, which means all stones are removed. But this means some move has sent some stone to the store, decreasing the free count.

Of course, both players play alternately when no stone comes to the store. But just do the similar thing for the opponent; at some point, one of the two A‘s must decrease low enough for some stone to be forced to the store, decreasing the free count.

Thus we’re done!


Clearly, the inspiration from Goodstein’s theorem is the above, with the \omega‘s appearing. Had I noticed that the simple number two works when I first thought about it, I wouldn’t have used \omega‘s. But eh, why not.

And now I need to sleep…

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s