Subsets of points lying in disks

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Subsets of points lying in disks

G H J

Reveal topic tags

combinatorial geometry

L

G H BBookmark kLocked kLocked NReply

Source: Romania TST 2023 Day 2 P4

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1742 posts

oVlad

#1 h Apr 7, 2024, 2:40 PM

Y by

Fix a positive integer $n.{}$ Consider an $n{}$ -point set $S{}$ in the plane. An eligible set is a non-empty set of the form $S\cap D,{}$ where $D$ is a closed disk in the plane. In terms of $n,$ determine the smallest possible number of eligible subsets $S{}$ may contain.

Proposed by Cristi Săvescu

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

40 posts

#2 h Apr 7, 2024, 5:34 PM

Y by

Maybe problem is near to trivialize by BAMO 2020/5 problem....

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1535 posts

#3 h Apr 7, 2024, 6:31 PM • 1 Y

Y by FairyBlade

Interesting

We claim that there are at minimum $\binom{n+1}{2}$ such subsets.

Claim: This can be constructed.
Proof. A construction follows by taking all of $S$ on a line, which gives $\binom{n}{2}$ subsets when there are more than two elements in it, and $n$ more.
This gives a total of $n + \binom{n}{2} = \binom{n+1}{2}$ . $\blacksquare$

Claim: For a set $S$ , we can generate $n+1$ distinct pairs of eligible sets $(A, A')$ where $A' = A \cup \{O\}$ .
Proof. Let one point $O$ of $S$ have minimal $x$ coordinate (rotate the plane until its uniquely minimal).
Take a line that goes through $O$ .
By taking a sufficiently large circle, it can approximate a half plane bordering the line. First have this half plane containg on elements.
Now rotate the line with pivot $O$ . Suppose that when sorted by when they hit the ray, the elements can be ordered as sets $T_1, T_2, \dots$ where $T_i$ is a set of point(s) collinear with $O$ . Then if $T_i = \{P\}$ has size one, we get a pair by considering when point $P$ is added to the set, and when the ray is perturbed such that $O$ isn't in the half plane.
In the case where $T_i$ has size more than one, then we get $|T_i|$ pairs by considering half planes that contain the $k$ th elements closest to $O$ for $1 \le k \le |T_i|$ . We can once again guarentee such a perturbation to not have $O$ in the subsets. $\blacksquare$

Claim: This is minimal.
Proof. We prove this inductively, the base case of $n = 2$ is obvious.
Now suppose that we have a set $S$ of $n + 1$ points. Fix $O$ as before. Then $S \setminus \{O\}$ inductively has at least $\binom{n+1}{2}$ eligible sets.
For each such eligible set, take a representation of it. This creates a matching from eligible sets on $S \setminus \{O\}$ to $S$ which agree on all elements but perhaps $O$ .
For each pair, then take the element of the pair which disagrees on $O$ . This gives that $S$ has at least $\binom{n+1}{2} + n+1 = \binom{n+2}{2}$ . $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

17 posts

#4 h Apr 9, 2024, 4:30 PM

Y by

This is my solution.
The minimum is $\binom{n+1}{2}$ .
We will initially show that for any initial configuration of $S$ we have at least $\binom{n+1}{2}$ eligible subsets.
Claim : For every point in S there is a circle that passes through it and does not pass through the other $n-1$ points.

Let $S={ A_1,A_2,\ldots,A_n }$ .We will prove the claim for $A_1$ . We consider $l$ a straight line that passes through $A_1$ and does not pass through the other n-1 points.We consider $O$ a point on $l$ such that $O$ is not on the perpendicular bisector of $A_1A_i$ for every i from 2 to n.
Now the circle with the center $O$ that passes through $A_1$ respects the condition in the claim .So the claim is proved.

Analogously, we will prove that for any pair of 2 points in $S$ there is a circle that passes through them and does not pass through the other $n-2$ points.So we have at least $n+\binom{n}{2}=\binom{n+1}{2}$ eligible subsets of $S$ .

Now we will build an example in which the minimum is reached.

Thus we consider $n$ distinct collinear points .So the configuration reaches the minimum.

This post has been edited 1 time. Last edited by matematica007, Apr 9, 2024, 4:31 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5 posts

#5 h Apr 11, 2025, 4:44 PM

Y by

Well

There's at least $\binom{n+1}{2}$ eligible subsets. For the intuition, we will first generate the example.

Take $n$ points all in a line, numbered $1, 2, \dots, n$ . If an eligible subset $D$ has "lowest" point $a$ and "greatest" point $b$ , then segment $ab$ will be contained within the disc $D$ that represents the subest, from which all the points $a, a+1, a+2, \dots, b$ are contained within $D$ . This means all of the subsets can be represented by a pair $(a, b)$ , with $1 \leq a \leq b \leq n$ , which can be picked in $\binom{n+1}{2}$ ways.

Now to prove this is the minimum: using the intuition from the example, we "order" the $n$ points from left to right, and number them $1, 2, \dots, n$ .

Explanation and argumentation: pick a line $l$ that is not parallel to any of the lines determined by any pair of points, and place that line outside of the convex hull of the $n$ points. Sort the points from left to right by sorting them in increasing order from $l$ . No two points are at the same distance, because their line can't be parallel to $l$

We need to prove we can construct at least $\binom{n+1}{2}$ sets. For each point $A$ , Start creating a circle passing through $A$ with center $O$ such that $AO \perp l$ , and $A$ is the closest point to $l$ on the circle; we gradually increase the radius of the disc, adding more points into the set until we have every point "greater' than $A$ in our disc. We start only with $A$ , and as we gradually increase the disc we keep adding exactly one* other point greater than $A$ into the disc, we end up with $n - a$ new sets (here $a$ is the order number of $A$ ).

There's an asterisk there, because this logic breaks if at one step we add two or more points. This however happens only if we have three or more points on the same circle and one of the lines through the center and a point in the circle is perpendicular to $l$ . There's only a finite number of such problematic lines, and $l$ takes an infinity of orientations, so just pick an orientation of $l$ for which this does not happen.

The reason why this process only adds points greater than $A$ into the disc is the following: as we gradually increase the disc through $A$ , each such generated disc contains any disc that came before it. As the radius approaches infinity, the disc becomes the half-plane found to the right of the line through $A$ parallel to $l$ , which doesn't contain any point to the left of $A$ .

This means there's at least $n + (n-1) + (n-2) + \dots + 1 = \binom{n+1}{2}$ eligible subsets.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a