Estonian Mathematical Olympiad

We will show that $2n-1$ initiations are necessary regardless of the network of lines. Consider an arbitrary sequence of initiations, at the end of which all computers have output the numbers of all computers. Let $A$ be the computer with the latest time of the initiation of the first procedure. Since the procedure has been initiated at least once in all other computers by that time, the order number of this initiation is at least $n$. Therefore, after the first $n-1$ initiations, no computer has output the number of computer $A$. To ensure that each computer outputs the number of computer $A$ at least once, $n$ more initiations are needed. Thus, at least $2n-1$ initiations are necessary.

Now we will show that $2n-1$ initiations are sufficient regardless of the network of lines. Choose an arbitrary computer $A$ and construct a sequence of the remaining computers $B_1,B_2,\dots ,B_{n-1}$ without repetition, such that each computer in this sequence can receive information directly from some preceding computer in this sequence or from computer $A$. Such a sequence of length $n-1$ indeed exists, because if at any step adding the next computer was not possible, then from none of the already included computers in the sequence nor from computer $A$ could information be sent directly to any of the remaining computers – which contradicts the condition of the problem that information can move between these computers via the network. Similarly, construct a sequence of computers $C_1,C_2,\dots ,C_{n-1}$ without repetition, such that each computer in this sequence can send information directly to some preceding computer in this sequence or to computer $A$. By symmetry considerations, such a sequence also exists. It turns out that a suitable sequence of procedure initiations of length $2n-1$ is $C_{n-1},C_{n-2},\dots ,C_1,A,B_1,B_2,\dots ,B_{n-1}$.

We will prove this statement; for simplicity, denote $C_0=A$. According to the construction of the sequence $C_1,C_2,\dots ,C_{n-1}$, each computer $C_i$ where $0<i$, sends its number to at least one computer $C_{i^{\prime }}$ where $0\le i^{\prime }<i$. If $0<i^{\prime }$, then computer $C_{i^{\prime }}$ in turn sends the number of computer $C_i$ to at least one computer $C_{i^{\prime \prime }}$ where $0\le i^{\prime \prime }<i^{\prime }$. Continuing in this way, the number of computer $C_i$ reaches computer $C_j$ for successively smaller indices $j$. Since there are $n-1$ computers besides $A$, the number of computer $C_i$ must reach computer $A$ in at most $n-1$ steps. Since $C_i$ was chosen arbitrarily, the numbers of all other computers reach computer $A$ within the first $n-1$ initiations of the procedure. It remains to note that during each subsequent initiation of the procedure, all computer numbers are output and transmitted. This is evidently done by computer $A$, and when all computers $B_1,B_2,\dots ,B_{i-1}$ have done this, then by the construction of the sequence $B_1,B_2,\dots ,B_{n-1}$, computer $B_i$ also does this. Consequently, after $2n-1$ initiations of the procedure, all computers have output the numbers of all computers at least once.