An organization has 30 employees, 20 of whom have a brand A computer while the other 10 have a brand B computer. For security, the computers can only be connected to each other and only by cables. The cables can only connect a brand A computer to a brand B computer. Employees can communicate with each other if their computers are directly connected by a cable or by relaying messages through a series of connected computers. Initially, no computer is connected to any other. A technician arbitrarily selects one computer of each brand and installs a cable between them, provided there is not already a cable between that pair. The technician stops once every employee can communicate with every other. What is the maximum possible number of cables used?
Pick one
Solution
Answer (B): Let be one of the computers of brand A. If every brand B computer is connected to every brand A computer other than , then there will be cables, but the employee using computer is completely isolated and cannot communicate with any other. Therefore the requested answer is greater than 190.
To see that 191 cables is the requested maximum, suppose that the technician has installed 191 cables. First note that every brand A computer must have at least one cable attached, because otherwise there would be at most cables. Furthermore, if each of the brand A computers is attached to at most 9 cables, this accounts for at most cables. Therefore at least one brand A computer has 10 cables attached—one leading to each of the brand B machines. Call this brand A computer . A symmetric argument shows that at least one of the brand B computers, say , is attached by 20 cables to every computer of brand A. It now follows that there is a path of length 2, going through , joining any pair of brand B computers; there is a path of length 2, going through , joining any pair of brand A computers; and there is a path of length at most 3, going through and , joining any brand B computer to any brand A computer. Therefore 191 cables guarantee that every employee can communicate with every other, regardless of which pairs of computers are directly connected.