A number game

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

Consider the following card game:

A set of nine cards numbered 1 to 9. Two players in turns pick up a card. The winner is the player who first have three of his cards add up to 15.

For instance, in the fourth turn Player A gets 1,2,3,9 and Player B gets 4,5,6,7, then Player B wins the game as 4+5+6=15.

Better have a try first before continue to read.




Three classes of 1-9 tiles in Mahjong. [Source: Wikimedia Commons]

If we talk about an IQ game involving 1 to 9, which game comes to your mind?
Let me guess: the magic square! Arrange the nine cards in a magic square.

8	1	6
3	5	7
4	9	2

The above is one of the possible answer.
Now plays the card game again.

Have you noticed that you are just playing Tic-Tac-Toe?
It is a game that you may already dismiss as too childish long time ago.

Old thing can be new again if it is given a completely different look.

Strategy-stealing argument

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


(Too many unexpected: my baby girl Cherria comes to the world two weeks earlier than expected, and my mail account is hacked...)

I have posted two articles on the game Tic-Tac-Toe. Fields Medalist and leading game theorist John Nash was believed to be one of the two independent inventors of a two-player game called Hex. John Nash is able to prove that the first player has a winning strategy, i.e. the first player always wins if he makes no mistakes. The proof involves the "Strategy-stealing argument":

Consider a two-player game about occupying spaces on a board, no filled space will ever be freed, such that an extra move will never be a disadvantage. Assume that Player II has a winning strategy.

• Player I is about to make the first move. He randomly assumes that Player II has already made a move M0, then he pretends himself as a second player and use Player II's strategy to make a move F1.
  What Player I thinks: M0 F1
  What really happens: F1
• Player II responses by playing S1, Player I then plays F2
  What Player I thinks: M0 F1 S1 F2
  What really happens: F1 S1 F2
• The game continues. Suppose in Step 4, Player II plays M0, Player I again randomly assumes that indeed Player II has played M1 and responses with F5.
  What Player I thinks: M0 F1 S1 F2 S2 F3 S3 F4 M1 F5
  What really happens: F1 S1 F2 S2 F3 S3 F4 M0 F5
• The game continues. Suppose in Step 7, Player II plays M1, Player I again randomly assumes that indeed Player II has played M2 and responses with F8.
  What Player I thinks: M0 F1 S1 F2 S2 F3 S3 F4 M1 F5 S5 F6 S6 F7 M2 F8
  What really happens: F1 S1 F2 S2 F3 S3 F4 M0 F5 S5 F6 S6 F7 M1 F8
• The game continues. Suppose Player I thinks he wins Step 9, i.e.
  M0 F1 S1 F2 S2 F3 S3 F4 M1 F5 S5 F6 S6 F7 M2 F8 S8 F9
  Note that Player II will not be better off if the extra move is not there, i.e. he still loses in the real situation
  F1 S1 F2 S2 F3 S3 F4 M0 F5 S5 F6 S6 F7 M1 F8 S8 F9

As we can see, this is a contradiction as Player II should be the winner. Therefore Player II cannot have a winning strategy.

The argument works on games like Hex, Chomp, Gomoku and Tic-Tac-Toe. However, it does not work on Chess, Chinese checkers and Go. However, it is believed that the first player most likely to be the winner.

4x4 Tic-Tac-Toe (II)

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

In the last blog, I have asked the following question:

If we consider the Tic-Tac-Toe game on a 4x4 board, then (a) is it possible to end in a draw? (b) does anybody have a nonlosing or winning strategy?

The answer for (a) is yes. The following is a possible draw game.

X	O	X	O
X	O	X	O
O	X	O	X
O	X	O	X

The answer for (b) is: There is a winning strategy for the first player.
His very first move:

	X

His second move, with Os indicate the possible moves of the second player:

O O O O X O O O X O O O O O

O         X X O O

Now we see, no matter how the second player corresponds, the first player is able to finish an unbroken row or an unbroken column of three X's.

It is trivial that the winning strategy is not unique. Moreover, this winning strategy works for a more strict version of Tic-Tac-Toe, meaning we don't allow diagonal row of X's.

In 1913, German mathematician Ernst Zermelo published a paper on game theory. He proved his famous Zermelo's theorem--

For any finite two-player games of perfect information in which the players move alternatingly and in which chance does not affect the decision making process, one of the players will always have a non-losing strategy. If the game cannot end in a draw, then this non-losing strategy is a winning strategy.

A finite game means the game will end in a finite number of steps. Perfect information means everyone knows all the possible consequences of any moves. There is no chance involved, therefore it excludes games like Contract Bridge and backgammon.

By Zermelo's Theorem, we know there will be non-losing strategies for Chess and Go. However, no one have yet found those winning strategies.
In 2007, scientists develop a never-losign program for English Draughts, making it the most complicated game ever solved. A list of solved games can be found here.

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.

$a^{\log_ax}=x$

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

This time, lets talk about a really simple equality, but it scares many high school kids. The equality is

$$a^{\log_ax}=x.$$

Those kids will say, "I know logarithms, but this equality is too complicated."

I ask, "Tell me what is $\log_ax$?"

They answer, "It is the answer of $a$ to the power of something equals $x$."

I say, "Write it down?"

They write, "It is the answer of $a^{(\ )}=x$."

I ask, "What is the answer?"

They confuse, "$\log_ax$?"

I say, "Write the answer inside ( )."

They write, "$a^{\log_ax}=x$."

I say, "Now you know."

They reply, "Know what?"

I say, "The equality is nothing but just the definition of $\log_ax$."

They complain, "I still don't understand!"

I ask, "Sigh! Lets start again. Do you know logarithm?"

They say, "I know logarithms, but this equality is too complicated."

Prove that 2n>n

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

(I am wondering if I shall add a "level-indicator" on the page, because somehow the level of knowledge is not quite even among my posts...)

Preliminary concept: A set is just a collection of objects. A (possible empty) part of the set is called a subset. The set consists of all subsets of a specified set is called the power set of the specified set.

e.g. A={1,2,3,4} is a set. { }, {1}, {1 3}, and A itself, are subsets of A. The power set of A is
P(A) ={{ }, {1}, {2}, {3}, {4}, {1,2}, {1,3}, {1,4}, {2,3}, {2,4},
{3,4}, {1,2,3}, {1,2,4}, {1,3,4},{2,3,4},{1,2,3,4} }

The power set of A, can be denoted by P(A) or 2^A. It is not hard to see that for a set with n elements, there is exactly 2ⁿ elements in the power set, hence we have the notation.

It looks obvious that 2ⁿ>n. Well, it is quite obvious when it is finite. 2³>3, 2⁴>4, how hard is that?

However, when n is infinite, 2ⁿ is also infinite. To compare two infinite sets is tricky. Well, it is easy to see that 2ⁿ≥n: If A={a,b,c,...} then the size of A is the same as {{a},{b},{c},...} which is a subset of P(A).

The hard part is: We have to make sure 2ⁿ≠n. In other words, we have to establish the fact that there is no one-to-one correspondence between A and P(A).

Consider a correspondence from A to P(A) such that any element a∈A corresponds to a subset S(a)∈P(A). Since A is infinite, we cannot write down all its elements, but we can have a local list:
....
α : ....α∈S(α)? β∈S(α)? γ∈S(α)? δ∈S(α)?
β : ....α∈S(β)? β∈S(β)? γ∈S(β)? δ∈S(β)? ....
γ : ....α∈S(γ)? β∈S(γ)? γ∈S(γ)? δ∈S(γ)? ....
δ : ....α∈S(δ)? β∈S(δ)? γ∈S(δ)? δ∈S(δ)? ....
....

It is a table of true and false. Now construct a new subset B containing only those element a such that the question a∈S(a)? is fales.

Note that if a∈S(a) then a∉B and so S(a)≠B; likewise if a∉S(a) then a∈B and so S(a)≠B. Hence the list

....α∈S(B)? β∈S(B)? γ∈S(B)? δ∈S(B)? ....

is different from any S(a) at exactly the a∈S(a)?-position. (We can see now it is exactly the Cantor's diagonal argument used in the previous two posts: Not enough names for numbers and  The are uncountably many subsets of natural numbers
)

Therefore no element of A corresponds to B and so this correspondence is not a one-to-one correspondence. As this is just any correspondence, so one-to-one correspondence cannot exist.

The are uncountably many subsets of natural numbers

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

In the post Not enough names for numbers, we prove that there are more real numbers between 0 and 1 than natural numbers, technically we say that the set of real numbers is uncountable. We now apply the same argument to prove that there are uncountably many real numbers made up entirely by 1 and 2 in the unit interval.

Consider a list of real numbers made up entirely by 1 and 2 in the unit interval:

0.α₁₁α₁₂α₁₃α₁₄α₁₅…
0.α₂₁α₂₂α₂₃α₂₄α₂₅…
0.α₃₁α₃₂α₃₃α₃₄α₃₅…
0.α₄₁α₄₂α₄₃α₄₄α₄₅…
……………

construct a real number B=0.β₁β₂β₃β₄β₅… such that β_j=1 if α_jj=2; 2 if α_jj=1.

Again this number B is not in the list. Hence there is never a complete list of such real numbers.

---

Lets consider a somewhat different problem. The set of natural numbers is {1,2,3,…}. Each subset S of natural numbers is corresponding to a unique real number α_S=0.α₁α₂α₃α₄α₅… in a way that α_j=1 if j∈S; 2 if j∉S, for example
α_{1,2}=0.1122…
α_{1,3,4}=0.121122…
α_{{2,4,6,8,…}}=0.2121212…

Suppose there is a given list of subsets of natural numbers, then we convert it to a list of numbers in the unit interval made up entirely by 1 and 2, then we have a B which is not in the list, and finally we convert B to a subset S_B={j β_j=1} which is of course not in the given list of subsets of natural numbers.

Can we construct S_B directly from the given list? Yes, we can!

S_B={j : j∉ the j-th subset in the list}

---

In the first part of the previous section, we have a correspondence that each subset of natural numbers S maps to a real number α_S in (0,1). Different subsets map to different real numbers in (0,1), and hence there is at least as many real numbers in (0,1) as the subsets of natural numbers.

Lets consider another correspondence. For each real number in (0,1), expressed in binary number system, for example 5/8=0.101000…. If α=0.α₁α₂α₃α₄α₅…, then let S_α={j : α_j=1}, for example S_0.101000…={1,3}. Different real numbers in (0,1) maps to different subsets of natural numbers, and hence there is at least as many subsets of natural numbers as real numbers in (0,1).

Combining, we see that there are as many subsets of natural numbers as real numbers.