2021 Fall AMC 12A Problem 16
Problem 16 of 25IntermediateAlgebraCounting & Probability
An organization has employees, of whom have a brand A computer while the other 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 each other. What is the maximum possible number of cables used?
Answer choices
Show solution
Solution
The technician keeps adding cables until the graph becomes connected. To maximize the count, keep the network disconnected for as long as possible: leave a single brand A computer isolated and fully connect the remaining brand A computers to all brand B computers.
That uses cables while still disconnected. The next cable connects the last brand A computer, joining everyone, for a total of
Thus, the correct answer is B.