Matematik Olimpiyatı 2013, 2. Aşama, Soru 3

*n* hava yolu şirketinin ve 100 kentin bulunduğu bir ülkedeki kentlerden bazıları arasında karşılıklı olarak toplam 2013 uçak seferi yapılıyor. Bu seferleri kullanarak bu kentlerden herhangi birinden bir diğerine gitmek olanaklı olup, birinden diğerine doğrudan veya tek aktarma ile gidilemeyen en az iki kent bulunmaktadır. Bu ülkedeki herhangi iki kent arasında tek bir şirketin uçuşlarını kullanarak gitmek mümkünse, *n* nin alabileceği en büyük değeri belirleyiniz.

Şıklar:


Çözüm:
Cevap *n* = 1915. 


Soruyu çizge teorisi kavramlarını kullanarak yeniden formüle edelim: Köşe sayısı 100 ve kenar sayısı 2013 olan bağlantılı bir *G* çizgesinde birinden diğerine olan uzaklık en az üç olan en az iki köşe bulunuyor. Çizgenin kenarları *n* renge, herhangi bir köşeden herhangi başka bir köşeye aynı renge boyalı kenarlarla ulaşılabilecek şekilde boyanabiliyorsa, *n* en fazla kaç olabilir? 


İlk önce *n* = 1915 için bir örnek verelim. Çizgenin tüm köşelerini birleştiren bir ağacın tüm kenarlarını aynı renge ve kalan kenarların hepsini birbirinden farklı renklere boyanırsa sorudaki koşullar sağlanır ve toplam renk sayısı *n* = 2013 - 99 + 1 = 1915 olur. 


Şimdi renk sayısının daha fazla olamayacağını gösterelim. En çok renk bulunduruan bir boyama alalım. Bu boyamada 


1. Aynı renkli kenarlar bağlantılı bir ağaç oluşturuyorlar: Tek renkli bir döngü varsa, bu döngünün bir kenarı yeni bir renge boyanarak toplam renk sayısı artırılabilir. Birbiriyle bağlantılı olmayan aynı renkli iki ağaç varsa bu ağaçların biri yeni bir renge boyanarak toplam renk sayısı artırılbilir. 


2. İki ağacın ortak köşe sayısı en fazla iki olabilir: Ortak köşe sayısı ikiden fazla ise, bu ağaçların birleşimi en az iki döngü içerecektir. Bu durumda önce bu iki agacı ayna renge boyayıp, daha sonra her döngüde birbirinden farklı birer kenarı yeni bir renge boyayarak toplam renk sayısı artırılabilir. 


3. Genellüğü bozmadan iki ortak köşe paylaşan iki ağacın keşişim noktalarının bu ağaçların uç noktaları olduklarını varsayabiliriz. Aksi takdirde önce bu iki agacı ayna renge boyayıp, daha sönra bu iki ağacın birleşimindeki döngüdeki bir kenarı yeni bir renge boyayarak toplam renk sayısını değiştirmemiş oluruz. 


Şimdi aralarındaki uzaklık en az 3 olan herhangi *u* ve *v* köşelerini alalım. *u* ve *v* köşelerini birleştiren ve aynı renkli kenarlardan oluşan ağacın köşeler kümüseki *X*, *X* - {*u*, *v*} = *Y* olsun. *u* köşesinin komşu köşeleri *A*, *G* çizgesinin *u*, *v* ve *A* dışındaki köşeler kümüseki *B* olsun. *u* köşesi, *B* - *Y* deki her köşeyle aynı renkli kenarlardan oluşan bir ağaçla birleşmek zorundadır. Bu ağaçlar *T*<sub>1</sub>, ..., *T<sub>p</sub>* olsun. Bu ağaçlardan herhangi ikisi *u* noktasında kesişiyorlar. 3. özelliğe göre bu ağaçların herhangi ikisinin *u* dışında kesişme noktası bulunmuyor. Buna göre, *k* = 1, ..., *p* olmak üzere, her *T<sub>k</sub>* ile *A* nın bir köşesi birebir eşleştirilebilir. Sonuç olarak *T*<sub>1</sub>, ..., *T<sub>p</sub>* ağaçlarının birleşimi *u* dışında en az |*B*| - |*Y* ∩ *B*| + *p* tane köşe içeriyor. *v* köşesi, *A* - *Y* deki her köşeyle aynı renkli kenar lardan oluşan bir ağaçla birleşmek zorun dadır. Bu ağaçlar *S*<sub>1</sub>, ..., *S<sub>q</sub>* olsun. Benzer şekilde, bu ağaçların birleşimi *v* dışında en az |*A*| - |*Y* ∩ *A*| + *q* tane köşe içeriyor. Aynı renkli kenarlardan oluşan 1 + *d* köşeli bir ağaç *d* - 1 renk kaybına neden oluyor. Buna göre, toplam renk kaybı en az 


\[|B| - |Y \cap B| + p - p + |A| - |Y \cap A| + q - q + |Y| - 2\]


olacaktır. |Y ∩ B| + |Y ∩ A| = |Y| - 2 olduğuna göre, toplam renk kaybı en az |A| + |B| = 98 oluyor. Sonuç olarak renk sayısı en fazla 2013 - 98 = 1915 olabiliyor.