TR-MO 2005 Problem 3

$n+1$ kentin bulunduğu bir ülkede, bu kentlerden bazıları arasında karşılıklı uçak seferleri yapılmaktadır. $A$ ve $B$ kentleri arasında yapılan bir karşılıklı sefer, aynı gün içinde hem $A$ dan $B$ ye, hem de $B$ den $A$ ya yapılan bir uçuş ikilisi anlamına gelip, bir kentten diğerine karşılığı olmayan tek yönlü bir sefer mevcut değildir. İki kent arasında aynı gün içinde birden çok sayıda karşılıklı sefer yapılabilmektedir. $A$ kenti için, bir günde $A$ dan kalkan uçak sayısını $d_A$ ile gösteriyoruz. Başkent dışındaki tüm $A$ kentleri için $d_A \leq n$ ve yine başkent dışındaki ve aralarında karşılıklı uçak seferi bulunmayan farklı herhangi iki $A, B$ kenti için, $d_A + d_B \leq n$ koşulları sağlanmaktadır. $n+1$ kent arasında yer alan başkentten bir gün içinde yapılan uçak seferlerinin sayısı konusunda ise, herhangi bir kısıtlama yoktur.

Bu ülkede bir günde en çok kaç karşılıklı uçak seferi yapılabileceğini ve bu en çok karşılıklı sefer sayısını olanaklı kılan tüm uçuş çizelgelerini belirleyiniz.