Geomania.Org Forumları

Yarışma Soruları => Tübitak Lise 2. Aşama => 2008 => Konuyu başlatan: geo - Ağustos 06, 2013, 03:42:23 öö

Başlık: Tübitak Lise 2. Aşama 2008 Soru 6
Gönderen: geo - Ağustos 06, 2013, 03:42:23 öö

$2008$ tane bilgisayardan oluşan bir bilgisayar ağında, herhangi iki döngü kesişmiyor. $t=0$ anında, bir bilgisayar korsanı bu ağdaki bir bilgisayarı ele geçiriyor ve $t=1$ anında da, ağ yönetici, ele geçirilmemiş bir bilgisayara koruyucu bir program yüklüyor. Her $k$ pozitif tam sayısı için, $t=2k$ anında, korsan, varsa, o ana kadar ele geçirdiği bilgisayarlardan birine doğrudan bağlı olan ve koruyucu program yüklenmemiş olan bir bilgisayarı daha ele geçirebiliyor; $ t=2k+1$ anında da, ağ yöneticisi, varsa, o ana kadar koruyucu program yüklenmiş bilgisayarlardan birine doğrudan bağlı olan ve korsanın ele geçirmemiş olduğu bir bilgisayara daha koruyucu programı yükleyebiliyor. Bilgisayar ağı ne şekilde düzenlenmiş olursa olsun, korsanın en çok kaç tane bilgisayarı ele geçirmeyi garantileyebileceğini belirleyiniz.

[ $m \geq 3$ olmak üzere, $B_1$ ve $B_m$ bilgisayarları ve, her $2\leq i \leq m$ için, $B_{i-1}$ ve $B_i$ bilgisayarları doğrudan bağlıysa, $m$ elemanlı $\{B_1, B_2, \dots, B_m\}$ kümesine bir döngü diyoruz.]

(Azer Kerimov)

Başlık: Ynt: 6 - Tashih edildi
Gönderen: geo - Ağustos 17, 2013, 11:33:57 ös

(Mehmet KAYSİ)

Soruyu çizge sorusuna çevirip öyle çözelim. Çözümde bilgisayarları çizgenin köşeleri (noktaları), iki bilgisayar arasındaki ağ\i, çizgenin kenarları olarak; korsanı 1. oyuncu, ağ yöneticisini 2. oyuncu olarak; hamleleri ise noktaları ele geçirme olarak düşüneceğiz.

1. Durum: Çizgede hiç döngü yoksa

iddia 1: 1. oyuncu noktaların en az yarısını ele geçirir.

ispat: 1. oyuncu ilk hamlesi için rastgele bir nokta seçsin. Bu noktayı sildiğimizde, çizgede döngü olmadığı için çizge birbirinden kopuk alt çizgelere ayrılır. 2. oyuncu bu alt çizgelerden en fazla birini ele geçirebilir.
Eğer alt çizgelerden en büyük olan noktaların yarısından fazla sayıda nokta içermiyorsa, 1. oyuncu diğer alt çizgeleri alacağından noktaların en az yarısını ele geçirmeyi garantiler.
Eğer alt çizgelerden en büyüğü noktaların yarısından fazla nokta içeriyorsa, 1. oyuncunun ilk hamlesini değiştiriyoruz. Daha önce seçilen nokta yerine, bu nokta ile komşu olan ve en büyük alt çizgeye ait olan noktayı seçiyoruz. 2. oyuncu bir önceki durumda seçtiği alt çizgenin noktalarından birini seçmiyorsa, 1. oyuncu bir önceki durumda 2. oyuncunun ele geçirdiği noktaları ele ge\c irir ki bu noktaların sayısı da tüm noktaların sayısının yarısından az değildir. Aksi takdirde 1. oyuncunun ele geçirdiği noktaların sayısı en az 1 artar. 1. oyuncu ele geçireceği noktaların sayısı tüm noktaların en az yarısı olacak şekilde ilk hamlesini gözden geçirerek, amacına ulaşır.

2. Durum: Çizgede döngü varsa,

Bu durumu da üçe ayıracağız. Burada bir tanım vermemiz gerekiyor. Döngüdeki bir noktadan, döngüdeki noktaları kullanmadan gidilebilen noktardan oluşan ve kenarları verilen çizgenin kenarları olan alt çizgeye, o noktadan çıkan kol diyeceğiz. İspatın kalanını okurken çizgede kesişen 2 döngünün bulunmadığını unutmayalım.
1. oyuncunun noktaların üçte birini almayı garantileyeceğini gösterelim.

• Tüm döngülerin her bir kolu, tüm noktaların üçte birinden az sayıda nokta içeriyorsa
  
  1. oyuncu ilk hamlesini kesinlikle bu döngü üzerinde yapmalıdır. Aksi takdirde 2. oyuncu, 1. oyuncunun hamle yaptığı kol ile döngünün bağlantısını keserek, 1. oyuncunun hedeflenenden az sayıda nokta almasını sağlayabilir. Aslında bu durumda herhangi bir kolun döngüye bağkandığı noktayı ele geçiren oyuncu, o kolu tümden ele geçirmiş olur. Dolayısıyla her iki oyuncu da mümkün olduğunca çok nokta ele geçirmek istiyorsa, döngü üzerinde nokta kalmayana kadar hamlelerini döngü üzerinde yapmak zorundadırlar.
  Döngüdeki noktaları bir çember üzerine, noktalar arasında eşit uzaklıkta olacak şekilde dizdiğimizi düşünürsek, oyuncular birer yarım çember ele geçirecekler. 1. oyuncu hamlesini çember üzerinde bir noktaya yapsın, bu noktaya $A$ noktası diyelim.
  
  iddia 2: 2. oyuncu $A$ noktasını içermeyen istediği yarım çemberi ele geçirebilir.
  
  ispat: 2. oyuncu ele geçirmek istediği yarım çemberle diğer yarım çember arasına bir çizgi çizer. Sonra 2. oyuncu, 1. oyuncunun ele geçirdiği  noktanın bu doğruya göre simetriğindeki noktayı ele geçirir.
  
  
  (http://geomania.org/forum/2008-34/6-3120/?action=dlattach;attach=13245;image)
  
  Burada 2. oyuncu $A$ ya karşılık $B$ yi, $D$ ye karşılık $E$ yi, $J$ ye karşılık $H$ yi ele geçirir.
  
  Bu durumda şunu ispatlamamız gerekiyor:
  iddia 3: 1. oyuncu ilk hamlesinde öyle bir nokta ele geçirebilir ki, o noktayı içeren tüm yarım çemberler kollarıyla beraber en az istenilen sayıda nokta içerir.
  
  ispat: Diyelim ki her nokta için o noktayı içeren en az bir adet yeterli miktarda nokta içermeyen bir yarım çember bulunsun. İlk olarak herhangi bir nokta alalım ve bu noktayı içeren ve yeterli miktarda nokta içermeyen bir yarım çember alalım. Daha sonra bu yarım çemberin uç noktalarından birini alalım, bu noktayı içeren en az bir yarım çember vardır, bu yarım çemberler içinde ilk yarım çemberimiz ile kesişimi en az olan yarım çemberi seçelim. İlk yarım çember ile ikinci yarım çember aynı yarım çemberler değilse, bu ikinci yarım çemberin ilk yarım çember üzerinde olmayan uç noktasını alalım ve aynı şekilde 3. yarım çemberi seçelim. Bu yarım çemberleri seçme şeklimizden dolayı(kesişimin en az olması)  üçünün kesişimi boş kümedir. Ve bu da bu yarım çemberlerin çemberi çevrelemesini gerektirir. Yarım çemberlerin özelliği içerdiği noktaların sayısıyının toplam nokta sayısının 1/3 ünden daha az miktarda olmasıydı. Dolayısıyla elimizdeki 3 yarım çemberin içerdiği noktaların sayısının bütün noktaların sayısından küçük olması gerekir, fakat bu üç yarım çemberimiz bütün çemberi içeriyordu dolayısıyla kesinlikle bütün noktaların sayısından fazladır. Demek ki her nokta için uygun bir yarım çember bulunamaz ve en az bir nokta için o noktayı içeren bütün yarım çemberler yeterli sayıda nokta içerir. 
  Son olarak, atladığımız ilk yarım çember ile 2. yarım çemberin kesişmesi durumuna bakalım. Bu durumda ilk çemberin uç noktasını içeren ve tüm noktaların 1/3'ünden az sayıda nokta içeren tek yarım çember var demektir. Bu uç noktanın ilk yarım çember üzerinde olmayan komşusunu alalım. Kabulümüz gereği, bu noktayı içeren ve içerdiği noktaların sayısı 1/3'ten az olan bir yarım çember olmak zorundadır. Fakat bu yarım çember ilk çemberin seçtiğimiz uç noktasını içemez. Dolayıyla bu yarım çember ile ilk yarım çemberin bileşimi bize çemberin tamamını verir. Fakat bu iki yarım çemberdeki noktaların sayısı tüm noktaların 2/3' ü kadardı, çelişki. Demek ki her nokta için uygun bir yarım çember bulunamaz ve en az bir nokta için o noktayı içeren bütün yarım çemberler yeterli sayıda nokta içerir.
  
• Bir kolu tüm noktaların üçte birinden fazla fakat üçte ikisinden az sayıda nokta içeren bir döngü varsa
  
  1. oyuncu bu kolun döngüye bağlandığı noktayı seçer. Bu durumda 1. oyuncu, 2. oyuncunun hamlesine göre ya kolu, ya da kol hariç çizgenin kalanını ele geçirir. Her iki durumda tüm noktaların en az üçte birini ele geçirmiş olur.
  
• Tüm döngülerde, tüm noktaların üçte ikisinden fazla sayıda nokta içeren bir kol varsa
  
  1. oyuncu ilk hamlesini bu döngü üzerinde yaparsa, 2. oyuncu kol üzerindeki döngüye en yakın noktayı seçerek, 1. oyuncunun döngü ile olan bağlantısını keser ve 1. oyuncunun hedeflenenden az sayıda nokta almasını sağlar. Bu yüzden 1. oyuncu ilk hamlesini döngü üzerinde yapmamalıdır. Bu durum 1. duruma çok benzer hale geldi. Yine 1. oyuncunu yapacaği hamle çizgeyi, birbirinden kopuk alt çizgelere ayırır.
  
  Önce döngüdeki noktaları kırmızı renk ile işaretleyelim. Her döngüden birer kenar çıkararak, çizgeyi döngüsüz hale getirelim. 1. Durumdaki adımları takip edip 1. oyuncunun ilk hamlesini yapacağı noktayı belirleyelim. Bu nokta kırmızı noktalardan biri değildir, aksi takdirde tüm noktaların en az üçte ikisini içeren bir alt çizge bulunur. Sonra sildiğimiz kenarları tekrar çizelim. 1. durumdaki gibi 1. oyuncu tüm noktaların en az yarısını ele geçirmeyi garantiler.
  
  Buraya kadar olan kısımda, 1. oyuncunun  noktalardan en az 1/3'ünü ele geçirebileceğini gösterdik. Şimdi 1. oyuncunun noktalardan 1/3'ünden fazla sayıda nokta ele geçiremeyeceği bir örnek vererek çözümü tamamlayacağız.
  
  
  (http://geomania.org/forum/2008-34/6-3120/?action=dlattach;attach=13247;image)
  
  Çözümde, 1. oyuncu hamlesini yaptıktan sonra 2. oyuncunun istediği yarım çemberi alabildiğini  göstermiştik. Bu çizgede 1. oyuncu nasıl oynarsa oynasın, 2. oyuncu 2 kol almayı garantiler.