Grades 11-12 Video Solutions 2022-2022_11-12

Video Transcription

The map shows a region with 16 cities connected by roads. The government wants to build electric power plants in some of the cities.  Each power plant can provide enough electricity for the city where it's situated, and any cities connected to that city by a single road.  What's the smallest number of power plants that need to be built? So let's first get a lower bound on the number of power plants that we need to build.  If we put a plant on one of the corner cities, we light up 3 cities in total. If we put a power plant on one of the edge cities, we light up 4 cities in total.  And if we put a power plant on one of the center cities, we light up 5 cities in total. So at maximum we can light up 5 cities with one power plant.  Since we have 16 cities in total, that means we need at least 4 power plants. Now the question is, can we do it in exactly 4?  So first let's try putting a power plant on one of the center cities, because it lights up a lot of things. It's going to light up all of these guys.  But now the question is, what do we do about the corner? We have to light it up somehow, and so either we can put a power plant on it, or on one of its neighbors.  So if we put a power plant right here, the only new city that gets lit up is the corner city, and it just repeats these two. So that's probably not going to help us too much.  If we instead put the power plant on one of its neighbors, it lights up this one and this one, but then these two cities get repeated.  So that's probably not going to help us very much either. So putting something on the center probably isn't going to help us too much, and similarly  putting things on a corner isn't really going to help too much because it doesn't light up too many things. So instead let's focus on these edges.  So now what happens if I put a power plant here? Well now let's look at this edge right here. I need to light up this city somehow, and putting a power plant here is just going to  repeat these two. So instead I'm going to put a power plant here, and by exactly the same reasoning I'm  going to put a power plant here, and then I'm going to put a power plant here. And now we've done the job in four power plants, so our answer is four.

Video Summary

The government needs to build a minimum of four power plants to provide electricity to all 16 cities in the region. Each plant can power its host city and those directly connected by a single road. The optimal strategy is to place plants on edge cities rather than corners or centers, as edges cover more cities without unnecessary repeats. By strategically placing plants on the edges, every city can be covered efficiently with exactly four plants, achieving the objective using the least number possible.

Keywords

power plants

electricity

cities

optimal strategy

efficient coverage