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

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öneticisi, 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 \ge 3 \text{ olmak üzere, } B_1 \text{ ve } B_m \text{ bilgisayarları ve, her } 2 \le i \le m \text{ için, } B_{i-1} \text{ ve } B_i \text{ bilgisayarları doğrudan bağlıysa, } m \text{ elemanlı } \{B_1, B_2, \dots, B_m\} \text{ kümesine bir döngü diyoruz.}]\]

Şıklar:

Cevap:  671

Çözüm:
Cevap: 671. 


İlk önce korsanın en fazla 671 bilgisayarı ele geçirmeyi garantileyebileceği bir örnek verelim. \(\{B_1, B_2, B_3, B_4, B_5, B_6\}\) bilgisayarları bir döngü üzerinde bulunsunlar: \(B_1\) ve \(B_2\), \(B_2\) ve \(B_3, \dots, B_5\) ve \(B_6\) ve son olarak \(B_6\) ve \(B_1\) bilgisayarları arasında doğrudan bağ olsun. \(i = 1, 2, \dots, n-1\) olmak üzere, \(T_i\) ve \(T_{i+1}\) bilgisayarları arasında birer doğrudan bağ varsa, \(\{T_1, T_2, \dots, T_n\}\) bilgisayar grubuna ilk elemanı \(T_1\) olan \(n\) elemanlı bir bilgisayar zinciri diyelim. 668 elemanlı birinci bilgisayar zincirinin ilk elemanı doğrudan \(B_1\) bilgisayarına, 667 elemanlı ikinci bilgisayar zincirinin ilk elemanı doğrudan \(B_{3}\) bilgisayarına, 667 elemanlı üçüncü bilgisayar zincirinin ilk elemanı da doğrudan \(B_5\) bilgisayarına

bağlı olsun. Bu durumda korsanın ilk olarak ele geçirdiği bilgisayar herhnagi bir zincirin elemanıysa, yönetici aynı zincirin döngüye direkt bağlı bilgisayarına koruyucu yükleyerek korsanın en fazla 668 bilgisayarı ele geçirmesini sağlar. Simetriden dolayı sadece korsanın ele geçirdiği bilgisayarın  \( B_1 \)  ve  \( B_2 \)  olduğu durumları inceleyeceğiz. Başlangıçta korsan  \( B_1 \)  bilgisayarını ele geçirirse yönetici koruyucu programı  \( B_4 \)  e yükler. Bu durumda korsan sadece  \( B_6, B_1, B_2 \)  ve  \( B_1 \)  e bağlı birinci bilgisayar zincirindeki bilgisayarları, dolayısıyla 671 bilgisayarı ele geçirmeyi garantileyebilir. Benzer şekilde başlangıçta korsan  \( B_2 \)  bilgisayarını ele geçirirse yönetici koruyucun programı  \( B_1 \)  bilgisayarına yükler ve korsan sadece  \( B_1, B_3, B_4 \)  ve  \( B_2 \)  ye bağlı ikinci bilgisayar zincirindeki bilgisayarları, dolayısıyl 670 bilgisayarı ele geçirmeyi garantileyebilir. 


Şimdi bilgisayar ağı ne şekilde düzenlenmiş olursa olsun, korsanın en az 671 bilgisayarı ele geçirmeyi garantileyebileceğini göstereceğiz. 


Durum 1: Bilgisayar ağında herhangi bir döngü üzerinde bulunmayan öyle bir B bilgisayarı bulunuyor ki, B bilgisayarı ağdan alındığı takdirde birbirleriyle bağlantılı (doğrudan veya başka bilgisayarlar aracılığıyla) bilgisayardan oluşan her bilgisayar grubunda en fazla 1337 bilgisayar olsun. Bu durumda korsan ilk olarak B bilgisayarını ele geçirirse en az 2008–1337 = 671 bilgisayarı ele geçirmeyi garantiler. 


Durum 2: Bilgisayar ağında öyle bir Z = {B1, B2, . . ., Bm} ağı bulunuyor ki, bu döngü ağdan alındığı takdirde birbirleriyle bağlantılı (doğrudan veya başka bilgisayarlar aracılığyla) bilgisayardan oluşan her bilgisayar grubunda e fazla 1337 bilgisayar olsun. Her 1 ≤ i ≤ m indisi için, korsan ilk olarak B i bilgisayarını ele geçirdiği ve korsan ve yöneticinin en iyi stratejilerini uyguladıkları durumda korsanın Z döngüsünde ve tüm ağda ele geçreceği bilgisayarlar kümeleri sırasıyla Hi ve Gi olsun. |Hi| = ⌈m/2⌉ olduğu açıktır. i ve j indislerini |Hi ∪ Hj| sayısı en büyük olacak şekilde seçelim. Z = Hi ∪ Hj ise, |Gi| + |Gj| ≥ 2008 ve dolayısıyla Gi ve Gj kümelerinin en az biri en az 1004 eleman içermiş olur. Diğer durumda Bk ∈ Z(Hi ∪ Hj) alırsak Hi ∪ Hj ∪ Hk = Z olur. O zaman |Gi| + |Gj| + |Gk| ≥ 2008 + 3, ve dolayısıyla Gi, Gj, Gk kümérinin en az biri en az ⌈2011/3⌉ = 671 eleman içermiş olur. 


Sonuç olarak korsan her iki durumda da en az 671 bilgisayarı ele geçirmeyi garantilemiş olur. 


Son olarak bilgisayar ağı ne şekilde düzenlenmiş olursa oluşan, Durum 1 ve Durum 2 den en az birinin her zaman geçerli olduğunu gösterelim. Aksi takdirde her işlemde seçilecek B bilgisayarını 1337 den fazla bilgisayar içeren bağlantılı gruba doğru bir bilgisayar kaydıralım. Birkaç işlem sonucunda hareket yönünü değiştirmek zorunda kalacağız. Bu noktada her iki yöne doğru en az 1337 bilgisayar bulunmak zorundadır ve bu da bir çelişkidir.