HMMT November, 2014

Combinatorics Difficulty 5.0 AIME Find the answer United States

Problem:
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 $\lfloor 20-5|\ln (A / N)|\rfloor$ . Otherwise, your score will be zero.

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:
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.

In fact, of the $2^{45} \approx 3.51 \cdot 10^{13} \approx 3 \cdot 10^{13}$ graphs on 10 labelled vertices, virtually all (about $3.45 \cdot 10^{13}$ ) 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 class contains $10!\approx 3 \cdot 10^{6}$ elements, one for each permutation of the vertices. So estimating the quotient $\frac{3 \cdot 10^{13}}{3 \cdot 10^{6}}=10^{7}$ gives a very close estimate.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.