Monday, December 31, 2012

Happy New Year!!!

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

Happy New Year!!!


Sorry I am a bit lazy, but it is a holiday season!

Lets end this year with a Nim game.

2013=(11111011101)
Lets play a Nim game with three heaps:

*****
***
*


Who will be the winner?

First heap's nimber is 5=(101),
second heap's nimber is 3=(011),
last heap's nimber is 1=(001).
So the nim sum is (101)+(011)+(001)=(111) which is nonzero. Therefore the first player has a winning strategy.

(111)+(101)=(010)=2, so the first player takes 3 and leaves 2 in the first heap.

Lets talk about binary numbers in the next blog.

Sunday, December 23, 2012

Nimbers, the numbers for Nim game

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

In previous posts, we have introduced some simple games. One of them is $G'(n)$, which consists a board with n pieces, two players in turn can take any number of pieces from the block, the winner is the one who takes the last piece.

Looks like a stupid game, right? The first player can take all pieces at his first step and win.

How about G'(3)+G'(7)? G'(2)+G'(6)+G'(5)? G'(11)+G'(6)+G'(8)+G'(3)?

Not so easy now. It is the famous Nim game. Some says that Nim originated from China, but no one can sure.

**
******
*****
The Nim game G'(2)+G'(6)+G'(5) consists of three heaps, each time a player can take away any number of pieces from a heap, the objective is to take the last piece.


To solve Nim, mathematicians have introduced the concept of nimber, which is basically ordinal numbers represented in binary numeral system under the position-wise boolean addition (i.e. 0+0=1+1=0, 0+1=1+0=1).

For example 3+7=(011)+(111)=(100)=4, 5+11=(0101)+(1011)=(1010)=10.

There is also nimber multiplication, which is omitted here.

Before we get into the relation between Nim and nimber, lets investigate the properties of nimber addition:
  1. n+m=0 if and only if n=m
  2. If n has a 1 at the 2k-th position and m is a k-digit nimber, then n+m<n. (The proof is easy: (1...1...)+ (1...)=(1...0...)<(1...1...). )
  3. If the nim sum of several nimbers is a k-digit nimber, then at least one nimber has a 1 at the 2k-th position.
  4. If the nim sum of several nimbers is 0, then replace any one of them by a different nonzero nimber, the new nim sum is nonzero. (Proof: Given n1+n2+...+nr=0. Suppose we replace the first nimber by m, then m+n2+...+nr=m+n1+n1+n2+...+nr=m+n1≠0.)
Now we are ready to study Nim.

For each heap, there are a nimber of pieces. Take the nim sum of the nimbers.
**
******
*****
The Nim sum of G'(2)+G'(6)+G'(5)is 2+6+5=(010)+(110)+(101)=(001).

The objective of the game is to take away all the pieces. At that last moment, the number of pieces is 0. From Property (4), if the nim sum is already 0, take away any number of pieces from a heap cannot keep the nim sum be 0, and therefore cannot win the game.

What if the nim sum, say m is a k-digit nimber?
From Property (3), there is a heap of which the nimber, say n, has a 1 at the 2k-th position. From Property (2), n+m<n. Take away some pieces fromt that heap so that there are n+m pieces left. The nim sum becomes
nim sum of all other heaps+(n+m)=(m-n)+(n+m)=m+m=0.

Therefore, the winning strategy is to maintain the nim sum to be 0. If the nim sum at the beginning is 0, the second player wins; if the nim sum at the beginning is nonzero, the first player wins.

Consider the game G'(2)+G'(6)+G'(5).
2=(10), 6=(110), 5=(101).
2+6+4=(10)+(110)+(100)=(001).
Only 5 have a 1 at the 1-th position. (101)+(001)=(100)=4, so the player has to left 4 in the last heap.

The game becomes G'(2)+G'(6)+G'(4).
The nim sum is 0. No matter the opponent does, he will disturb the balance. Suppose he takes away 3 pieces from the second heap.

The game becomes G'(2)+G'(3)+G'(4).
The nim sum is (101). The player now leaves (100)+(101)=(001)=1 pieces in the last heap.

The game becomes G'(2)+G'(3)+G'(1).

I suppose the readers can figure out the rest.

Thursday, December 20, 2012

Sum of games (2)

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

Suppose G is a first player's game and G' is a second player's game, what is G+G'?
It is still a first player's game. The first player moves on G at the first step. Note that the first player can force the opponent to be the first player on G'. Why? Because G is a first player's game, and so sooner or later the second player cannot make a move on G and have to move on G'.

Suppose G is L's game and G' is a first player's game.
Consider the following game:
  • L(n) consists of a board with n pieces. L can take away any number of pieces at his turn but R can only take away a piece. Obviously, L(1) is a first player's game but L(n) is always L's game.
L(2)+L(1) is a first player's game. No matter L or R makes the first move, he will take away a single piece from L(2) and win the game.
L(3)+L(1) is L's game. If L makes the first move, he will take away two pieces from L(3) and win; if R makes the first move, the new configuration is either L(3) or L(2)+L(1) with L being the first player, so L wins.

Suppose G is L's game and G' is a second player's game.
Suppose R is the first player. If R takes G' then he will lose on both G and G'. However if R takes G which is L's game, then sooner or later he will be forced to make a first move on G' and he will also lose. Suppose L is the first player, then obvious he will make his first move on G and force R to be the first player on G', and then he can win. G+G' is L's game.

In the last two cases, if G is R's game, the argument is similar.

Suppose G is L's game and G' is R's game.
Consider L(n) and R(n), i.e., the game identical to L(n) but the roles of L and R interchanged.
L(2)+R(2) is the second player's game.
L(3)+R(2) and L(2)+R(3) are both first player's games. No matter who moves first, he can change it to L(2)+R(2) with himself being the second player.
L(4)+R(2) is surely L's game. If L moves first, he will make it L(2)+R(2).
L(2)+R(4) is surely R's game.

We can see that L(n)+R(n) is always a second player's game. It is because the second player can make a mirror copy of the first player's move, and therefore he will never be the one who cannot make a legitimate move.
Indeed, if G=(GL|GR) is a game, then we define a new game -G=(-GR|-GL), i.e. the game with the role of L and G interchanged, then G + (-G) is always a second player's game.

Suppose G1=G+(second player's game). We have
  1. If G is a first player's/second player's/L's/R's game then G1 retains the same property.
  2. G1+(-G)=(second player's game).
Technically speaking, the set of second player's games forms an identity element under the addition operations.

Sum of games (1)

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

In the previous two blogs, we see that a nominal game (i.e. player who makes the last move wins) can be defined as G=(GL|GR) where GL (R resp.) is the set of possible configurations after L (R resp.) makes the first move.

Indeed, we can add two nominal games G=(GL|GR) and G'=(G'L|G'R) together and form a new nominal game. Symbolically, it is
G+G'=(GL+G', G+G'L | GR+G', G+G'R)
where the sum is defined recursively.

What does it mean exactly? Indeed, we simply put the two games side by side, and at each step, the player can make a move on either game.

What is the effect on the games?

Suppose both G and G' are games that the second player wins.
If the first player moves on G, then the second player moves on G; if the first player moves on G', then the second player also moves on G'. The second player is still the second winner on both G and G' and therefore he wins on both games. In other words, G+G' is still a second player's game.

Suppose both G and G' are games that L (R resp.) wins.
It is trivial that L (R resp.) is still the winner.

Suppose both G and G' are games that the first player wins.
It is a bit more complicated. Consider the following two games:
  • G(n) consists of a board with n pieces on it. Two players in term takes a piece from the board. The player who takes the last piece wins.
  • G'(n) consists of a board with n piece on it. Two players in term can take arbitrary number (possibly all) of pieces from the board. The player who takes the last piece wins.
Obviously, G(n) is a first player's game if n is odd but a second player's game if n is even, and G'(n) is always a first player's game-the first player can take everything at the first move.

G(1)+G(1)=G(2), so the sum of two first player's games can be a second player's game.
G(1)+G'(2) is, however, a first player's game. At the very first move, the first player will take away a piece from G'(2) and the new configuration is G(2) with himself as the second player. Therefore, he wins.

Can you figure out the remaining four cases?

Tuesday, December 11, 2012

"number" game

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, we know that there are "number" games n+1=(n| ) and -(n+1)=( |n). It is easy to see that in all positive integers, L will be the winner. Indeed, for any games of the form ((X| )| ), L will be the winner, as R can never be able to make a move.

How about negative integers ( |n)? If L is the first player, he loses as he cannot make a move. If R is the first player, the next configuration is the game n, and R is the loser. Therefore the second player will always be the winner.

Lets consider ( |-n). Who wins?
If L is the first player, he loses. If R is the first player, the next configuration is the game -n with L makes the first move -- but for the game -n, the one who makes the first move loses--and so L loses again. It is a game that R wins.

Lets consider (n|-m). Who wins?
If L is the first player, the next configuration is n, and so L wins. If R is the first player, the next configuration is -m with L makes the first move, and so R wins. It is a game that the first player wins.

Lets consider a little bit more complicated ( |n,-m). Who wins?
If L is the first player, he loses. If R is the first player, he can choose the next configuration to be n or -m (and L makes the first move): If R chooses n, he loses; if R chooses -m, he wins.
It is a game that there is no definite winner, but R has a winning strategy - choosing -m if he is the second player.

Lets consider (n|n, -m). Who wins?
If L is the first player, he wins. If R is the first player, he wins only if he chooses -m.
It is a game of which the first player has a winning strategy.

Lets consider (( |n,m),( |-n)|n, -m). Who wins?
Again, it is a game that the first player has a winner strategy: If L is the first, he should choose ( |n,m); If R is the first, he should choose -m.

It is not that complicated, right.....?

Saturday, December 8, 2012

zero game

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

John Conway,Elwyn Berlekamp and Richard Guy together invented a theory for general two-player games. The term "general" here means that the game may not be identical to the two players, meaning the two players can have different game options.

Let we say the two players be L and R. A game is defined as an ordered pair (GL | GR), where GL (resp. GR) is the set of all possible configurations if L (resp. R) is the one who make a move.

A zero game 0=( | ) is the game that the first player automatically loses, because neither L nor R has a valid move.

( | 0) is the game that L must lose. If L is the first player, he has no valid move. If R is the first player, the configuration will become 0, and L being the next player has no valid move.

(0 | ) is the game that R must lose.

The star game *=(0 | 0) is the game that the second player will lose.

We have 0 game. We also have other "number" games:
1=(0 | )
2=(1 | )
3=(2 | )
4=(3 | )
....

-1=( | 0)
-2=( | 1)
-3=( | 2)
-4=( | 3)
....


It is possible to include all the numbers, some represents games with infinitely many configurations.

Invented by John Conway, the concept of games as numbers where first introduced to the public through a story book by Donald Knuth: Surreal Numbers: How Two Ex-Students Turned on to Pure Mathematics and Found Total Happiness. It is a rare case that a new concept is introduced this way. The name Surreal Number is given by Donald Knuth and is adopted by John Conway.

Like other number systems, the surreal numbers can add, subtract, multiply and divide.

A little exercise: For games 1,2,3,..., -1,-2,-3,...., which player (L, R, first player, second player) is the winner?

(Please also remember the name Donald Knuth, he is the creator of TeX, the standard typesetting system for most mathematical publications.)

Saturday, December 1, 2012

Tic-Tac-Toe related games

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

On the web, I have crossed over two 3D versions of Tic-Tac-Toe. One is called FourSight, it is played on a four-layer of 4 by 4 boards, the objective is to be the first one joining a line of 4 X's or O's. Another one is played on a three-layer of 3 by 3 boards, the objective is to seize as many lines as possible.

It is easy to see, for these two and many other similar games, an extra piece is always an advantage. Then using Nash's Strategy-Stealing Argument mentioned in a previous post, the first player has a strategy that he will never lose. The fun for those games for me, as a mathematician, is to find the winning strategy.

Now consider the original Tic-Tac-Toe, but the player who first gets a line of 3 is declared to be the loser. Is the new game always ended in a draw as the original one? Or does one of the players have a winning strategy?

FourSight from www.mathsisfun.com

Note that in the new game, an extra piece is a disadvantage. Therefore, it is unlikely that the first player has a winning strategy. However, the first player has a simple drawing strategy:
  1. The first player captures the middle space in his first move.
             
        X    
             
  2. Then he mirrors the second player's moves.
    O       
        X    
           X
    O       
    X X O
           X
  3. In this way, the first player is sure that he will get a line of 3 only after the second player gets it. Unless the second player is careless, the game will always end in a draw.


In combinatorical game theory, there are two types of two-player games: The normal game, where the player who makes the last move wins; the misère game, where the player who makes the last move loses.

The original Tic-Tac-Toe is a normal game, the new version is the misère game. There is a rich theory on normal games, but relatively few on misère games. We will have a look of the mathematical background in the coming posts.

Tuesday, November 27, 2012

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.
816
357
492
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.

Wednesday, November 21, 2012

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.

Thursday, November 8, 2012

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.
XOXO
XOXO
OXOX
OXOX


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 OO
OXOO
OXOO
O OO
   
   O      
XX
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.

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.

Wednesday, October 24, 2012

$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."

Thursday, October 18, 2012

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 2A. It is not hard to see that for a set with n elements, there is exactly 2n elements in the power set, hence we have the notation.

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

However, when n is infinite, 2n is also infinite. To compare two infinite sets is tricky. Well, it is easy to see that 2n≥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 2n≠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 aA 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 aB and so S(a)≠B; likewise if a∉S(a) then aB 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.

Sunday, October 14, 2012

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.α11α12α13α14α15
0.α21α22α23α24α25
0.α31α32α33α34α35
0.α41α42α43α44α45
……………

construct a real number B=0.β1β2β3β4β5… 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.α1α2α3α4α5… 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 SB={j βj=1} which is of course not in the given list of subsets of natural numbers.

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

SB={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.α1α2α3α4α5…, then let Sα={j : αj=1}, for example S0.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.

Monday, October 8, 2012

Not enough names for numbers

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

Napier's constant, Pi, Planck constant, golden ratio, etc. We have given names to many special numbers. However, there are far many numbers than our human language can handle. It is not a philosophical statement, it is a true mathematical theorem which is surprisingly simple to prove.

A language consists of phrases which are finite sequences of a finite set of symbols. English phrases, for example, are finite sequences of 'a' to 'z' and the empty space. If we assign an ordering of the symbols, then we also assign an lexographical order of phrases. If we assign 'a'<'b'<...<'z'<' ', we will have 'ab cd'<'acbde'<'a bac'. In other words, all possible phrases in a language can be listed.

We are now going to prove that the set of all real numbers between 0 and 1 cannot be listed, and hence there are far more numbers than possible words:

Suppose on the contrary, the set of all real numbers between 0 and 1 can be listed as follows

0.α11α12α13α14α15
0.α21α22α23α24α25
0.α31α32α33α34α35
0.α41α42α43α44α45
……………

Now, construct a real number 0.β1β2β3β4β5… such that βj≠αjj, 0 and 9.

Under this special construction, the new number is different from the j-th number in the list, as they have different j-th digits. (Note that two numbers with different digits can be the same, e.g. 0.10000… and 0.09999… but this will not happen in our construction.) Therefore, the new number is not in the list of all real numbers between 0 and 1, which is obviously a contradiction.

The above construction is the famous Cantor's diagonal argument by Georg Cantor (1845-1918).  This seemingly simple technique is indeed rather powerful, it is used in the arguments for Russell's paradox, the first of Gödel's incompleteness theorems, and Turing's answer to the Entscheidungsproblem.

Thursday, October 4, 2012

$\cos \theta=2$

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

Question: Write down one solution to each of the following:

(a) $\cos \theta=0.5$
(b) $\cos \theta=1$
(c) $\cos \theta=-0.17$
(d) $\cos \theta=2$

Note that there is no ° in the question, so the answer should be in radian.

A high school student could do (a) and (b) without a calculator. Calculator will give a solution of (c) with $\pi/2<\theta<\pi$. For (d), school algebra tells us that there is no solution, as the value of cosine lies in between -1 and 1 -- however, it is not the case if we consider complex number.

There are three definitions of cosine:

1. As the ratio of the adjacent to the hypotenuse in a right angled triangle.  Under this definition, $\theta$ can only be $0<\theta<\pi/2$ and we have $0<\cos \theta<1$.

2. As the $x$-coordinate of point with polar coordinate $(1, \theta)$. Under this definition, $\theta$ can be any real number and it is still true that $-1\le \cos \theta\le 1$.

3. By the formula discovered by Leonhard Euler (1707-1783):
$$\cos \theta=1-\frac{1}{2!}\theta^2+\frac{1}{4!}\theta^4-\frac{1}{6!}\theta^6+\cdots$$
or equivalently
$$\cos \theta=\frac{e^{i\theta}+e^{-i\theta}}{2}.$$
Nowadays, the study of wave behaviour in physics and modern axiomatic approach in mathematics, cosine is no more an "angle" thing, and therefore Euler's formula serves as a better definition.

By using Euler's formula, we can have the cosine of a complex number.
$$\begin{eqnarray*}
\cos\theta&=&2\\
\frac{e^{i\theta}+e^{-i\theta}}{2}&=&2\\
e^{i\theta}+e^{-i\theta}&=&4\\
1+(e^{-i\theta})^2&=&4e^{-i\theta}\\
(e^{-i\theta})^2-4e^{-i\theta}+1&=&0
\end{eqnarray*}$$
One solution of the quadratic equation is $e^{-i\theta}=2+2\sqrt{3}$ and hence one solution of (d) is $\theta=i\log_e(2+\sqrt{3})$.

Tuesday, October 2, 2012

The two meanings of $\sqrt{4}$

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

What is wrong with the following expression?

$$4=\sqrt{16}=\sqrt{-4 \times -4}=\sqrt{-4}\times \sqrt{-4}=-4.$$

It seems easy. $\sqrt{-4}$ doesn't make sense. Right? Well, yes and no.

If we just consider the usual real numbers, then square of any number is positive and $\sqrt{-4}$ simply does not exists.

However, there is something called complex numbers.  For complex numbers, square can be negative.  In this case, there are two ways of interpreting $\sqrt{-4}$.

1.  $\sqrt{-4}=2 i$, where $i$ is the imaginary unit.  In this case, the equality $\sqrt{-4 \times -4}=\sqrt{-4}\times \sqrt{-4}$ does not hold.

2. $\sqrt{-4}=\{ \pm 2 i \}$, i.e. it is a set.  We would also reinterpreting $\sqrt{16}=\{\pm 4\}$. In this case, we have
$$\{\pm 4\}=\sqrt{16}=\sqrt{-4 \times -4}=\sqrt{-4}\times \sqrt{-4}=\{\pm 2\}\times\{\pm 2\}=\{\pm 4\},$$
here we use element-wise multiplication of two sets.

In general, there are two different meanings of $\sqrt{x}$.

1. $\sqrt{x}$ is the unique positive square root of $x$, if $x>0$; $\sqrt{0}=0$; $\sqrt{x}=\sqrt{-x}i$ if $x<0$;  any one of the square root of $x$ if $x$ is not a real number.  Under this meaning, we have $\sqrt{ab}=\sqrt{a}\times\sqrt{b}$ only if at least one of $a$ and $b$ are nonnegative.

Under this meaning, the formula for the quadratic equation $ax^2+bx+c=0$ is $\frac{-b\pm\sqrt{b^2-4ac}}{2a}$.  As we have extended the definition of $\sqrt{\cdot }$, this formula now makes senses for any complex numbers $a\ne 0$, $b$ and $c$.

2. $\sqrt{x}$ is the set consists of the two roots of $x$.  Indeed, we can generalize it to $\sqrt[n]{x}$ being the set of all $n$-th roots of $x$.  For this meaning, we have $\sqrt[n]{ab}=\sqrt[n]{a}\times\sqrt[n]{b}$ for all complex numbers $a$ and $b$.

The formula for the quadratic equation is now simply $\frac{-b+\sqrt{b^2-4ac}}{2a}$, which is indeed the set of the two solutions.

Thursday, September 27, 2012

What is a number?

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

What is a number?

In mathematics, there is no formal definition for "number".

Really?

We have definition for natural number, negative number, rational number, complex number, real number, p-adic number, hyperreal number, cardinal number, ordinal number, etc. We just don't have the definition for "number".

Isn't mathematics a subject of vigor? How come such an extensively used term have no formal definition?

Mathematics is a subject of vigor, but the use of language is not. Indeed, at the very beginning, "number" just refers to the counting number: 1,2,3,... Latter, the need to record different types of quantities force humans to extend the number system. Just as other branch of knowledge, we like to expand the meaning of the existing names, other than invent a new name-- we do this because we would have a ridiculous large dictionary otherwise.

Indeed, even if we don't mind to have an infinitely large dictionary, we still cannot afford to have one name for one mathematical object. There are much more real numbers than all possible finite combinations of alphabets!

Monday, September 24, 2012

Marriage Problem

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

女孩:我想知道姻緣。
相士:您一生會遇到十個要娶您的男人。
女孩:哪一個是最好?
相士:天機不可涉漏!
女孩:!!!

Girl: I want to know my future.
Fortuneteller: I see. You will meet ten men that want to marry you. 
Girl: Who will be the best?
Fortuneteller: Oh, I just can't tell!
Girl: !!!

In many Hong Kong old films, there is a know-all who loves to do fortunetelling but hold back the most important bit, and hence tragedy happens.

As the story goes, several guys have proposed to the girl, but she refuses as she dreams to have a better one coming.  The latter are worse and worse. As the magical "ten" approaches, she panics and gets married, and it turns out the best is just around the corner.

Not really too tragic. However, if the girl knows some mathematics, she may have a higher chance to marry the best one: She should refuse the first three men and she must marry once she meet a guy who is better than the first three men.

Using this strategy, her chance of marrying the best one is $0.44$, whereas if she makes her decision randomly, her chance is just $0.10$.

In general, suppose the girl knows that there will be $N$ men and she marries the first one who is better than the first $k$ guys, then her chance of marrying the best one is $$\frac{k}{N}\sum_{i=k}^{N-1}\frac{1}{n}.$$
How do we come up with this probability?
Well, the probability that the $(i+1)$-th one is the best is $\frac{1}{N}$. In this case, the girl may marry him only if the best among the first $i$ guys is one of the first $k$ guys, and hence the probability is $\frac{k}{i}$.
To find the optimal $k$ is not easy for large $N$, but it is not that hard to see that (Can you do it?) $$(N-\frac34)^{1/2}-\frac14\le k\le \frac{N}{2}.$$ In our case, $N=10$ and the optimal $k$ is $3$.

The mathematics problem has a name: Marriage Problem. (Note there are other mathematics problems of the same name.) Its another name is Secretary Problem.

Lets end this with one very important point: The girl can achieve the highest probability only if she sticks with the strategy!

Thursday, September 20, 2012

Complex Number and Treasure Hunting

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

It is a well-known story among mathematics lovers, but relative unknown to outsiders:

"A guy gets a map of a treasure island. On the map, it writes: There are an oak, a pine and a gallows. Walk from the gallows to the oak, counting the steps, turn 90 degrees right and walk the counted number of steps, then mark the position. Walk from the gallows to the pine, counting the steps, turn 90 degrees left and walk the counted number of steps, then again mark the position. The midpoint of the two marks is where the treasure buried.

The guy arrives at the island, he find the oak and the pine, but the gallows is already gone without a trace..."

Simply google "treasure and complex number" and you will find many websites on this question. The pure geometric solution is not hard but a bit complicated. The simplest solution involves using the complex numbers.

A complex number is an entity of the form $a+bi$, where $a$ and $b$ are the usual real numbers and $i=\sqrt{-1}$ is a square root of $-1$. Indeed, each complex number $a+bi$ can be identified with the point $(a,b)$ on the plane.

If $Z=a+bi$ is a complex number, then $Zi=-b+ai$ is the complex number obtained by rotating $Z$ with 90 degrees left about the origin, whereas $Z(-i)=b-ai$ is the complex number obtained by rotating $Z$ with 90 degrees right about the origin.
If $Y=c+di$ is another complex number, then $W=Z+Y=(a+c)+(b+d)i$ is the complex number obtained by moving $ZO$ to $WY$.
Now, we take the midpoint between the oak and the pine as the origin, and take the oak and the pine as the $1$ and $-1$ respectively on the complex plane. Now, we let $G$ to be the gallows. The first mark is therefore $-i(G-1)+1$ and the second mark is $i(G+1)-1$ (Check them yourself!), and so the treasure is at $((-i(G-1)+1)+i(G+1)-1))/2=i$, independent of the position of the gallows. The solution!

Sunday, September 16, 2012

The amazing NAND

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

In daily language and mathematical articles, we frequently use the four basic logical operations: "not", "and", "or", "if-then". However, in electronics, the most fundamental logical operation is "nand" -- the NAND ("not and") operation can be used to implement other logical operations.


The symbol for NAND gate.

The truth table of NAND is $$\begin{array}{c|c|c} p&q&p|q \\ T & T & F \\ T & F & F \\ F & T & F \\ F & F & T \end{array}$$ In other words, the output is false only if both $p$ and $q$ are true. (Note that apart from $p|q$, there are other symbols for NAND, for example $p\bar{\wedge}q$, see here.)

From NAND we can construct the four basic logical operations, which are the building blocks of the symbolic logic:

  • Negation: Not $p$. $$\begin{array}{c|c} p&\neg p\\ T & F\\ F & T \end{array}$$ By comparing its truth table with the truth table of $p|p$, we see that $$\neg p = p|p.$$
  • Conjunction: $p$ and $q$. $$\begin{array}{c|c|c} p&q&p\wedge q \\ T & T & T \\ T & F & F \\ F & T & F \\ F & F & F \end{array}$$ The output is true only if both $p$ and $q$ are true. It turns out that $$p \wedge q = (p|q)|(p|q).$$ Note also that $p|q = \neg (p\wedge q)$, i.e. "$p$ NAND $q$" is indeed "Not ($p$ AND $q$)".
  • Disjunction: $p$ or $q$. $$\begin{array}{c|c|c} p&q&p\vee q \\ T & T & T \\ T & F & T \\ F & T & T \\ F & F & F \end{array}$$ The output is false only if both $p$ and $q$ are false. It turns out that $$p \vee q = (p|p)|(q|q).$$
  • Conditional: If $p$ then $q$. $$\begin{array}{c|c|c} p&q&p\rightarrow q \\ T & T & T \\ T & F & F \\ F & T & T \\ F & F & T \end{array}$$ The output is false only if $p$ is true but $q$ is false. It turns out that $$p \rightarrow q = p|(q|q).$$
It is also possible to build all the logical operations from the NOR ("not or") operation.

Tuesday, September 11, 2012

Triangle Centroid and Position Vectors

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

We can treat points in a plane as position vectors (or simply vectors). If you have not heard about vectors before, they are mathematical objects that we can perform addition and scalar multiplication (i.e. scaling).

For instance, given two points A and B, the point X which lies on the line joining A and B such that AX:XB=r:1-r can be written as

X=(1-r)A+rB

Note that r can be any number. If r<0 then X lies on the BA extended; if 0 then X lies on the line segment AB; if r>1 then X lies on the AB extended.

In particular, 0.5A+0.5B is the mid-point of AB.

Now, given three points A, B and C. Consider

M=1/3 A+1/3 B+1/3 C

Now M=1/3 A+(2/3)(0.5B+0.5C), and so M indeed lies on the median joining A and the mid-point of BC. Likewise, it lies on the other two medians.

Therefore M is the centroid of the triangle ABC. Moreover, from the formula, we can tell that it always divides the medians in the ratio 2:1.