HMMT 十一月 2014 · 冲刺赛 · 第 35 题

HMMT November 2014 — Guts Round — Problem 35

[ 20 ] Ten points are equally spaced on a circle. A graph is a set of segments (possibly empty) drawn between pairs of points, so that every two points are joined by either zero or one segments. Two graphs are considered the same if we can obtain one from the other by rearranging the points. Let N denote the number of graphs with the property that for any two points, there exists a path from one to the other among the segments of the graph. Estimate the value of N . If your answer is a positive integer A , your score on this problem will be the larger of 0 and ⌊ 20 − 5 | ln( A/N ) |⌋ . Otherwise, your score will be zero.

解析

[ 20 ] Ten points are equally spaced on a circle. A graph is a set of segments (possibly empty) drawn between pairs of points, so that every two points are joined by either zero or one segments. Two graphs are considered the same if we can obtain one from the other by rearranging the points. Let N denote the number of graphs with the property that for any two points, there exists a path from one to the other among the segments of the graph. Estimate the value of N . If your answer is a positive integer A , your score on this problem will be the larger of 0 and ⌊ 20 − 5 | ln( A/N ) |⌋ . Otherwise, your score will be zero. Answer: 11716571 The question asks for the number of isomorphism classes of connected graphs on 10 vertices. This is enumerated in http://oeis.org/A001349 ; the answer is 11716571. 45 13 13 13 In fact, of the 2 ≈ 3 . 51 · 10 ≈ 3 · 10 graphs on 10 labelled vertices, virtually all (about 3 . 45 · 10 ) are connected. You might guess this by noticing that an “average” graph has 22 . 5 edges, which is fairly dense (and virtually all graphs with many edges are connected). Moreover, a “typical” isomorphism 6 class contains 10! ≈ 3 · 10 elements, one for each permutation of the vertices. So estimating the 13 3 · 10 7 quotient = 10 gives a very close estimate. 6 3 · 10