Tübitak Genç Takım Seçme 2015 Soru 3

[Eray]

Bir ülkedeki $2015$ kentten herhangi ikisi arasında tam olarak bir karşılıklı uçak seferi yapılmaktadır. Herhangi üç kent arasındaki direkt seferler üç farklı havayolu şirketi tarafından yapılıyorsa, bu ülkede en az kaç havayolu şirketi olabilir?

(Azer Kerimov)

[MATSEVER 27]

Cevap: $2015$. Bibirinden ayrık kent ikilisi sayısı $1007$ olduğundan her havayolu şirketi en fazla $1007$ karşılıklı uçak seferi yapabilir. Toplam karşılıklı sefer sayısı $\binom{2015}{2}$ olduğundan en az $\frac{2015 · 2014}{2 · 1007}= 2015$ tane havayolu şirketi gerekmektedir. $2015$ havayolu şirketi için örnek:

Kentler $1, 2, . . . , 2015$ olmak üzere, $i$ ve $j$ kentlerini arasındaki seferler $(i + j)$ $\pmod{2015}$ numaralı havayolu şirketi tarafından yapılıyor.