Math 308 2003 Term Project
Topic: A mathematical game - SIM
Student: Derek Kao
Student #: 85537991
Date: Dec 18, 2003
Index:
A mathematical game - SIM
Example - 6 points game
Proof - 6 points game
Pigeonhole Principle
Ramsey's Theorem
Reference
A
mathematical game
- SIM
It is a game
designed for two players, and each player draw a line by using one color between
two points. The player who gets a triangle with his color first loses the game.
The game can be played with any point which is lager or equal than six and the result
never be a draw.
Please click the picture or example.ps
to download the postscript file
in order to
see the full process of the example.
Click proof.ps download this example in postscript file.
1. Use 6 points game as an example for the proof.
2. Choose a point, then there are 5 separate lines connect to it.
3. Since we only have two players for this game (red and blue), so by applying
the Pigeonhole Principle
---we know that there must be 3 line in the same color, here we assume those 3
lines are in blue color.
4. Look at the lower left 3 points of the graph, connect the first line in
blue color will form a blue triangle.
5. Mark the first line with the red color instead and try next line.
6. Connect the second line will form another blue triangle.
7. Mark the second line with the red color instead and try next line.
8. Connect the third line will form another blue triangle.
9. Mark the third line with the red color instead but form a red triangle now.
Therefore, there must be at least one monochromatic triangle formed.
However, for 5 points game, it is possible to have no monochromatic triangle. We can simply draw:
Click the picture to download the postscript file
If there are X pigeons that live in X pigeonholes, then every pigeonhole
should have one pigeon.
If and only if there is a pigeonhole with more than one pigeon, then there must be
an empty pigeonhole left.
Therefore, we can also say that:
If there are X pigeons that live in Y pigeonholes and X is greater than Y, then
there must be a hole with more than one pigeon.
Ramsey's theorem states that every positive integers m and n, there exists r=R(m,n) which are any complete graph's vertices. Those edges between every vertices are marked in blue and red color, and there must be a monochromatic complete subgraph on r vertices with blue color or on s vertices with the red color.
By applying the pigeonhole principle, we know R(m,1) = R(1,m)=m. Here, we can
use the induction method for the proof. By finding a bound of R(m,n), so we know
R(m,n) exists and R(m-1,n) and R(m,n-1) also exist by mathematical induction.
Now we have to prove the statement: R(m,n)≤R(m-1,n)+R(m,n-1)
First of all, assume that there are R(m-1,n)+R(m,n-1) vertices on a complete
graph. Choose a vertex p from the complete graph and consider there are two
complete subgraphs X and Y. If and only if (p,q) is in blue color, and q is a
vertex in X. Otherwise q is a vertex in Y instead. At this point, using the
pigeonhole principle again, we can say either |M|≥R(m-1,n) or
|N|≥R(m,n-1). In the first case, if X has a red Kn,
then we prove the statement, otherwise X has a blue Km-1, and
we can know X a blue Km too by the definition. We can use
the similar technique to prove the second case.
Therefore, we proved the case for 2 colors.
How about the case with many colors? here we will prove the other case with c
colors.
we already prove the case with c=1 and 2, so let c>2 for the following
statement:
R(n1,...,nc;c)≤R(n1,...,nc-2,R(nc-1,nc;2);c-1)
First, we can know the inequality on the right hand side of statement exists by
the mathematical induction. Now consider a complete graph with many vertices and
with c colors to draw. Second, assume that we accidentally mix up c and c-1
color are the same color, so the total colors will become c-1 now. Thus, by
applying the induction method again, the graph will have a Kn1
monochromatically subgraph with color i (1≤i≤2) or a KR(nc-1,nc;2)
colored in "mixed-up color". In the first case, we proved the
statement. In the other case, we found out c and c-1 color are not the same
anymore and from the definition of R(nc-1,nc;2),
there must be either a monochromatic Knc-1
or a monochromatic Knc.
Therefore, we proved the case for c colors.
but there exist a special case which has c=2 and n1=n2=3
This is a table of all of the known Ramsey numbers of the form r=R(K_{m}, K_{n}) and some of the known lower/upper bounds for others:
m | n | R(K_{m}, K_{n}) | m | n | R(K_{m}, K_{n}) | |
---|---|---|---|---|---|---|
3 | 3 | 6 | 3 | 4 | 9 | |
3 | 5 | 14 | 3 | 6 | 18 | |
3 | 7 | 23 | 3 | 8 | 28 | |
3 | 9 | 36 | 3 | 10 | [40,43] | |
3 | 11 | [46,51] | 3 | 12 | [51,60] | |
3 | 13 | [60,69] | 3 | 14 | [66,78] | |
3 | 15 | [73,89] | 4 | 4 | 18 | |
4 | 5 | 25 | 4 | 6 | [35,41] | |
4 | 7 | [49,62] | 4 | 8 | [53,85] | |
4 | 9 | [69,116] | 4 | 10 | [80,151] | |
5 | 5 | [43,49] | 5 | 6 | [58,87] | |
5 | 7 | [80,143] | 5 | 8 | [95,216] | |
5 | 9 | [114,371] | 6 | 6 | [102,165] |
http://www.cut-the-knot.org/do_you_know/pigeon.shtml
http://hkumath.hku.hk/~wkc/MathModel/index.php?area=games&topics=SIM&page=home
http://en.wikipedia.org/wiki/sim
http://164.8.13.169/Enciklopedija/math/math/r/r066.htm