This quarter at Northwestern I'm taking "Mathematical Foundations of Computer Science" AKA Discrete Math. While most programmers I know personally tend to detest the more theoretical areas of computer science, I've always had a fascination with those types of problems. It just so happens that in the first class my professor (Nicole Immorlica) showed us a very elegant proof on the board. That week we also had a problem set that required a similar approach, although it was not obvious from the problem description. I figured I might as well write something about it for like-minded people and also for my own memory (can't forget the final!).
The first problem, I later figured out, is called the "mutilated chessboard" problem. The idea is that one is given a chessboard, but with two opposite corners cut out. The question is, is it possible to cover the entire board with dominoes such that every square is covered once and only once?
The mutilated chessboard.
The solution here is really a rather elegant one. Note that in the mutilated chessboard every square has a color associated with it. Also note that the "checker" pattern means that the colors are alternating—a white square never touches another white square orthogonally and vice versa. This implies that a domino covering two squares must cover one black and one white square. This also means that any number of dominoes on the board must cover an equal number of white and black squares. So can we cover the board with dominoes? No, because you'll notice that the two squares that have been removed from the chessboard are both black. This means that there are 32 white pieces on the chessboard, but only 30 black pieces, making complete coverage impossible.
The second problem we were presented with, at first glance, doesn't seem anything like the first problem. However, we will soon find that the same approaches can be used to prove a number of different suppositions about these problems. I have reproduced the problem text in full below:
Imagine an apartment complex with 3 floors, each of which contains 9 apartments arranged in a 3 × 3 grid. In each apartment there is a child who has lost a tooth. The tooth fairy must collect all the teeth, starting with the apartment on the ground floor in the southwest corner. Passing only through walls, ceilings, and floors, is it possible for her to collect the tooth of the child in the middle apartment last without leaving the building and while visiting each apartment just once?
The first trick is to represent our problems in a more generalizable form. As most computer scientists and mathematicians know, this representation is called a graph. I have built the graph for the apartment below. Each vertex in the graph represents a room, while each edge represents a path the fairy can travel. The graph is split into three separate floors for easy visualization, but simply imagine that each vertex is connected to the nodes above and below them.
The graph for the checkerboard is practically identical—I'll leave its creation as an exercise for the reader. The second trick is that we can actually phrase both the checkerboard and the apartment as the same type of graph, a bipartite graph.
A bipartite graph is a graph in which each of the vertices is a member of one of two disjoint sets. Moreover, each vertex must not have any edges to members of the same set. The two problems both qualify as bipartite graphs because of their orthogonal lattice structure. Since the names of the disjoint sets are arbitrary, we may as well name them "red" and "black." To reflect this, I've gone ahead and colored the graph appropriately.
Now that we've set up the problems as bipartite graphs, let's see what we can glean from the analysis.
The first property that we would like to study is whether or not someone can draw a given path through the graph. By noticing that every edge traversal in a bipartite graph touches a vertex from an alternate set we can derive Lemma 1.
>**Lemma 1**: Any path of *2n* length (number of vertices) will touch exactly *n* "red" vertices and *n* "black" vertices. Any path of length *2n+1* will touch *n+1* vertices of the set where the path starts and *n* vertices from the second set. Along the same lines, since we know that no two members of the same set can be adjacent vertices, we can derive some information about the start and end points of any path. >**Lemma 2**: Any path of length (number of vertices) *2n+1* will end on the same colored vertex as it started on. Any path of length *2n* will end on the opposite colored vertex. Note that since any graph cycle must start and end at the same vertex this leads to our first corollary for bipartite graphs. >**Corollary 1**: No cycles of odd length can exist in a bipartite graph. It also sets us up to solve some of the very problems we were dealing with. First we must introduce a new term: [Hamiltonian path](http://en.wikipedia.org/wiki/Hamiltonian_path). A Hamiltonian path is a path in a given graph which touches each and every vertex exactly once. Now that we have a bit more terminology, let's see if we can rephrase the homework problem to a bit more math-friendly form. >Given graph *G*, can one find a Hamiltonian path that starts at a corner vertex and ends at the middle vertex? Using Lemma 2 our answer is trivial: no. The total number of vertices in the graph is 3^3=27 (odd). Thus the Hamiltonian path will be 26 (even). Since the corner node is black and the center node is red, it is impossible for an even length Hamilonian path to exist. Hopefully this has given a little perspective on some of the elegant techniques in graph theory and also why it is so powerful. The models generated by graph theory are very generic and can thus be applied to many different problem domains, especially in computer science. One could easily write a depth-first search algorithm to test if a Hamiltonian path could exist, but rephrasing the problem first can save time and often yield unexpected results. I'll leave the reader with a simple exercise answerable from our lemmas—what can we say, if anything, about a bipartite graph with a Hamiltonian cycle?
