10 9 8 E2 76 54 Cell Towers AAAA 3 2 1 A B C D E F GHI J As the head of analytics for a cell phone company, you have been asked to optimize the location of cell towers in a new area where your company wants to provide service. The new area is made up of several neighborhoods. Each neighborhood is represented by a black house icon in the accompanying image. A cell tower can be placed on any square (including squares with or without a neighborhood). Once placed, a cell tower provides service to 9 squares (the 8 adjacent squares surrounding it and the one it sits on). For example, if you placed a cell tower in B2, it would provide service to A1, B1, C1, A2, B2, C2, A3, B3, and C3. The company recognizes that it may not be worthwhile to cover all neighborhoods, so it has instructed you that it needs to cover only 70% of the neighborhoods in the new area. Each cell tower is expensive to construct and maintain so it is in your best interest to only use the minimum number of cell towers. Questions 1. What is the minimum number of cell towers needed to provide service to at least 70% of the neighborhoods? 2. Now assume that the cell tower can provide 100% service to only the neighbourhood it is placed on. To all remaining neighborhoods it can provide a coverage of 50% only (e.g. if you place a tower to G6, G6 is 100% covered. But F6,H6,G5, and G7 are only 50% covered. What is the minimum number of towers needed to provide service to at least 70% of the neighborhoods? 3. Repeat (1) and (2) for at least 90% coverage. 4. How realistic is this problem for placing real cell towers in a new neighborhood? Are there any aspects of the problem that are not considered at all?