Last two weeks
Tutorial
| Combinatorial game theory | Nim is a 2 player
game. At the start of the game, there are 3 piles of
tokens. Players take turn choosing one pile and removing a positive
number of tokens from the chosen pile. The player to taken the last
token wins.
In a variant of this game, there is only one pile of tokens but
players must remove either 1, 7 or 10 tokens from the pile when it
is their turn
We look at how to win at these and other turn based full information
games. |
| Four colour theorem | The four colour theorem is a famous
problem in graph theory. The theorem states that the regions of any
map can be coloured with four colours so that regions sharing a
border receives different colours
Although the theorem is simple to state. Its proof is surprisingly
difficult. An interesting, but less well know, fact about this proof
is that it is computer assisted. That is at some points in the
proof, a computer is used to check hundreds of cases.
We look at the proof on a high level and see just how a computer is
used. |
| Counting labelled trees | Determining the number of
(unlabelled) graphs with n vertices
is difficult. However, determining the number of labelled graphs is
easy. Suppose instead we want to determine the number of labelled
trees. It turns out that there is a very nice bijection for
counting labelled tree. This is know as the Prüfer sequence.
We look at the simple algorithm which turns a tree into a number
and back. |
| Combinatorial design | Suppose we building large complex
system which has many "switches" which can be individually set to "on"
or "off". We want to make sure our system does not break but it would
take too much time to test all combination of switch states. It was
noticed that if the system breaks, it is due to a combination of a
small number of switches. We would like to design a series of tests
(in each test, we set each switch to some state "on" or
"off").
We use combinatorial designs to show that few tests are needed.
|
|