Monday, November 5, 2012

4x4 Tic-Tac-Toe (I)

If you are in Hong Kong and you need help for university mathematics courses, please visit www.all-r-math.com.

(Busy moving. Not moving the blog, but relocate my family :D )

Several years ago, there is a 14 year-old "math genius", who got very high mark in A-level exams. In an entrance interview, a professor asked the kid about a question on a combinatorical game, the kid's response was: It is not mathematics!
As it turns out the kid, under the guidance of his teacher, i.e. his father, are only interested in those problems related to examinations.

Maybe we should not blame the kid too much. Unlike calculus or algebra, combinatorics do not have the feel of advanced mathematics. The structure is loose and there is no satisfactory introduction about it. However, the underlying mindset is the basis for studying computer science, mathematical politics, game theory, etc.

For most of us, the first combinatorical game encountered is the Tic-Tac-Toe. It is easy, and we should figure out (if we are old enough) that we can usually forced a draw. However, it is fairy complicated to write down the non-losing strategy. That is the perfect example that Easy may not be Simple!

How about if we play the Tic-Tac-Toe game on a 4x4 grid instead? The winner is again the first player getting a non-broken row (horizontal, vertical or diagonal) of three X's or O's.

The question is:
(a) Could the game ended in a draw if the players wish?
(b) Is there any non-losing or even winning strategy for one of the players?

We will answer this question in the next blog.