1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A (probably) simple combinatorial problem

  1. Mar 6, 2012 #1

    UD1

    User Avatar

    1. The problem statement, all variables and given/known data

    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.


    2. Relevant equations



    3. The attempt at a solution

    All I can say is that I'm pretty sure this is an application of the pigeonhole principle.
     
  2. jcsd
  3. Mar 6, 2012 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
  4. Mar 7, 2012 #3

    UD1

    User Avatar

    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.
     
  5. Mar 7, 2012 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Yes, you are right. That only gives you stations that can talk to four other stations. Better keep thinking about this.
     
  6. Mar 7, 2012 #5

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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: Mar 7, 2012
  7. Mar 7, 2012 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Ah, think I see the 0 case. How are you doing?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: A (probably) simple combinatorial problem
Loading...