TR-MO 2008 Problem 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 \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, \ldots, B_m\}$ kümesine bir döngü diyoruz.]