MathDB
Combinatorics

Source: 0

April 21, 2009
pigeonhole principle

Problem Statement

Flights are arranged between 13 countries. For k≥2 k\ge 2, the sequence A1,A2,…Ak A_{1} ,A_{2} ,\ldots A_{k} is said to a cycle if there exist a flight from A1 A_{1} to A2 A_{2}, from A2 A_{2} to A3 A_{3}, … \ldots, from A_{k \minus{} 1} to Ak A_{k}, and from Ak A_{k} to A1 A_{1}. What is the smallest possible number of flights such that how the flights are arranged, there exist a cycle?
<spanclass=′latex−bold′>(A)</span> 14<spanclass=′latex−bold′>(B)</span> 53<spanclass=′latex−bold′>(C)</span> 66<spanclass=′latex−bold′>(D)</span> 79<spanclass=′latex−bold′>(E)</span> 156<span class='latex-bold'>(A)</span>\ 14 \qquad<span class='latex-bold'>(B)</span>\ 53 \qquad<span class='latex-bold'>(C)</span>\ 66 \qquad<span class='latex-bold'>(D)</span>\ 79 \qquad<span class='latex-bold'>(E)</span>\ 156
Back to ProblemsView on AoPS