Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

You have a circle of certain radius $r$.

enter image description here

I want to put a number of points in either of the semicircles. However, no two point can be closer than $r$.

The points can be put anywhere inside the semicircle, on the straight line, inside area, or on the circumference. There is no relation among the points of the two semicircles. But as you can see, eventually they will be the same.

How do I find the maximum number of points that can be put inside the semicircle?

share|improve this question
    
Try this: Add some points assuming(such that no points are closer than $r$), when you reach the maximum limit(if you can't put further), contradict that there can't be more than those many points! –  user63477 Mar 28 '13 at 4:24
    
@MontyGill I tried to visualize this as a packing problem of circles of radius $r/2$ inside a semicircle of radius $r$. But the problem is, some points can even be on the straight line (dividing the circle) or circle circumference. –  MMA Mar 28 '13 at 4:36
    
@Inceptio Where do I put the first one? I understand that the first one will affect the subsequent placements and thus will determine the maximum number of points that can be placed. –  MMA Mar 28 '13 at 4:39
    
@MMA Sorry I deleted my comment before I saw your reply, the problem statement has me confused - do you mean that points need to be put in exactly one semicircle? If not, do the same number of points have to be put in both semicircles? –  Monty Gill Mar 28 '13 at 4:40
    
@MMA: Place the first in the corner . Then use compass to draw a circle with radius just more than $r$. –  user63477 Mar 28 '13 at 4:42
show 5 more comments

1 Answer

up vote 2 down vote accepted

The answer is five points. Five points can be achieved by placing one at the center of the large circle and four others equally spaced around the circumference of one semicircle (the red points in the picture below). To show that six points is impossible, consider disks of radius $s$ about each of those five points, where $r/\sqrt3 < s < r$. These five smaller disks completely cover the large half-disk; so for any six points in the large half-disk, at least two of them must lie in the same smaller disk. But then those two points are closer than $r$ to each other.

five circles

share|improve this answer
    
Can you add more clarity about why the 2 points in a disc or radius $s$ must be within distance $r$ of each other? It doesn't seem immediately obvious, especially for $s \approx r$. Of course, there would be lots of overlap, but your argument didn't rely on that. –  Calvin Lin Jan 19 at 17:03
    
I agree it's not immediately obvious, but especially with the picture as a guide, it should be possible to work it out. Try splitting the right half-annulus into four equal pieces and showing that each piece is close enough to the corresponding point on the circumference. –  Greg Martin Jan 20 at 7:15
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.