Original problem
If 8 points in a plane are chosen to lie on or inside a circle of diameter 2cm then show that the distance between some two points will be less than 1cm.
My proof
Let the points be $p_1,p_2,\dots,p_8$
Placing point $p_8$ at the center of the circle and placing other seven points on the periphery of the circle, at equal distances.(remember we are required to prove that there are at least a pair of points whose distance from each-other is less than 1cm.)
Now we have one point at the center and seven at the periphery of the circle.
The heptagon which will be formed by joining the seven points on the circle will have all its side equal in length.
The length of the side of the heptagon is less than $\frac{2\pi}{7}$cm which is less than 1cm.
Now if we replace the position of any point then too we get a pair of points whose distance from each-other is less than 1cm.
End of proof
I think that I have proved it correctly. But my brother was saying that this is just a verification because you are choosing the points by yourself. I think that this is a in general proof rather a particular verification.
Is my proof correct in general or not? If not then please provide an in general proof?
EDIT(Another proof)
I was thinking of another technique. In proof by contradiction, for example proving $\sqrt{2}$ is irrational, we first assume that $\sqrt{2}$ is rational and then we use the property of rationals and find that some properties is not true for $\sqrt{2}$, then this contradicts and we say that $\sqrt{2}$ is irrational.
In this proof firstly I'm making a unit circle(with center O). Taking a point on the periphery we draw a circle of radius 1cm, now we say that no other points will lie in the shaded region.
Distance between $p_1$ and $p_2$ is exactly 1cm.
I'm placing a point($p_1$) on the periphery and taking that no other point lie at a distance of less than 1cm from $p_1$. I'm repeating this thing for $p_2$ and $p_3$. If we do this for the fourth point($p_4$), then after that we can see that the unshaded region is very small, from here we can easily show that the separation between a pair of points is less than 1cm.
The reason why I have taken all points on the periphery and not inside the circle.The reason is that, because when we take any point inside the circle then the area covered by that point* inside the circle will be more as compared to when we take that point on the periphery.
*area covered by that point - I mean the area covered by the unit circle with center as that point.
Is this proof correct or not? Is this equivalent to the proof by contradiction or not?
$\endgroup$ 48 Answers
$\begingroup$Original statement
If 8 points in a plane are chosen to lie on or inside a circle of diameter 2cm then show that the distance between some two points will be less than 1cm.
Interpretation
Your problem is that you did not understand the problem, possibly because it is not as clearly phrased as possible. It means the following:
Actual problem
Show that for any arbitrary 8 points that are within or on a circle of radius 1, some 2 of those points will have distance less than 1.
Hints
Find a set of 7 hexagons with diameter 1 that cover the disk of radius 1. Then no matter how the 8 points are placed, at least two must be within the same hexagon, and hence must be at opposite vertices if they are to have distance at least 1. Then check all possible cases.
Full solution
Don't look until you've tried!
$\endgroup$ 8 $\begingroup$
The above picture shows hexagons of diameter 1 covering the unit disk. If there are 8 points in the disk with pairwise distance at least 1, there must be 2 of them in the same hexagon. Any 2 points in the same hexagon must then be at opposite vertices, and thus there also cannot be more than 2 in the same hexagon.
Case 1 (The center hexagon has 2 points): By symmetry we can assume that the 2 points are on the leftmost and rightmost vertices, which would also be in the 4 hexagons to the left and right, and so none of those 4 hexagons can contain any other points since the opposite points would be outside the disk. That leaves the top and bottom hexagon, which can contain at most 1 point each, giving a total of only 4 points, and hence a contradiction.
Case 2 (The center hexagon has at most 1 point): Exclude the rightmost vertex from the top hexagon, and rotationally similarly for all the other hexagons around the circle (such as leftmost vertex from the bottom hexagon). Then the hexagons still cover the unit disk, but now no peripheral hexagon can contain 2 points, because those 2 points must be opposite vertices of the hexagon within the unit disk, but the only such pair is impossible due to the excluded vertices. So the total is at most 7 points, which is a contradiction.
Therefore our assumption that we can have 8 points with pairwise distance at least 1 is incorrect.
As remarked by others your proof is essentially flawed on purely logical grounds (handling of quantifiers). Here is a correct proof:
Partition the disk into six equal sectors so that none of the eight points is a common peripheral vertex of two sectors. Maybe one of the eight points is the center $O$ of the disk, but in any case $\geq7$ points $\ne O$ remain, at least two of them in the same sector and not a vertex of this sector. These two points have a distance $<1$.
$\endgroup$ $\begingroup$Your proof is invalid because you start from a very special configuration and argue that any other configuration could be obtained by moving one of the points. But there are configurations that may require moving several of the points and it is not clear from your proof attempt that this won't work.
Instead, problems of this type are often best solved by considereing discs around the points in question that are distjoint by the distance condition and have a total area that is too big to fit. Here, let's assume we could achieve that all distances are $\ge 1$. Then discs of radius $\frac12$ around these points are disjoint. Their total area is $8\cdot \pi\frac1{2^2}=2\pi$. While these discs may not be wholly inside the given circle of radius $1$, they are certainly contained in the concentric circle of radius $1+\frac12$. The area of that is $\frac94\pi$. Unfortunately, this is slightly more than $2\pi$, so in principle we haven't yet excluded the possibility, but we are pretty close: All that remains (but that might be tricky) is to show that there will always be at least $\frac14\pi$ "gap" space in the enlarged circle (presumably best seen near the perimeter) ...
$\endgroup$ 1 $\begingroup$An alternative solution is to split into two cases right at the start. (It was first hinted at by zhw. but not justified.)
Case 1 (A point is at the centre of the disk): The other points must be on the periphery to maintain distance of at least 1 from that centre point. Your justification that it is impossible is wrong, however, since you did not show that all possible arrangements fail. To do so, divide the periphery into 6 equal cyclic half-open arcs (closed at one end and open at the other), and check that each arc can contain at most 1 point. Thus the periphery can have at most 6 points, giving only 7 points in total.
Case 2 (No point is at the centre of the disk): Divide the disk without the centre into 7 equal sectors (pie slices). Consider any 2 points $A,B$ in a sector with distance at least 1. Extend $\overline{AB}$ until it hits the sector perimeter at $C,D$. Then $C,D$ have distance at least 1. If both of $C,D$ are not on the sector arc, we can scale them from the disk centre until one of them hits the sector arc, and now the points are $E,F$ with $E$ on the arc. $F$ can be moved along the sector perimeter such that $E,F$ grows further apart until $F$ hits the disk centre or the disk perimeter at $G$. If $G$ is the disk centre, one of the above transformations strictly increased the distance, so the original distance was less than 1. If $G$ is on the disk perimeter, then $E,G$ have distance $2\sin(2x)$ for some $x \in [0,\frac{2\pi}{7}]$, which is less than 1.
$\endgroup$ $\begingroup$I agree with your brother. You have shown that your particular placement works. You have not shown thatany placement works.
This might work: In your heptagon, since you are putting 8 points into 7 segments, there must be a segment with two points. If you can show that the diameter of each segment is less than one, you are done.
If not, try to find a division of the circle into 7 segments whose diameter is less than one.
$\endgroup$ 1 $\begingroup$I try to convince myself that there is a clear way to interpret your last paragraph of the proof but I still don't see it works. If all 8 points are moved from your initial set up, then it is hard to justify that still all distances are shorter than 1 cm.
However it is a good start. We can continue this idea. When the first point is in the center, then you pretty much have done the job. Or you just argue that the rest of the points must be on the circle, and it is impossible to have 7.
If the first point is not at the center, draw a circle centered at this point with radius 1. The area not inside the new circle but in the original circle is the place where you can place other points. Since the new circle cannot be inside the original circle, if you place the second point inside the circle and still be able to place 8 points as required, you can still do it by placing the second point on the arc inside the new circle. The other direction is not valid. Without lose of generality place the second point on the original circle.
Similarly you place next point on the original circle, and go on the procedure above. You will be able to place at most 3 points before having no room to place the next point. (Since $\pi = 3.14\dots$) Then done.
$\endgroup$ $\begingroup$Sketch:If one of the points is at the center, we can do what @Singh did. Otherwise, none of the points is the center. Now some closed sector of central angle $\pi/4$ contains at least $2$ of these points. WLOG, one of the points is $(r,0)$ for some $r\in (0,1],$ and the sector is $\{se^{it}: 0\le s \le 1, 0\le t \le \pi/4\}.$ To maximize the distance from this point to any other point in the sector, we need only look on the boundary. (At an interior point you can always move further away.) This is pretty easy - a little geometric reasoning shows we only need look at the distance from $(r,0)$ to $e^{i\pi/4},$ the square of which equals $r^2 - \sqrt 2 r + 1 < 1.$
$\endgroup$ 3 $\begingroup$This problem is valid with 8, 7 and 6 points.
If you have a circle with radius of 1, you can split the circle in sections, like a pie, and you split the pie in 6 sections, each pie slice will have the angle of 60 degrees. At least one pie slice of 60 degrees will have two points.
Now you can work on a pie slice of 60 degrees that has two points, and need to calculate the maximum distance between two points, and that will be 1. you have an triangle with 3 sides of 1, and the radius of the original circle of 1. If it is true for a slice of 60 degrees, it will be true for a slice of 45 degrees as well, that is contained in the bigger slice.
