HMMT 十一月 2015 · 团队赛 · 第 9 题

HMMT November 2015 — Team Round — Problem 9

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

解析

[ 7 ] A graph consists of 6 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 V connected to at least one other vertex, it is possible to draw a path starting and ending at V that traverses each edge exactly once. What is the probability that the graph is good? Proposed by: Sam Korsky 10 9 507 2 − 10 2 − 5 Answer: or or 15 14 16384 2 2 First, we find the probability that all vertices have even degree. Arbitrarily number the vertices 1, 2, 3, 4, 5, 6. Flip the coin for all the edges out of vertex 1; this vertex ends up with even degree with 1 probability . Next we flip for all the remaining edges out of vertex 2; regardless of previous edges, 2 1 vertex 2 ends up with even degree with probability , and so on through vertex 5. Finally, if vertices 2 1 through 5 all have even degree, vertex 6 must also have even degree. So all vertices have even degree ( ) 6 1 1 15 with probability = . There are = 15 edges total, so there are 2 total possible graphs, of 5 2 32 2 10 which 2 have all vertices with even degree. Observe that exactly 10 of these latter graphs are not ( ) 6 1 10 good, namely, the graphs composed of two separate triangles. So 2 − 10 of our graphs are good, 2 3 10 2 − 10 and the probability that a graph is good is . 15 2 x