Maths Olympiad Prep

Library / /22 of 23

Combinatorics Difficulty 6.1 National Olympiad Find the answer United States

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 PP be one of the computers of brand A. If every brand B computer is connected to every brand A computer other than PP, then there will be 1019=19010 \cdot 19 = 190 cables, but the employee using computer PP 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 1910=19019 \cdot 10 = 190 cables. Furthermore, if each of the brand A computers is attached to at most 9 cables, this accounts for at most 209=18020 \cdot 9 = 180 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 RR. A symmetric argument shows that at least one of the brand B computers, say SS, is attached by 20 cables to every computer of brand A. It now follows that there is a path of length 2, going through RR, joining any pair of brand B computers; there is a path of length 2, going through SS, joining any pair of brand A computers; and there is a path of length at most 3, going through RR and SS, 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.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.