HMMT February

Combinatorics Difficulty 5.2 AIME, harder Find the answer

Let $r$ be a positive integer. Show that if a graph $G$ has no cycles of length at most $2 r$ , then it has at most $|V|^{2016}$ cycles of length exactly $2016 r$ , where $|V|$ denotes the number of vertices in the graph G.

Your answer

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

Solution

The key idea is that there is at most 1 path of length $r$ between any pair of vertices, or else you get a cycle of length $\leq 2 r$ . Now, start at any vertex ( $|V|$ choices) and walk 2015 times. There's at most $|V|^{2016}$ ways to do this by the previous argument. Now you have to go from the end to the start, and there's only one way to do this. So we're done.

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: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.