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

英文解析

9. [ 7 ] A graph consists of 6 vertices. For each pair of vertices, a coin is flipped, and an edge connectingthe two vertices is drawn if and only if the coin shows heads. Such a graph is good if, starting fromany vertex V connected to at least one other vertex, it is possible to draw a path starting and endingat 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 withprobability . Next we flip for all the remaining edges out of vertex 2; regardless of previous edges,1
   vertex 2 ends up with even degree with probability , and so on through vertex 5. Finally, if vertices 12
   1 through 5 all have even degree, vertex 6 must also have even degree. So all vertices have even degree 2
   ( )
   1 1 156
   with probability = . There are = 15 edges total, so there are 2 total possible graphs, of
   2 32 25
   which 2 have all vertices with even degree. Observe that exactly 10 of these latter graphs are not 10
   ( )
   1 106
   good, namely, the graphs composed of two separate triangles. So 2 − 10 of our graphs are good,
   2 3
   2 − 1010
   and the probability that a graph is good is .
   x 215