Category Archives: Math

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…

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 →

A/B + C/D

I was contacted by a friend that maintains an online judge, asking about the solution to a particular problem that has existed for how many days on an “easy” section.

Basically, the problem is this: given positive integers A, B, C, D, compute A/B + C/D and simplify it. You are guaranteed that if you represent A/B + C/D = E/F in lowest terms, then all of A,B,C,D,E,F fit in p-bit integers (in the problem, p = 64). Your task is to find this E and F.

Continue reading →

Antiderivative of secant

(Yes, I’m bored. So why not completing my series.)

Antiderivative of tangent

First, remember that \dfrac{d}{dx} \ln |x| = \dfrac{1}{x}, so by chain rule we obtain \dfrac{d}{dx} \ln |f(x)| = f'(x) \cdot \dfrac{1}{f(x)} = \dfrac{f'(x)}{f(x)}. By the (first) fundamental theorem of calculus, derivative and antiderivative are two inverse operations, thus we obtain \displaystyle\int \dfrac{f'(x)}{f(x)} \, dx = \ln |f(x)| + C.

Also, recall that \dfrac{d}{dx} \tan x = \sec^2 x and \dfrac{d}{dx} \sec x = \sec x \tan x. Don’t tell me you don’t know this; if you don’t, then stop reading.

To the real meat.

\displaystyle\int \sec x \, dx

= \displaystyle\int \dfrac{\sec x (\tan x + \sec x)}{\tan x + \sec x} \, dx (!)

= \displaystyle\int \dfrac{\sec^2 x + \sec x \tan x}{\tan x + \sec x} \, dx

Letting f(x) = \tan x + \sec x, we have f'(x) = \sec^2 x + \sec x \tan x (!). Thus,

= \displaystyle\int \dfrac{f'(x)}{f(x)} \, dx

Which by our lemma above is equal to

= \ln |f(x)| + C

= \ln |\tan x + \sec x| + C (Hint: Wikipedia is your friend.)

Usually I stop here, but you can also simplify it to involve only one trigonometric function:

\tan x + \sec x

= - \cot \left( x + \frac{\pi}{2} \right) + \dfrac{1}{\cos x}

= - \dfrac{1}{\tan \left( x + \frac{\pi}{2} \right)} + \dfrac{1}{\sin \left( x + \frac{\pi}{2} \right)} (!)

Call a = \dfrac{x}{2} + \dfrac{\pi}{4}. So

= - \dfrac{1}{\tan 2a} + \dfrac{1}{\sin 2a}

= - \dfrac{1}{ \dfrac{2 \tan a}{1 - \tan^2 a} } + \dfrac{1}{2 \sin a \cos a}

= - \dfrac{1 - \tan^2 a}{2 \tan a} + \dfrac{\sec a}{2 \sin a}

= \dfrac{\tan^2 a - 1}{2 \tan a} + \dfrac{\sec a}{2 \sin a \cdot \frac{\cos a}{\cos a}}

= \dfrac{\tan^2 a - 1}{2 \tan a} + \dfrac{\sec a}{2 \cos a \cdot \frac{\sin a}{\cos a}}

= \dfrac{\tan^2 a - 1}{2 \tan a} + \dfrac{\sec^2 a}{2 \tan a}

= \dfrac{\tan^2 a - 1 + \sec^2 a}{2 \tan a}

= \dfrac{\tan^2 a + \tan^2 a}{2 \tan a} (remember \tan^2 x + 1 = \sec^2 x?)

= \dfrac{2 \tan^2 a}{2 \tan a}

= \tan a

= \tan \left( \dfrac{x}{2} + \dfrac{\pi}{4} \right)

Thus \displaystyle\int \sec x \, dx = \ln \left| \tan \left( \dfrac{x}{2} + \dfrac{\pi}{4} \right) \right| + C.

Now, what happens to \displaystyle\int \sec^3 x \, dx…

Happy New Year!

Unlike last year, I don’t have any puzzle planned. I’m constructing an LMI test for April or May, and considering that I just finished my first semester of university a week or so ago, I’ve been taking the holiday for my usual computer stuff: programming, browsing the net, playing some games…

So what have I done in 2013?

Continue reading →

Two real numbers

Initially found from xkcd’s blog, then got a link to MathOverflow.

Suppose you are playing a game with Alice. She uses some probability distribution to pick two distinct real numbers and writes them in two envelopes. You then choose either of the envelope and opens the number inside the envelope. Is there a strategy that guarantees you a strictly larger than 50% probability to guess correctly whether the chosen real number is the greater or the lesser, for any probability distribution that Alice uses?

This is my take on the problem; feel free to comment, discuss, or argue with me! As long as the discussion is kept civil.

The answer is yes.
Continue reading →