MathDB
flights

Source: Ireland 2007

July 6, 2009
combinatorics unsolvedcombinatorics

Problem Statement

Air Michael and Air Patrick operate direct flights connecting Belfast, Cork, Dublin, Galway, Limerick, and Waterord. For each pair of cities exactly one of the airlines operates the route (in both directions) connecting the cities. Prove that there are four cities for which one of the airlines operates a round trip. (Note that a round trip of four cities P,Q,R, P,Q,R, and S S, is a journey that follows the path P→Q→R→S→P P \rightarrow Q \rightarrow R \rightarrow S \rightarrow P.)
Back to ProblemsView on AoPS