February, 2017

Combinatorics Difficulty 4.7 AIME Prove it United States

Problem:

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

Solution

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 2r$ . 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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.