Olympiad Maths Prep

Library / /4 of 4

Combinatorics Difficulty 6.7 National olympiad Prove it Turkey

In a computer network consisting of 20082008 computers no two cycles intersect. At time t=0t = 0, a hacker hacks into a computer in this network; and at time t=1t = 1, the network administrator installs a protective software to an unhacked computer. For each positive integer kk, at time t=2kt = 2k, 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 t=2k+1t = 2k + 1, 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 m3m \ge 3, {C1,C2,,Cm}\{C_1, C_2, \dots, C_m\} is a cycle if the computers C1C_1 and CmC_m and, for all 2im2 \le i \le m, the computers Ci1C_{i-1} and CiC_i are directly connected.]

Solution

The answer is 671671.

First consider a network that has a single cycle {C1,C2,C3,C4,C5,C6}\{C_1, C_2, C_3, C_4, C_5, C_6\}, and has chains of 668668, 667667 and 667667 computers starting at C1C_1, C3C_3 and C5C_5, respectively. Hacker takes C1C_1 in the first move. Then if the administrator takes C4C_4, the moves C2C_2, C3C_3, C6C_6, C5C_5 guarantee the hacker 671671 computers. Hacker does better for any other response by the administrator. For instance, if the administrator takes C2C_2 in the second move, then the moves C6C_6, C3C_3, C5C_5, C4C_4 give the hacker 13381338 computers.

Now consider an arbitrary network with 20082008 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 13371337 computers. Then the hacker guarantees to hack into at least 20081337=6712008 - 1337 = 671 computers by hacking into this computer in the first move.

Case 2: There is a cycle Z={C1,C2,,Cm}Z = \{C_1, C_2, \dots, C_m\} such that, when it is removed from the network, each of the remaining connected components contains at most 13371337 computers. For 1im1 \le i \le m, let HiH_i, respectively GiG_i, be the set of all hacked computers in ZZ, respectively in the entire network, when the hacker takes CiC_i in the first move and from there on both follow their best strategies. Then Hi=m/2|H_i| = \lfloor m/2 \rfloor. Take i,ji, j such that HiHj|H_i \cup H_j| is maximum. If Z=HiHjZ = H_i \cup H_j, then Gi+Gj2008|G_i| + |G_j| \ge 2008, and one of the sets Gi,GjG_i, G_j has at least 10041004 elements. If, on the other hand, CkZ(HiHj)C_k \in Z \setminus (H_i \cup H_j), then HiHjHk=ZH_i \cup H_j \cup H_k = Z. In this case, Gi+Gj+Gk2008+3|G_i| + |G_j| + |G_k| \ge 2008+3, and therefore, one of the sets Gi,Gj,GkG_i, G_j, G_k has at least 2011/3=671\lfloor 2011/3 \rfloor = 671 elements. In either case the hacker has a strategy guaranteeing at least 671671 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 13371337 computers at each step. At some step we must reverse our direction. When this happens we have more than 13371337 computers to each side of the connection along which we retraced our last step, a contradiction.

Looking for a route rather than an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.