Browse · MathNet
Print16th Turkish Mathematical Olympiad
Turkey counting and probability
Problem
In a computer network consisting of computers no two cycles intersect. At time , a hacker hacks into a computer in this network; and at time , the network administrator installs a protective software to an unhacked computer. For each positive integer , at time , the hacker hacks into another computer, if there is one, that is not protected and that is directly connected to a hacked computer; and at time , the administrator installs the protective software to another computer, if there is one, that is not hacked and that is directly connected to a protected computer. Determine the maximum number of computers the hacker can guarantee to hack into no matter how the network is configured.
[For , is a cycle if the computers and and, for all , the computers and are directly connected.]
[For , is a cycle if the computers and and, for all , the computers and are directly connected.]
Solution
The answer is .
First consider a network that has a single cycle , and has chains of , and computers starting at , and , respectively. Hacker takes in the first move. Then if the administrator takes , the moves , , , guarantee the hacker computers. Hacker does better for any other response by the administrator. For instance, if the administrator takes in the second move, then the moves , , , give the hacker computers.
Now consider an arbitrary network with computers and without intersecting cycles.
Case 1: There is a computer that is not on a cycle such that, when it is removed from the network, each of the remaining connected components contains at most computers. Then the hacker guarantees to hack into at least computers by hacking into this computer in the first move.
Case 2: There is a cycle such that, when it is removed from the network, each of the remaining connected components contains at most computers. For , let , respectively , be the set of all hacked computers in , respectively in the entire network, when the hacker takes in the first move and from there on both follow their best strategies. Then . Take such that is maximum. If , then , and one of the sets has at least elements. If, on the other hand, , then . In this case, , and therefore, one of the sets has at least elements. In either case the hacker has a strategy guaranteeing at least hacked computers.
Finally, either Case 1 or Case 2 must hold. Otherwise, we can move along the network by moving into the component with more than computers at each step. At some step we must reverse our direction. When this happens we have more than computers to each side of the connection along which we retraced our last step, a contradiction.
First consider a network that has a single cycle , and has chains of , and computers starting at , and , respectively. Hacker takes in the first move. Then if the administrator takes , the moves , , , guarantee the hacker computers. Hacker does better for any other response by the administrator. For instance, if the administrator takes in the second move, then the moves , , , give the hacker computers.
Now consider an arbitrary network with computers and without intersecting cycles.
Case 1: There is a computer that is not on a cycle such that, when it is removed from the network, each of the remaining connected components contains at most computers. Then the hacker guarantees to hack into at least computers by hacking into this computer in the first move.
Case 2: There is a cycle such that, when it is removed from the network, each of the remaining connected components contains at most computers. For , let , respectively , be the set of all hacked computers in , respectively in the entire network, when the hacker takes in the first move and from there on both follow their best strategies. Then . Take such that is maximum. If , then , and one of the sets has at least elements. If, on the other hand, , then . In this case, , and therefore, one of the sets has at least elements. In either case the hacker has a strategy guaranteeing at least hacked computers.
Finally, either Case 1 or Case 2 must hold. Otherwise, we can move along the network by moving into the component with more than computers at each step. At some step we must reverse our direction. When this happens we have more than computers to each side of the connection along which we retraced our last step, a contradiction.
Final answer
671
Techniques
Graph TheoryGames / greedy algorithmsPigeonhole principle