Tübitak Lise 1. Aşama 1999 Soru 35

[geo]

$13$ kent arasında, karşılıklı olması gerekmeyen uçak seferleri yapılıyor. $k \geq 2$ olmak üzere, $A_1$ den $A_2$ ye, $A_2$ den $A_3$ e, $\dots$, $A_{k-1}$ den $A_k$ ye ve $A_k$ den $A_1$ e uçak seferi varsa, $A_1, A_2, \dots , A_k$ dizisine bir çevrim diyelim. Seferler hangi kentler arasında olursa olsun, bir çevrimin oluşmasını gerektiren en küçük toplam sefer sayısı kaçtır?

$
\textbf{a)}\ 14
\qquad\textbf{b)}\ 53
\qquad\textbf{c)}\ 66
\qquad\textbf{d)}\ 79
\qquad\textbf{e)}\ 156
$

[geo]

$A_1A_2\dots A_{13}$ bir $13$-gen olsun. Köşegenleri ve kenarları çizelim. Bu yollara  $i<j$ ise $A_i \rightarrow A_j$ olacak şekilde yön verelim. Bu durumda ${13 \choose 2} = 78$ yol vardır. Bu stratejiye göre, bir çevrimin olabilmesi için $1 < 2 < \dots < k < 1 $ gerekir. Bu mümkün değil. Demek ki, bu $78$ yol hiçbir şekilde bir çevrim oluşturmuyor. Bu sayı aynı zamanda $1\leq i < j \leq 13$ olacak şekilde yazılabilecek $(i, j)$ sıralı çiftlerin sayısıdır. $79$. çifti ele aldığımızda mecburen $i>j$ olacaktır.