On November 14th, my school sent two teams to the Harvard MIT Math Tournament. The competition comprised of two individual (General and Theme) rounds and two team rounds (Team and Guts). The problems were rather difficult, but had elegant solutions. Here are two problems that I found interesting.
Consider a grid of squares. A rook is placed in the lower left corner, and every minute it moves to a square in the same row or column with equal probability (the rook must move; i.e. it cannot stay in the same square). What is the expected number of minutes until the rook reaches the upper right corner?
Let represent the set containing point , represent the set containing the points reachable from with one move, and represent the set containing all other points
Visually, the sets looks like this:
We can make the observation that there are valid moves from any position, ways to get to from , ways to get to from , and way to get to from . Using this observation, we can formulate a series of state transitions.
Using the probabilities of state transitions, we can create equations that relate the expected value of reaching state from the other states.
A graph consists of vertices. For each pair of vertices, a coin is flipped, and an edge connecting the two vertices is drawn if and only if the coin shows heads. Such a graph is good if, starting from any vertex connected to at least one other vertex, it is possible to draw a path starting and ending at that traverses each edge exactly once. What is the probability that the graph is good?
If it is possible to draw a path starting at vertex and ending at vertex traversing each edge exactly once, the graph is known as an Eulerian graph. In order for that condition to hold true, every vertex must have an even degree (I.E. there must be an even number of edges connected to the vertex). For a graph with six vertexes, we can notice that there are a couple of graphs which have an Eulerian cycle, but are not good. These graphs have the two distinct cycles of size three.
There are graphs with this property.
All that is left is to count the number of labelled Eulerian graphs. We can make the observation that there is a one-to-one correspondence between the valid graphs with vertexes and the Eulerian graphs with vertexes. For every graph with vertexes, we add a vertex and connect it to all the vertexes with odd degree. This will produce a valid Eulerian graph because it forces all the vertexes to have degree two. Notice that there cannot be an odd number of vertexes with odd degree because the degrees of all the vertexes must add up to an even number. Thus once we connected the new vertex to all the odd degree vertexes, the new vertexes will have an even degree.