# A (probably) simple combinatorial problem

## Homework Statement

In a circle city of radius 4 we have 18 cell phone power stations. Each station covers the area at distance within 6 from itself. Show that there are at least two stations that can transmit to at least five other stations.

## The Attempt at a Solution

All I can say is that I'm pretty sure this is an application of the pigeonhole principle.

Dick
Homework Helper

## Homework Statement

In a circle city of radius 4 we have 18 cell phone power stations. Each station covers the area at distance within 6 from itself. Show that there are at least two stations that can transmit to at least five other stations.

## The Attempt at a Solution

All I can say is that I'm pretty sure this is an application of the pigeonhole principle.

I think you have to do a little geometry as well. If you draw a circle of radius 3, then any two stations within that circle can talk to each other. Can you think of a scheme to cover a circle of radius 4 with a small number of circles of radius 3?

I don't see how you can cover a circle of radius 4 by 3 circles radius 3 each, but 4 such circles is definitely enough. For instance, putting the center of the coordinate system at the center of the circle, so that it has equation $$x^2+y^2=4^2,$$ the four small circles will have equations $$(x\pm\sqrt{2})^2+(y\pm\sqrt{2})^2=3^2.$$ It's easy to check that they really cover the big circle. Then by pigeonhole, at least one of the small circles contains at least five stations, so that they all can talk to each other. However, I still don't see how the result follows from this.

Dick
Homework Helper

I don't see how you can cover a circle of radius 4 by 3 circles radius 3 each, but 4 such circles is definitely enough. For instance, putting the center of the coordinate system at the center of the circle, so that it has equation $$x^2+y^2=4^2,$$ the four small circles will have equations $$(x\pm\sqrt{2})^2+(y\pm\sqrt{2})^2=3^2.$$ It's easy to check that they really cover the big circle. Then by pigeonhole, at least one of the small circles contains at least five stations, so that they all can talk to each other. However, I still don't see how the result follows from this.

Yes, you are right. That only gives you stations that can talk to four other stations. Better keep thinking about this.

Dick