PUZZLOR

Cell towers

John Toczek
puzzlor@gmail.com

cell towers

Figure 1: How many cell towers are needed?

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 (Figure 1).

A cell tower can be placed on any square (including squares with or without a neighborhood). Once placed, a cell tower provides service to nine squares (the eight 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 percent 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.

Question:

What is the minimum number of cell towers needed to provide service to at least 70 percent of the neighborhoods?

Send your answer to puzzlor@gmail.com by June 15. The winner, chosen randomly from correct answers, will receive a $25 Amazon Gift Card. Past questions and answers can be found at puzzlor.com.

John Toczek is the assistant vice president of Predictive Modeling at Chubb in the Decision Analytics and Predictive Modeling department. He earned his BSc. in chemical engineering at Drexel University (1996) and his MSc. in operations research from Virginia Commonwealth University (2005).