2021 Fall AMC 12A Problems/Problem 16
Problem
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?
Solution
We claim that to maximize the number of cables used, we isolate one computer and connect all cables for the remaining computers, then connect one more cable for the isolated computer.
If a brand A computer is isolated, then the technician can use at most cables. If a brand B computer is isolated instead, then the technician can use at most cables. Therefore, the answer is
Remark
Suppose that the computers are labeled and We will prove the claim in the first paragraph of this solution:
- With exactly cables, it is possible that some computers cannot communicate with each other.
- With exactly cables, all computers must be able to communicate with each other.
- Between and where and
- Between and where and
- Between and where and
From this solution, it is clear that this claim is true: We isolate and connect all cables for and to get cables. However, cannot communicate with any of these computers.
By the Pigeonhole Principle, we conclude that at least one brand B computer connects to all brand A computers. Without loss of generality, we assume that connects to all brand A computers. On the other hand, we conclude that at least brand A computer connects to all brand B computers. Without loss of generality, we assume that connect to all brand B computers.
Therefore, any two computers must be able to communicate with each other:
The relay is
The relay is
The relay is
~MRENTHUSIASM
See Also
2021 Fall AMC 12A (Problems • Answer Key • Resources) | |
Preceded by Problem 15 |
Followed by Problem 17 |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | |
All AMC 12 Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.