I have a qustion: Can a the hacker hack a computer twice? Another quesiton: Is the network a undirected graph or directed graph?

It is undirected. Actually, there was nothing about hacking or protecting a computer twice in the exam paper. Yet, I think it doesn't make sense. Because hacking a computer twice brings you nothing.

I'm going out of the town for more or less a week. When I come back I'll write the solution if nobody writes it.

Umut Varolgunes wrote: It is undirected. Actually, there was nothing about hacking or protecting a computer twice in the exam paper. Yet, I think it doesn't make sense. Because hacking a computer twice brings you nothing.

I'm going out of the town for more or less a week. When I come back I'll write the solution if nobody writes it. I think I have misread the problem. I thought it is "Cycles have no common edges". And I don't know why if my graph is accepable, it is still wrong(I haven't done problems for long time, and may be stupier now...). And I think my solution is still useful, for my premary condition is weaker.

sorry, it must be "acceptable". (Does accepable exist?) In your solution you are finding an edge instead of a vertice. I'm giving the extreme case and you can see that your idea doesn't work, because you must start with a specific vertice of a cycle, instead of considering a cycle only with its number of vertices. in this graph, hacker should hack one of the six vertices of hexagon and after, admin. protects the opposite vertice. The admin can guarantee to protect two of the three main vertices.

Could somebody post the full solution?

the answer is 1004 , isn´t it?

We claim that the answer is $\boxed{671}$. First, let's show that the hacker cannot do any better. Take a cycle of six vertices, say $v_1 v_2 v_3 v_4 v_5 v_6.$ Then, draw a path of $669$ vertices which starts at $v_1$, a path of $668$ vertices which starts at $v_3$, and a path of $668$ vertices which starts at $v_5.$ Draw these paths in a way so that they share no vertices amongst each other, and each share only one vertex with the cycle. In this case, it can be seen that the hacker's optimal result is getting $671$ computers. Notice that every computer must eventually be hacked or protected because of connectivity, and so a winning strategy for the hacker is equivalent to a strategy which restricts the administrator to at most $1337$ computers. Let's now show that the hacker can always get $671$ computers. Let's consider the obvious graph $G$ which corresponds to the network of computers. Consider now the graph $G'$ which results when we condense all cycles of $G$ into vertices. This is doable by the condition of the problem. For example, if $G$ is the example exhibited above, $G'$ becomes three paths of $668, 667, 667$ edges glued together at one vertex. Observe that $G'$ is acyclic and connected, and so therefore is a tree. For a subgraph of $G'$, define its size to be the number of vertices it has, after "un-condensing" all vertices of it which correspond to cycles of $G'$. For instance, in our example, $G'$ has size $2008$ and not $1 + 668 + 667 + 667 = 2003$. Call a vertex $v$ of $G'$ tasty if its removal leaves only connected components of $G'$ which have sizes $< 1338.$ We now consider two cases. Case 1. There does not exist a tasty vertex of $G'$. We will apply the following operation on every vertex $v$ of $G'.$ Since $v$ is not tasty, there exists a connected component of size at least $1338$ resulting from the removal of $v$. Let $w$ be the unique vertex of this connected component which is adjacent to $v.$ Then, draw an arrow from $v$ to $w.$ Because there are only $|G'| - 1$ edges of $G$ and $|G'|$ arrows drawn, by Pigeonhole there must be an edge $ab$ so that there is an edge from $a$ to $b$ and from $b$ to $a.$ Now, consider the effect of removing the edge $ab.$ From the definitions of these arrows, we know that the two resulting connected components must both have size at least $1338.$ However, it's clear that the sum of their sizes must be at most $2008$, and so this case is actually an absurdity. Case 2. There exists a tasty vertex of $G'$. Call this vertex $v.$ If this vertex corresponds to a vertex of $G$ (and not a cycle), then there is literally no way that the hacker can lose. Indeed, the administrator can only protect the computers in one connected component of $G$ resulting from the removal of $v$, and so this is at most $1337$ computers. Hence, the hacker can ensure at least $2008 - 1337 = 671$ hacked computers because the remainder of the graph is connected. Otherwise, suppose that $v$ corresponds to a cycle $v_1 v_2 \cdots v_k$ of $G.$ In the cases when $k = 2, 3, 4, 5,$ or $6$, it is easy to find a winning strategy for the hacker and so these cases are left as exercises to the reader. Henceforth, assume that $k > 6.$ We'll first exhibit a strategy for the hacker to hack at least half of the vertices of the cycle. Indeed, this is trivial, as the hacker simply keeps on hacking computers in the cycle arbitrarily as long as he/she can. Consider a set $S$ of contiguous vertices in the cycle. We will define the quality of $S$ as follows. Consider the subgraph of $G$ which results when we remove the vertices of the cycle and all edges involving any of these vertices. It is a collection of connected components, some of which were attached to vertices of $S$ in the original graph $G.$ Call these connected components branches of $S.$ The quality of $S$ is then the sum of the numbers of vertices of all its branches plus the number of vertices in $S.$ Notice that, in a sense, quality is additive. Let's now consider two subcases. Subcase 1. There exists a contiguous set of at least half of the vertices of the cycle with quality at most $670.$ WLOG let this contiguous set of vertices be $\{v_1, v_2, \cdots, v_a\}$ for some $a \ge \frac{k}{2}$. Then, it's clear that the quality of $\{v_{a+1}, v_{a+2}, \cdots, v_k\}$ is at least $1338.$ By "discrete continuity," there must exist some $a+1 \le b \le k$ so that the quality of $\{v_{a+1}, \cdots, v_b\}$ and the quality of $\{v_b, v_{b+1}, \cdots, v_{k}\}$ are each at least $669.$ The hackers strategy is now simple. Start by hacking $v_b.$ Now, it's clear that the hacker can ensure that either the entirety of the set $\{v_{a+1}, \cdots, v_b\}$ is hacked or the entirety of the set $\{v_b, v_{b+1}, \cdots, v_{k}\}$ is hacked. Indeed, simply start hacking clockwise around the cycle or start hacking counterclockwise around the cycle, depending on which computer the administrator first protectts. In either case, the hacker will have hacked a contiguous set of vertices of quality at least $669$ eventually. After the hacker ensures that he/she has hacked a contiguous set of at least $669$ vertices as described above, then the hacker will continue to hack vertices of the cycle arbitrarily. Afterwards, we consider two cases. If the administrator has protected a computer in the branches of the set of computers that the hacker has hacked, then the hacker wins because the administrator can protect at most one branch with at most $1337$ vertices (by the tastiness of $v$). Otherwise, the administrator proceeds to infect all of the branches of the set of computers he has hacked so far. This ensures that the hacker has hacked at least $669$ computers. We will now work on improving this bound. If one of the sets consists of at least half of the vertices of the cycle, then it's clear that the other set consists of only one vertex. The hacker alters his strategy as follows. Start by infecting this vertex, say $\alpha$. From here, the hacker will set out to infect at least half of the vertices of the cycle. The hacker will hack at least two more computers in the cycle, because $k \ge 7.$ Again, if the administrator protects any of the branches of $\{\alpha \}$, then he/she can again protect at most $1337$ computers, and the hacker wins. Otherwise, the hacker hacks all of the branches of $\{\alpha\}$. After this, the hacker will have hacked at least $669$ computers (quality of $\{\alpha\}$) plus the additional two computers, for at least $671$ computers. Otherwise, both sets consist of less than half of the vertices of the cycle. If both sets have at most $\left \lceil \frac{k}{2} \right \rceil - 2$ vertices, then the hacker can win with a similar strategy as in the above paragraph (infect an entire set and then get some more computers in the cycle). Otherwise, suppose that one of the sets has at least $\left \lceil \frac{k}{2} \right \rceil - 1$ vertices. This means that the other set has at most $2$ vertices. If it has one vertex, then the above argument works. Suppose it has $2$ vertices. There then exists a set of two vertices with quality at least $669$. Call these two computers the legends. Observe that if the hacker is able to hack both of the legends as his/her first two moves, then he/she wins. Indeed, he/she then simply focuses on infecting additional vertices of the cycle, and then we finish with the same "if the administrator protected a branch of the legends, he/she loses; otherwise, we just infect the branches of the legends" logic. Therefore, if the hacker takes one of the legends as his first move, the administrator must respond by protecting the other legend. This leads to the following solution. Split the cycle into two contiguous sets of vertices differing in size by at most $1$ so that the legends are in different set. The hacker then hacks the legend which in the set of quality at least $1004$, call this set $\Gamma$. After the hacker protects the other legend, it's clear that the hacker can go on to infect all of the other vertices in $\Gamma$, and from there can infect all of the branches of $\Gamma.$ As the quality of $\Gamma$ is at least $1004$, the hacker will have infected at least $1004 \ge 671$ computers, and so he/she wins. Subcase 2. There does not exist such a set. Then, the hacker simply keeps on picking vertices of the cycle arbitrarily until he/she cannot. At this point, the hacker will have infected a set of at least half of the computers of the cycle with quality at least $671$, by the assumption of this case. If the administrator ever protected any computer among the branches of this set of vertices, then since $v$ is tasty he/she will have protected at most $1337$ computers and the hacker can therefore win by infecting all other computers. Otherwise, the hacker can infect all branches of this set as well, for at least $671$ computers. As we've exhausted all cases, we've shown that the hacker can always infect $\ge 671$ computers, and so we're done. $\square$