jeffreyxiao
Hi! I'm a student at the University of Waterloo studying software engineering. I have an interest in large scale distributed algorithms and infrastructure for data analytics. I also enjoy working with low level systems.

Harvard MIT Math Tournament

Tuesday, November 24, 2015

CompetitionMath

Team Photo in Front of MIT
Team Photo in Front of MIT

Introduction

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.

Theme Round: Question 8

Problem Statement

Consider a 888*8 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?

Solution

Let AA represent the set containing point (8,8)(8, 8), BB represent the set containing the points reachable from (8,8)(8,8) with one move, and CC represent the set containing all other points

Visually, the sets looks like this:

[BBBBBBBACCCCCCCBCCCCCCCBCCCCCCCBCCCCCCCBCCCCCCCBCCCCCCCBCCCCCCCB]\begin{bmatrix} B & B & B & B & B & B & B & A \\ C & C & C & C & C & C & C & B \\ C & C & C & C & C & C & C & B \\ C & C & C & C & C & C & C & B \\ C & C & C & C & C & C & C & B \\ C & C & C & C & C & C & C & B \\ C & C & C & C & C & C & C & B \\ C & C & C & C & C & C & C & B \end{bmatrix}

We can make the observation that there are 1414 valid moves from any position, 22 ways to get to BB from CC, 77 ways to get to AA from BB, and 11 way to get to AA from BB. Using this observation, we can formulate a series of state transitions.

E(CB)=214E(CC)=1214E(BA)=114E(BB)=614E(BC)=714\begin{aligned} E(C \rightarrow B) &= {2 \over 14} \\\\ E(C \rightarrow C) &= {12 \over 14} \\\\ E(B \rightarrow A) &= {1 \over 14} \\\\ E(B \rightarrow B) &= {6 \over 14} \\\\ E(B \rightarrow C) &= {7 \over 14} \\\\ \end{aligned}

Using the probabilities of state transitions, we can create equations that relate the expected value of reaching state AA from the other states.

E(A)=0E(B)=1+E(A)14+6E(B)14+7E(C)14E(C)=1+2E(B)14+12E(C)14\begin{aligned} E(A) &= 0 \\\\ E(B) &= 1 + {E(A) \over 14} + {6E(B) \over 14} + {7E(C) \over 14} \\\\ E(C) &= 1 + {2E(B) \over 14} + {12E(C) \over 14} \\\\ \end{aligned}

Simplifying:

8E(B)=14+7E(C)E(C)=7+E(B)E(C)=7+148+7E(C)8E(C)8=708E(C)=70\begin{aligned} 8E(B) &= 14 + 7E(C) \\\\ E(C) &= 7 + E(B) \\\\ E(C) &= 7 + {14 \over 8} + {7E(C) \over 8} \\\\ E(C) \over 8 &= {70 \over 8} \\\\ \therefore E(C) &= 70 \\\\ \end{aligned}

Team Round: Question 9

Problem Statement

A graph consists of 66 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 VV connected to at least one other vertex, it is possible to draw a path starting and ending at VV that traverses each edge exactly once. What is the probability that the graph is good?

Solution

If it is possible to draw a path starting at vertex VV and ending at vertex VV 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 (63)(33)=20\binom{6}{3} * \binom{3}{3} = 20 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 n1n-1 vertexes and the Eulerian graphs with nn vertexes. For every graph with n1n-1 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.

# of Eulerian Graphs=2(n12)=2(n1)(n2)2=1024# of Good Graphs=102420=1004\begin{aligned} \text{\# of Eulerian Graphs} &= 2^{\binom{n-1}{2}} \\ &= 2^{(n-1)(n-2) \over 2} \\ &= 1024 \\ \text{\# of Good Graphs} &= 1024 - 20 \\ &= 1004 \\ \end{aligned}
Introduction
Theme Round: Question 8
Problem Statement
Solution
Team Round: Question 9
Problem Statement
Solution
Previous Post
First Blog Post
Next Post
Hack Western