(Sinan KARAL)
İddiamız en fazla $\dbinom{n+1}{2}$ sefer olabileceğidir.
Kentlerimiz $V_1,V_2, \cdots V_n$ ve başkentimiz de $V$ olsun.
$V_i$ şehrinden başkente giden seferlerin sayısı $b_i$, $V_i$'nin başkent dışında seferi olduğu şehirlerin sayısı $r_i$ olsun.$V$ den çıkan yolların sayısı $y,$ $(V_1, \cdots , V_n)$ arasındaki yolların sayısı $x$ olsun.
Tüm $(V_i,V_j)_{(i\neq j)}$ ikilileri üzerinden seferleri sayalım.Bir $V_i$ ve $V_j$ ikilisi aldığımızda, bu ikisinden çıkan seferlerin toplam sayısı (bir seferi iki kez de sayabiliriz, farketmez.)
$d_{V_i}+d_{V_j}=b_i+b_j+(d_{V_i}-b_i)+(d_{V_j}-b_j)$ dir. Yani bu saymada $\displaystyle \sum_{i\neq j}(d_{V_i}+d_{V_j})$
toplamında $V$ den çıkan her sefer (mesela $V$ ile $V_1$ arasında bir yol) $d_{V_1}$ bu toplamda kaç kez geçmişse o kadar kez, yani $2n-2$ kez sayılır.Bir $V_i$ ve $V_j$ yi bağlayan sefer ise $d_{V_i}$ ve $d_{V_j}$ kaç kez geçmişse o kadar yani $2(2n-2)=4n-4$ kez sayılır.
Dolayısıyla $\displaystyle \sum_{i\neq j}(d_{V_i}+d_{V_j})=(2n-2)Y+(4n-4)X$ bulunur.... $(1)$
Diğer taraftan, $\displaystyle \sum_{i\neq j}(d_{V_i}+d_{V_j})=\displaystyle \sum_{i=1}^n \displaystyle \sum_{i\neq j}(d_{V_j}+d_{V_i})$ sağlanır.Yani $V_i$ şehrini sabit tutarak toplamı inceleyelim :
$V_i$'den sefer olan şehirler $V_{k_1},V_{k_2},\cdots , V_{k_{r_i}}$ olsun. Dolayısıyla bir $j\neq k_{\ell}$ için $V_i+V_j \leq n$ yazabiliriz :
$\displaystyle \sum_{i=1}^n \displaystyle \sum_{i\neq j}(d_{V_j}+d_{V_i})=\displaystyle \sum_{i=1}^n \left [\displaystyle \sum_{j\neq i,k_1,k_2, \cdots ,k_{r_i}}(d_{V_i}+d_{V_j})+\displaystyle \sum_{j\in k_1,k_2, \cdots ,k_{r_i}}(d_{V_i}+d_{V_j})\right]$
$\leq \displaystyle \sum_{i=1}^n \left [\displaystyle \sum_{j\neq i,k_1,k_2, \cdots ,k_{r_i}}n+\displaystyle \sum_{j\in k_1,k_2, \cdots ,k_{r_i}}(n+n)\right]$
$=\displaystyle \sum_{i=1}^n \left[n(n-r_i-1)+2n.r_i\right] = \displaystyle \sum_{i=1}^n (n^2-n+nr_i)=n^3-n^2+n(r_1+ \cdots +r_n)$
$r_1+ \cdots +r_n \leq 2X$ sağlanır, çünkü $r_1+ \cdots +r_n$ toplamı $V_1, \cdots ,V_n$ arasındaki toplam sefer sayısından küçük eşittir.($V_i$ şehrinden diğer şehirlere en az $r_i$ sefer vardır.)
$\implies$ $(1)$'i de kullanarak : $(2n-2)Y+(4n-4)X \leq n^3-n^2+2X.n$
$\implies$ $(2n-2)(x+y) \leq [2X-(n^2-n)]+[n^3-n]$
$\implies$ $x+y \leq \left[ \dfrac{2X-n^2+n}{2n-2} \right] + \dbinom{n+1}{2}$ bulunur.
$x+y \leq \dbinom{n+1}{2}$ olduğunu ispatlamak istiyoruz. $2X \leq n^2-n$ ise sorun yok. $2X > n^2-n$ olsun. Dolayısıyla her $V_a$ ile $V_b$ arasında en az 1 sefer olmalı, aksi takdirde $d_{V_A}+d_{V_b} \leq n$ olur ve $\displaystyle \sum_{i\neq a,b} d_{V_i} \leq n$ olduğundan : $2X \leq \displaystyle \sum_{i=1}^n d_{V_i} \leq n+(n-2)n = n^2-n$ olur, çelişki.
Yani her $V_a$ ve $V_b$ arasında sefer var. Bu durumda her $V_i$ şehrinden en az $n-1$ sefer başkent dışındaki şehirlere olacağından, $V_i$ şehrinin mümkün $n.$ seferi ya başkente ya da başka bir şehredir.Yani $Y\leq n$ olur ve tam $n-Y$ şehrin başkent dışındaki şehirlere en fazla $n$ seferi olur.
$\implies$ $2X \leq (n-Y)+(n^2-n)$, $x+y \leq \frac{n^2-n}{2}+ \frac{n+Y}{2} \leq \frac{n^2-n}{2}+n = \binom{n+1}{2}$
Demek ki bu durumda zaten $x+y \leq \binom{n+1}{2}$.
Sonuç olarak, $x+y \leq \dbinom{n+1}{2}$ bulunur ve eşitlik durumunun sağlanması için :
$i)$ $2X \leq n^2-n$ iken, $i=1, \cdots ,n$ için $r_i=d_{V_i}-b_i$ olacak, yani her $V_i$ şehrinden başka şehirlere en fazla 1 sefer olacak. Ayrıca $X= \dbinom{n}{2}$ olacak, yani başkent dışında her şehir arasında tam 1 sefer var. $Y=n$ olacağından, başkentten de diğer her şehre tam 1 sefer var. Yani ülkedeki her şehir arasında o gün içinde karşılıklı tam 1 sefer var, bu durumda şartların sağlandığı açıktır.
$ii)$ $2X > n^2-n$ iken, eşitlik durumu için $Y=n$ olmalı,
yani $X= \dbinom{n+1}{2}-Y= \dfrac{n^2-n}{2}$, çelişiki!
Demek ki bu durumda eşitlik olamaz.
İspat biter.
