Gönderen Konu: Tübitak Lise 2. Aşama 2017 Soru 6  (Okunma sayısı 3252 defa)

Çevrimdışı Eray

  • G.O Genel Moderator
  • G.O Efsane Üye
  • ********
  • İleti: 414
  • Karma: +8/-0
Tübitak Lise 2. Aşama 2017 Soru 6
« : Şubat 08, 2018, 10:01:09 ös »
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ç Karınca 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ı Karınca bulunuyor. Genç Karınca 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 en az bir geçerli durum olduğunu gösteriniz.

(Azer Kerimov)
« Son Düzenleme: Temmuz 06, 2024, 01:38:59 ös Gönderen: Lokman Gökçe »

Çevrimdışı geo

  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 2.633
  • Karma: +9/-0
Ynt: Tübitak Lise 2. Aşama 2017 Soru 6
« Yanıtla #1 : Temmuz 06, 2024, 08:53:28 öö »
Soruyu çizge teorisi kavramların kullanarak yeniden formüle edelim: Bir çizgenin her bir köşesi $0,1, \ldots, 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, \ldots, n-1$ için $\left|f\left(x_i\right)-f\left(x_{i+1}\right)\right|=1$ olacak şekilde $a=x_1, x_2, \ldots, x_n=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_1$ olsun. Biz $G_1=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\left(G_1\right), y \in V\left(G-G_1\right)}(|f(x)-f(y)|)=\left|f\left(x_0\right)-f\left(y_0\right)\right|
$$
olsun. Tanımlara göre $\left|f\left(x_0\right)-f\left(y_0\right)\right|>1$ 'dir. Ilk önce, $f\left(x_0\right)>f\left(y_0\right)$ kabul edelim. $G-G_1$ çizgesinde $f\left(y_0\right)$ renkli köşeleri $f\left(x_0\right)-1$ rengine ve $f\left(x_0\right)-1$ renkli köşeleri $f\left(y_0\right)$ rengine boyayalım. Bu yeniden boyama işleminden sonra elde edilen boyamanın da düzgün olacağını gösterelim: $G-G_1$ alt çizgesinde $f\left(x_0\right)-1$ ve $f\left(y_0\right)$ renkleri yer değiştirmiştir ve sonuç olarak herhangi iki komşu köşe farklı renklerde olacaktır. Ayrıca, $\left|f\left(x_0\right)-f\left(y_0\right)\right|$ ifadesinin minimum olmasından dolayı yeniden boyamadan sonra $f(x) \neq f(y)$ koşulu tüm $x \in G_1$ ve $y \in G-G_1$ köşeleri için sağlanacaktır. $f\left(x_0\right)<f\left(y_0\right)$ simetrik durumunda da $G-G_1$ alt çizgesinde $f\left(y_0\right)$ renkli köşeleri $f\left(x_0\right)+1$ rengine ve $f\left(x_0\right)+1$ renkli köşeleri $f\left(y_0\right)$ rengine boyarsak benzer şekilde düzgün bir boyama elde edeceğiz. $G_1$ çizgesine $y_0$ köşesinin ve $y_0$ ile $G_1$ arasındaki tüm kenarların eklenmesiyle oluşan çizge $G_2$ olsun. Bu yeni boyama $G_2$ için bir süper düzgün boyamadır ve $G_2$ alt çizgesi $G_1$ alt çizgesini kapsamaktadır, çelişki. O halde $G_1=G^{\prime}$ dir ve bu da $G$ 'nin bir süper düzgün boyamaya sahip olduğunu gösterir.

Kaynak: Tübitak Çözüm Kitapçığı
« Son Düzenleme: Temmuz 06, 2024, 09:02:37 öö Gönderen: geo »

 


Sitemap 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 
SimplePortal 2.3.3 © 2008-2010, SimplePortal