jump to navigation

Problem of the Day #404: Biking Paths April 26, 2012

Posted by Saketh in : potd , trackback

The city planning committee is laying down a set of bike trails between $n$ major attractions. They plan to submit a proposal asking for $kn$ of the $\binom{n}{2}$ possible trails to be built, where $k$ is some constant.

To accommodate athletes who wish to perform laps, the committee wants to guarantee that a cycle of length $4$ will be built. However, they don’t know which $kn$ trails will be chosen. What is the least value of $k$ for which a cycle of length $4$ will definitely exist?


no comments yet - be the first?