Question

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 each other. What is the maximum possible number of cables used?

$190$

$191$

$192$

$195$

$196$

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 $19$ brand A computers to all $10$ brand B computers.

That uses $19 \cdot 10 = 190$ cables while still disconnected. The next cable connects the last brand A computer, joining everyone, for a total of $190 + 1 = 191.$

Thus, the correct answer is B.

2021 AMC 12A Fall Problem 16

Solution:

Problem 16 in Other Years