Câu hỏi 107
Trong một mạng máy tính gồm $2008$ máy tính, không có hai chu trình nào giao nhau. Tại thời điểm $t = 0$, một hacker xâm nhập vào một máy tính của mạng; và tại thời điểm $t = 1$, quản trị viên mạng cài phần mềm bảo vệ cho một máy tính chưa bị xâm nhập. Với mỗi số nguyên dương $k$, tại thời điểm $t = 2k$, hacker xâm nhập vào một máy tính khác, nếu còn, chưa được bảo vệ và được nối trực tiếp với một máy tính đã bị xâm nhập; và tại thời điểm $t = 2k + 1$, quản trị viên cài phần mềm bảo vệ cho một máy tính khác, nếu còn, chưa bị xâm nhập và được nối trực tiếp với một máy tính đã được bảo vệ. Hãy xác định số máy tính lớn nhất mà hacker có thể đảm bảo xâm nhập được, bất kể mạng được cấu hình như thế nào.
[Với $m \ge 3$, $\{C_1, C_2, \dots, C_m\}$ là một chu trình nếu các máy tính $C_1$ và $C_m$, cũng như các máy tính $C_{i-1}$ và $C_i$ với mọi $2 \le i \le m$, được nối trực tiếp với nhau.]
[Với $m \ge 3$, $\{C_1, C_2, \dots, C_m\}$ là một chu trình nếu các máy tính $C_1$ và $C_m$, cũng như các máy tính $C_{i-1}$ và $C_i$ với mọi $2 \le i \le m$, được nối trực tiếp với nhau.]