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…

The Genius, by A Skymin’s Mind #8

Same Number Hunt

Used as Final Match of Season 3, Game 2.

Rules

Score points by correctly forming mathematical expressions resulting on the given number. Win by scoring 10 points first.

There is a grid of 16 letters. Behind each letter, there are the twelve numbers 1-12 and the four arithmetic operations +, -, ×, ÷. At the beginning, the back sides are shown for 5 seconds to the players, after which they are hidden again, only showing the letters. Then the game begins, playing round after round, until someone scores 10 points to be the winner.

In each round, a number is revealed; this number is a natural number that can be formed using the given numbers and operations. (For example, 23 can appear as 11+12 can be formed from the grid, but 29 will not appear.) A player that thinks they can form an equation should press the buzzer and recite three letters, corresponding to the numbers and operations. For example, if 11 is behind the letter C, + is behind the letter P, and 12 is behind the letter K, on a target number of 23 a player can recite CPK (or KPC) to score.

The expression must be in the form “number, operator, number”, and may not repeat any letter (thus 7+7 is not permitted). Upon pressing the buzzer, the player has 5 seconds to recite the expression, otherwise it’s considered as an incorrect answer. After reciting the letters, they are revealed; if the answer is incorrect, the turn is passed to the opposing player, who gets no time limit to form the equation. The turns are passed back and forth until a correct answer is made, which scores 1 point and begins the next round. The first player to score 10 points win the game.

As this is a Final Game, there are three items available (in addition to Item Copy and Item Disabler):

  • Priority: Allows the user to answer the next round first without pressing the buzzer first. (This can only be activated at the start of a round, before the target number is revealed.)
  • Double Chance: Allows the user to construct a 5-letter expression (number, operation, number, operation, number), which if correct, gives 2 points.
  • Peek: Allows the user to check the back of one letter before answering.

Continue reading

Introduction to Combinatorial Game Theory, Part 1

I feel the urge to write this post partially because I’m interested on this thing (even though I failed to understand much of the later part of Winning Ways Vol. 1), and partially because I feel bad to begin analysis of The Genius 3’s Monorail with “Sprague-Grundy theorem” without people understanding a thing. Also because I should try writing mathematical posts and stuff. I’m not particularly experienced on this either, so what I’m writing is to the best of my knowledge and might be faulty at points. Blame Wikipedia for not having a good CGT article.

…so let’s go.

Continue reading

Puzzle 91: Margin of Error

Heteromino Divide the white squares into polyominoes of size 3 such that no two identical polyominoes that are also identically oriented are orthogonally adjacent.

Expected difficulty HardAnswerComment/E-mail if you want a solution to be published

Puzzle 91: Heteromino

Puzzle 91: Margin of Error
Heteromino

Oh yay I’m alive.

There we go. Recently I got the inspiration of Heteromino with a two-cell wide empty border. A 10×10 doesn’t seem to work, since I only have 6×6 space to work with the black cells, but a 14×14 looks good. Besides, I can say “here’s the 10×10 puzzle, and in case you need it, here’s two-cell margin of error around the grid if you’re stuck or something”.

…yes, I appear to be terribly uninspired for titling puzzles.

Also, I appear to start playing Pokémon Trading Card Game Online. It’s free to play, although getting the in-game currency to get more cards might be a little hard.