Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2021 Fall AMC 12A Problems/Problem 16"

(Created page with "== Problem == An organization has <math>30</math> employees, <math>20</math> of whom have a brand A computer while the other <math>10</math> have a brand B computer. For secur...")
 
(→‎Solution)
Line 8: Line 8:
 
<b>POLISHING. NO EDIT PLEASE. A MILLION THANKS</b>
 
<b>POLISHING. NO EDIT PLEASE. A MILLION THANKS</b>
  
−
To maximize the number of cables used, we isolate one computer, connect all cables for the remaining <math>29</math> computers, and connect one more cable for the isolated computer.
+
We claim that to maximize the number of cables used, we isolate one computer, connect all cables for the remaining <math>29</math> computers, and connect one more cable for the isolated computer.
  
 
If a brand A computer is isolated, then the technician can use at most <math>19\cdot10+1=191</math> cables. If a brand B computer is isolated instead, then the technician can use at most <math>20\cdot9+1=181</math> cables. Therefore, the answer is <math>\boxed{\textbf{(B)}\  191}.</math>
 
If a brand A computer is isolated, then the technician can use at most <math>19\cdot10+1=191</math> cables. If a brand B computer is isolated instead, then the technician can use at most <math>20\cdot9+1=181</math> cables. Therefore, the answer is <math>\boxed{\textbf{(B)}\  191}.</math>
 +
 +
<u><b>Remark</b></u>
 +
 +
We will prove the claim in the first paragraph:
 +
 +
Suppose
  
 
~MRENTHUSIASM
 
~MRENTHUSIASM

Revision as of 20:55, 23 November 2021

Problem

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?

$\textbf{(A)}\ 190 \qquad\textbf{(B)}\ 191 \qquad\textbf{(C)}\ 192 \qquad\textbf{(D)}\ 195 \qquad\textbf{(E)}\ 196$

Solution

POLISHING. NO EDIT PLEASE. A MILLION THANKS

We claim that to maximize the number of cables used, we isolate one computer, connect all cables for the remaining $29$ computers, and connect one more cable for the isolated computer.

If a brand A computer is isolated, then the technician can use at most $19\cdot10+1=191$ cables. If a brand B computer is isolated instead, then the technician can use at most $20\cdot9+1=181$ cables. Therefore, the answer is $\boxed{\textbf{(B)}\ 191}.$

Remark

We will prove the claim in the first paragraph:

Suppose

~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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2021_Fall_AMC_12A_Problems/Problem_16&oldid=165735"