A (probably) simple combinatorial problem

  • Thread starter UD1
  • Start date
  • #1
UD1
20
0

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.
 

Answers and Replies

  • #2
Dick
Science Advisor
Homework Helper
26,263
619

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?
 
  • #3
UD1
20
0
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 [tex]x^2+y^2=4^2,[/tex] the four small circles will have equations [tex](x\pm\sqrt{2})^2+(y\pm\sqrt{2})^2=3^2.[/tex] 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.
 
  • #4
Dick
Science Advisor
Homework Helper
26,263
619
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 [tex]x^2+y^2=4^2,[/tex] the four small circles will have equations [tex](x\pm\sqrt{2})^2+(y\pm\sqrt{2})^2=3^2.[/tex] 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.
 
  • #5
Dick
Science Advisor
Homework Helper
26,263
619
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.
 
Last edited:
  • #6
Dick
Science Advisor
Homework Helper
26,263
619
Ah, think I see the 0 case. How are you doing?
 

Related Threads on A (probably) simple combinatorial problem

  • Last Post
Replies
1
Views
512
  • Last Post
Replies
3
Views
1K
Replies
3
Views
4K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
15
Views
5K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
0
Views
959
  • Last Post
Replies
6
Views
1K
Top