Matematik Olimpiyatı 2017, 2. Aşama, Soru 6

Her biri 2017 br uzunluğunda olan sonlu sayıda çubuk bir levhanın üzerinde dikey olarak çakılı halde bulunuyor. Bu çubukların her birinin üzerinde serbestçe kaydırılabilen bir boncuk bulunuyor. Bazı boncuk ikilileri lastik parçalarıyla birbirlerine birleştirilmiştir. Bu düzenekte ayrıca, tüm lastik

parçaları üzerinde yürüyebilen bir adet Genç Karnca ve sadece uçlarındaki boncukların yükseklikleri arasında 1 br fark bulunan lastik parçaları üzerinde yürüyebilen bir adet Yaşlı Karnca bulunuyor. Genç Karnca lastikleri kullanarak her boncuktan her boncuğa ulaşabiliyor. 


Her boncuğun yerden yüksekliğinin tam sayı olduğu ve her lastik parçasının uçlarındaki boncukların farklı yüksekliklerde bulunduğu durumlara geçerli durum diyelim. Bu düzenekte en az bir geçerli durum varsa Yaşlı Karıncanın her boncuktan her boncuğa ulaşabildiği an az bir geçerli durumun olduğunu gösteriniz.

Şıklar:


Çözüm:
Soruyu çizge teorisi kavramlarını kullanarak yeniden formüle edelim: Bir çizgenin her bir köşesi 0, 1, ..., 2017 renklerinden birine, her kenarın uçlarındaki köşeler farklı renkte olacak şekilde boyanmış ise bu boyamaya düzgün boyama diyelim. Bir düzgün boyamada, *x* köşesinin rengi *f(x)* ile gösterilmek üzere, herhangi *a* ve *b* köşeleri için, her *i* = 1, ..., *n* - 1 için |*f*(*x*<sub>i</sub>) - *f*(*x*<sub>i+1</sub>)| = 1 olacak şekilde *a* = *x*<sub>1</sub>, *x*<sub>2</sub>, ..., *x*<sub>n</sub> = *b* yolu bulunuyorsa bu boyamaya *süper düzgün boyama* diyelim. Soruda bizden göstermemiz istenen şu soruya denktir: 


Bağlantılı bir *G* çizgesinin düzgün boyaması varsa, süper düzgün boyaması da vardır. 


*G* düzgün boyanmış bir çizge olsun. *G*'nin süper düzgün boyamaya sahip en büyük alt çizgesi *G*<sub>1</sub> olsun. Biz *G*<sub>1</sub> = *G* olduğunu göstereceğiz. Aksini varsayalım. Bir *H* çizgesinin köşeler kümesi *V(H)*, kenarlar kümesi *E(H)* ile gösterilsin. 


\[min_{(x,y) \in E(G), x \in V(G_1), y \in V(G-G_1)} (|f(x) - f(y)|) = |f(x_0) - f(y_0)|\]


olsun. Tanımlara göre |*f*(*x*<sub>0</sub>) - *f*(*y*<sub>0</sub>)| > 1'dir. İlk önce, *f*(*x*<sub>0</sub>) > *f*(*y*<sub>0</sub>) kabul edelim. *G* - *G*<sub>1</sub> çizgesinde *f*(*y*<sub>0</sub>) renkli köşeleri *f*(*x*<sub>0</sub>) - 1 rengine ve *f*(*x*<sub>0</sub>) - 1 renkli köşeleri *f*(*y*<sub>0</sub>) rengine boyayalım. Bu yeniden boyama işleminden sonra elde edilen boyamanın da düzgün olacağını gösterelim: *G* - *G*<sub>1</sub> alt çizgesinde *f*(*x*<sub>0</sub>) - 1 ve *f*(*y*<sub>0</sub>) renkleri yer değiştirmiştir ve sonuç olarak herhangi iki komşu köşe farklı renklerde olacaktır. Ayrıca, |*f*(*x*<sub>0</sub>) - *f*(* y*<sub>0</sub>)| ifadesinin minimum olmasından dolayı yeniden boyamadan sonra *f*(*x*) ≠ *f*(*y*) koşulu tüm *x* ∈ *G*<sub>1</sub> ve *y* ∈ *G* - *G*<sub>1</sub> köşeleri için sağlanacaktır. *f*(*x*<sub>0</sub>) < *f*(*y*<sub>0</sub>) simetrik durumunda da *G* - *G*<sub>1</sub> alt çizgesinde f*(*y*<sub>0</sub>) renkli köşeleri *F*(*x*<sub>0</sub>) + 1 rengine ve *f*(*x*<sub>0</sub>) + 1 renkli köşeleri *f*(*y*<sub>0*</sub>) rengine boyarsak benzer şekilde düzgün bir boyama elde edeceğiz. *G*<sub>1</sub> çizgesine *y*<sub>0</sub> köşesinin ve *y*<sub>0</sub> ile *G*<sub>1</sub> arasındaki tüm kenarların eklenmesiyle oluşan çizge *G*<sub>2</sub> olsun. Bu yeni boyama *G*<sub>2</sub> için bir süper düzgün boyamadır ve *G*<sub>2</sub> alt çizgesi *G*<sub>1</sub> alt çizgesini kapsamaktadır, çelişki. O halde *G*<sub>1</sub> = *G*'dir ve bu da *G*'nin bir süper düzgün boyamaya sahip olduğunu gösterir.