Friday, January 04, 2008

Maths - Not Always About Thousands of Formulae (2)

In this series of maths posts, I try to explain maths in non-jargon and non-technical writing with my little experience in maths. In doing so, it's my fervent hope to debunk the "convoluted" and "only-genius-can-do" impressions about maths.

Most people hate textbooks and websites with tons of dry, confusing solutions. Often, all we see in there are solutions with copious hints of "see I am so smart", where they show off their come-out-of-no-where ingenious steps, and then make no explanations about how they got the ideas from. It's as if the ideas' origin are trade secrets among mathematicians. In addition to that, it doesn't help when they choose to present their answers in gibberish terms and symbols that are all Greek (pun intended) to us.

It is no surprise then that maths is often misconceived as a field of "formula manipulation". Such perception is wrong. In fact, maths is much more than, and much less than formula manipulation. So, with all knowledge I could muster from my little repertoire, I will present this point in this blog via a lighthearted, layman-friendly approach.

In a previous post, I posted this question as an example:

Alice and Bob alternately choose a number from among 1 to 9, with no replacement. The first to obtain any 3 numbers which sum to 15 wins. Does Alice (the first player) have a winning strategy?

[Provided by Chiun Lin in ReCom. Spoiler Warning: Solution in the original page]
A clarification here: The term "winning strategy" might have been confusing. The question should be better phrased as "Is there any way Alice could force a win?"

What does the question mean?

I guess the question itself is rather self-explanatory. Everyone knows what a sum is. No replacement means each number can only be used once. Speaking of "force a win", it should be familiar to anyone who has played 2-player strategy games like Chess. When it comes to the endgame, sometimes you can strategize such that your opponent will definitely lose regardless of the struggles he puts up. To win with such a strategy is considered to "force a win". If you have an excellent strategy but can't foresee the definite loss of your opponent, then it's not considered forcing a win.

Now that we sorted out the question's meaning, let's try to solve the problem. While approaching such questions, the most natural first step is doing some trials-and-errors. Let's just imagine that we are Alice.

How should we choose the first number?

To make things easier, let's just name "3 numbers with the sum of 15" as "15-triplet". There are many potential 15-triplets; namely 4,5,6; 3,4,8 etc. So, what is the first number we should choose to force a win? A commonsense approach would be to start with the number which appears in most 15-triplet combinations. To do that, we write down a full list of 15-triplets:
  • 1,5,9
  • 1,6,8
  • 2,4,9
  • 2,5,8
  • 2,6,7
  • 3,4,8
  • 3,5,7
  • 4,5,6
So there are eight of them. By some simple counting, you would notice that 5 appears most frequently here (4 times) while the other numbers only appear 3 or 2 times.

Intuitively, five should be the best choice for our first number.

What next?

After making our choice, let's consider what move our opponent would make. Remember, we are trying to force a win instead of just "maximising our chance of winning". So, we should always consider the best moves from our opponents and see if we could still win despite their best effort. This is the principle behind all types of "find the winning strategy" questions.

If you were the opponent, what would you choose?

Now that I have already chosen 5, my most potential winning triplet are 1,5,9; 2,5,8; 3,5,7; 4,5,6. If you want to reduce my list of triplet choices, you must be disappointed now - no matter which number you choose, only one of my triplets are crossed out. For example, if you choose 1, the first triplet will no longer be possible for me; but the rest are still available to me.

So, from the perspective of "reducing my triplet choices", there's no number that gives you an advantage. Any number that you choose would have the same effect, that is, to sabotage one of my potential triplets. There's not a single number with a higher "sabotage ability" than the other numbers.

However, let's consider another perspective. What about choosing a number which is less prone to subsequent sabotage from me? Now, remember that I said 5 appeared four times in the potential triplet list, some numbers (2, 4, 6, 8) appeared three times while the rest (1, 3, 7, 9) appeared two times?

It's starting to get convoluted, so I shall leave this post at this stage. As some sort of a cliffhanger, if you are free enough, let's just consider some factors:
  1. What happens when you choose 1, 3, 7 or 9? Are they good / strong moves? Can I force a win after you chose one of those numbers?
  2. Consider the same questions for 2, 4, 6 or 8.
  3. In the end, can my initial choice of 5 force a win?
  4. If the initial choice of 5 can't force a win, does that automatically mean that other initial choice can't force a win too?
  5. If the analysis gets too complicated by now, what should we do?
[To be continued...]
[6 Jan: Continued here]


Anonymous said...

Hmm.. I have no idea already.

The only way I can think of is make it win, or DRAW, then restart the game; wait until the opponent make a mistake, that's how tic tae toc work?

Waiting for your answer...=p

Woon Pang

youngyew said...

Woon Pang, hah your answer is actually the very solution I am going to elaborate on. The thing with tic-tac-toe is, it's a game where there's no force-win strategy. Or in other words, if two players play the game with perfect strategy, every single game will end up with a draw.

The full strategy of tic-tac-toe is rather interesting and simple enough to be understood by everyone:

Wikipedia article

(under the "strategy" section)