I have found this tough combinatorial geometry question in some Soviet math competition circa $1972$. It looks very simple (and rather natural), yet I cannot find the proof for quite some time now.
$2n$ points are given on the plane. Prove that there exist $n$ non-overlapping circles, each containing exactly two given points.
Note: Circle here means a filled circle, not a circumference.
There is a version of this problem which is, probably, easier... yet not so easy that I can figure the solution right away.
Given an arbitrary subset of the plane consisting of $2n$ points, is it true that there always exist $n$ non-overlapping squares, each containing exactly two points from the subset?
In both versions the covering shapes (circles or squares) are allowed to touch each other but they cannot have common interior points.
It turns out that the first statement is simply false. As a counterexample, consider a very large natural number $n$ and then the set of $2n$ points, consisting of $2n-1$ vertices of a regular polygon with $2n-1$ sides plus its center. Proving that this set is, indeed, a counterexample to the first statement, is not trivial. The proof is technically tough (despite being rather straightforward), since it requires wading through quite a few boring geometric and trigonometric inequalities.
However, we can discard the requirement that the circles do not overlap, replacing it with the requirement that their intersections do not contain any points from the given set. Thus, the seemingly more reasonable variant of the original problem looks like this:
$2n$ points are given on the plane. Prove that they can be covered by $n$ disks, each of them containing exactly two of the points.
The resulting problem is still not at all trivial. I guess that the proof can be attempted using Delaunay triangulation... remember, however, that the given set does not have to consist of points in general position.
An attempt: pair the points such that the sum of pairwise distances is minimal. This give a solution to an older problem. It may solve this one too.
( that was a useful try, that in fact directed us to the solution, see below).
$\bf{Added:}$ In fact one should choose a pairing $A_i B_i$ such that the sum $$\sum |A_i B_i|^2$$ is minimal. Then the circles with diameter $A_i B_i$ do not intersect.
For a convex quadrilateral, two circles with diamaters opposite edges intersect, while the other do not, and this depends on the angle of diagonals, and also, on which pair has sum of squares smaller.
For such a pairing, the segments $A_i B_i$ and $A_j B_j$ do not intersect, simple to see (assume the contrary, consider them diagonals, and choose instead the pair opposite acute angle).
Note that is also solves the older problem where the segments should not intersect. Now sometime the sum of squares minimum is also sum minimum, but it's not clear how that differs, and whether sum minimum does solve this problem at hand.
Here is a picture: in a convex quadrilateral, build circles with diameters the sides. Then those opposite circles intersect for which the corresponding diagonal angle is obtuse.
$\bf{Added:}$ Here is an example of a configuration of $4$ points giving some counterexamples. Consider an isosceles trapezoid with orthogonal diagonals, whose intersection cuts them into segments $a<b$. Now we have $\sqrt{2}(a+b) < 2 \sqrt{a^2+b^2}$, so the sum of bases is $<$ sum of sides. Now modify a bit the angle of diagonal to make the bases oppose an obtuse angle. Now we get the example where the sum of sides is smallest, but the sum of squares is not.
$\bf{Added:}$ @Calvin Lin: was kind to point out that the proof does not work if $4$ of the points form a concave quadrilateral. Therefore, as it stands, the proof only works for points that are vertices of a convex polygon, a restrictive condition. I'll see what can be said about the general case.