Question 30
A positive integer $n$ is given. There are $n$ computers in a network, numbered with natural numbers $1, 2, \dots, n$. The computers are connected with one-way communication lines such that information can be sent from any computer to all other computers either directly or through other computers in the network. Initially, each computer only knows its own number. When a certain procedure is initiated on any computer, the computer outputs all the numbers of computers it knows and communicates them to all the computers it has direct lines to. The computer operator initiates this procedure on any selected computers in any chosen sequence (possibly multiple times on the same computer).
Prove that the minimum total number of procedure initiations, for which it is possible for all computers to have output the numbers of all computers at least once, does not depend on the network of lines, but only on the number $n$, and find this number of initiations.
Prove that the minimum total number of procedure initiations, for which it is possible for all computers to have output the numbers of all computers at least once, does not depend on the network of lines, but only on the number $n$, and find this number of initiations.