A (probably) simple combinatorial problem

[UD1]

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.

Homework Equations

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 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.

Homework Equations

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?

 

[UD1]

Thanks for your reply, Dick.

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]

Thanks for your reply, Dick.

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]

Ok, think I'm getting a little closer. Here's a hint. If a station is within 2 units of the center of the city then it can transmit to the whole city. If there are two stations in there then you are all done. So suppose there are 0 or 1. The 1 case falls out pretty easily if you use the four circle covering. I'm still struggling with the 0 case.

 

[Dick]

Ah, think I see the 0 case. How are you doing?