Covering points with small amount of intervals

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

Covering points with small amount of intervals

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Polish MO Finals P6 2023

The post below has been deleted. Click to close.

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

191 posts

#1 h Mar 30, 2023, 1:35 PM

Y by

For any real numbers $a$ and $b>0$ , define an extension of an interval $[a-b,a+b] \subseteq \mathbb{R}$ be $[a-2b, a+2b]$ . We say that $P_1, P_2, \ldots, P_k$ covers the set $X$ if $X \subseteq P_1 \cup P_2 \cup \ldots \cup P_k$ .

Prove that there exists an integer $M$ with the following property: for every finite subset $A \subseteq \mathbb{R}$ , there exists a subset $B \subseteq A$ with at most $M$ numbers, so that for every $100$ closed intervals that covers $B$ , their extensions covers $A$ .

This post has been edited 1 time. Last edited by TheMathBob, Mar 30, 2023, 1:39 PM

Z K Y

The post below has been deleted. Click to close.

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

107 posts

#2 h May 20, 2023, 12:55 PM

Y by

Any answer?

Z K Y

The post below has been deleted. Click to close.

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

182 posts

hrqdcj

#3 h May 21, 2023, 4:01 AM • 1 Y

Y by alligatorar

We only need to prove: For any $n$ , there exists an integer $M_n$ , such that for any $A\in\mathbb{R}$ , there exists a subset $B$ of $A$ , $|B|\leq M_n$ satisfy: if a total of $\leq n$ sets cover $B$ , then their extensions cover $A$ .
Hint: Try using induction to prove $M_n=3M_{n-1}+2$ is fine.

Z K Y

The post below has been deleted. Click to close.

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

107 posts

#4 h May 26, 2023, 8:42 AM

Y by

You can prove the problem by simply inducting on n.

This post has been edited 1 time. Last edited by Sourorange, May 26, 2023, 8:42 AM
Reason: Adding more

Z K Y

The post below has been deleted. Click to close.

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

1472 posts

math90

#5 h May 26, 2023, 5:44 PM

Y by

For a closed interval $I=[a-b,a+b]\subset\mathbb R$ , define $I^e=[a-2b, a+2b]$ as its extension.

Lemma 1. If $I\subset\mathbb R$ is a closed interval, then $I\subset I^e$ . Moreover, if $I\subset J\subset\mathbb R$ are closed intervals, then $I^e\subset J^e$ .

Proof. Obviously $I\subset I^e$ . Now suppose $I=[a_1-b_1,a_1+b_1]$ and $J=[a_2-b_2,a_2+b_2]$ . Since $I\subset J$ by assumption, we have $b_1\le b_2$ and $a_2-b_2\le a_1-b_1$ . Hence
$a_2-2b_2\le a_1-b_1-b_2\le a_1-2b_1.$ Moreover, $a_1+b_1\le a_2+b_2$ so
$a_1+2b_1\le a_2+b_2+b_1\le a_2+2b_2.$ Therefore $I^e\subset J^e$ . $\square$

Now we prove a general lemma, which solves the initial problem.

Lemma 2. Let $n$ be a positive integer. Then there exists a positive integer $M_n$ with the following property: for every finite subset $A \subseteq \mathbb{R}$ , there exists a subset $B \subseteq A$ with at most $M_n$ elements, so that for every collection of $n$ closed intervals that covers $B$ , their extensions covers $A$ .

Proof. We will prove the lemma by induction on $n$ . For the base case $n=1$ , we will prove that $M_1=2$ works. Let $a=\min(A)$ and $b=\max(A)$ . Now choose $B=\{a,b\}$ . Then $|B|\le 2$ , and every closed interval which covers $B$ also covers $A$ , hence by lemma 1 its extension covers $A$ .
Now suppose the claim is true for $n$ and we will prove the claim for $n+1$ . We will prove that $M_{n+1}=3M_n+2$ works. If $|A|\le 1$ then $M_{n+1}=1$ works, so assume $|A|\ge 2$ . Let $a=\min(A)$ and $b=\max(A)$ . Moreover define closed intervals $I_1=\left[a,a+\frac{1}{3}(b-a)\right]$ , $I_2=\left[a+\frac{1}{3}(b-a),a+\frac{2}{3}(b-a)\right]$ and $I_3=\left[a+\frac{2}{3}(b-a),b\right]$ . This way, we partition $[a,b]$ into three equal closed intervals. An easy observation is that $I_3\subset (I_1\cup I_2)^e$ and $I_1\subset (I_2\cup I_3)^e$ . Let $A'=A\setminus\{a,b\}$ . For $i\in\{1,2,3\}$ we define $A_i=I_i\cap A'$ . By induction hypothesis, for each $i=1,2,3$ there exists a subset $B_i\subset A_i$ with at most $M_n$ elements, so that for every collection of $n$ closed intervals that covers $B_i$ , their extensions covers $A_i$ . We will prove that $B=B_1\cup B_2\cup B_3\cup\{a,b\}$ works. By the union bound we have $|B|\le 3M_n+2=M_{n+1}$ , so this will prove the induction step. Now let $\{J_i\}_{i=1}^{n+1}$ be a collection of $n+1$ closed intervals that covers $B$ .

Claim 1. We have $A_1\subset\bigcup_{i=1}^{n+1}J_i^e$ and $A_3\subset\bigcup_{i=1}^{n+1}J_i^e$ .

Proof. By symmetry, it suffices to prove that $A_1\subset\bigcup_{i=1}^{n+1}J_i^e$ . We consider two cases.

Case 1. There exists an integer $i\in[1,n+1]$ such that $J_i\cap B_1=\emptyset$ . WLOG $J_{n+1}\cap B_1=\emptyset$ . Therefore
$B_1=\bigcup_{i=1}^{n+1}(B_1\cap J_i)=\bigcup_{i=1}^n(B_1\cap J_i)\subset \bigcup_{i=1}^n J_i.$ Therefore, by induction hypothesis, $A_1\subset\bigcup_{i=1}^n J_i^e\subset\bigcup_{i=1}^{n+1} J_i^e$ .
Case 2. For every integer $i\in[1,n+1]$ we have $J_i\cap B_1\neq\emptyset$ . As $b\in \bigcup_{i=1}^{n+1}J_i$ we can assume WLOG that $b\in J_1$ . By assumption there exists $c\in J_1\cap B_1$ . Hence $I_2\cup I_3\subset[c,b]\subset J_1$ so
$A_1\subset I_1\subset I_1^e\subset (I_2\cup I_3)^e\subset J_1^e\subset\bigcup_{i=1}^{n+1}J_i^e.$

As we have exhausted all cases, this ends our proof. $\square$

Claim 2. We have $A_2\subset\bigcup_{i=1}^{n+1}J_i^e$ .

Proof. We consider two cases.

Case 1. There exists an integer $i\in[1,n+1]$ such that $J_i\cap B_2=\emptyset$ . WLOG $J_{n+1}\cap B_2=\emptyset$ . Therefore
$B_2=\bigcup_{i=1}^{n+1}(B_2\cap J_i)=\bigcup_{i=1}^n(B_2\cap J_i)\subset \bigcup_{i=1}^n J_i.$ Therefore,by induction hypothesis, $A_2\subset\bigcup_{i=1}^n J_i^e\subset\bigcup_{i=1}^{n+1} J_i^e$ .
Case 2. For every integer $i\in[1,n+1]$ we have $J_i\cap B_2\neq\emptyset$ . As $a\in \bigcup_{i=1}^{n+1}J_i$ , there exists an integer $p\in[1,n+1]$ such that $a\in J_p$ . By assumption there exists $c\in J_p\cap B_2$ . Hence $I_1\subset[a,c]\subset J_p$ so
$J_p^e\supset I_1^e=\left[a-\frac{1}{6}(b-a),a+\frac{1}{2}(b-a)\right]\supset\left[a,\frac{a+b}{2}\right].$ By symmetry, there exists an integer $q\in[1,n+1]$ such that $J_q^e\supset\left[\frac{a+b}{2},b\right]$ so
$A_2\subset [a,b]=\left[a,\frac{a+b}{2}\right]\cup\left[\frac{a+b}{2},b\right]\subset J_p^e\cup J_q^e\subset\bigcup_{i=1}^{n+1}J_i^e.$

As we have exhausted all cases, this ends our proof. $\square$

As $a\in B$ and $b\in B$ , we have $\{a,b\}\subset\bigcup_{i=1}^{n+1}J_i\subset\bigcup_{i=1}^{n+1}J_i^e$ . Therefore
$A=A_1\cup A_2\cup A_3\cup\{a,b\}\subset\bigcup_{i=1}^{n+1}J_i^e.\square$
Now substitute $n=100$ and finish.

Remark

This post has been edited 1 time. Last edited by math90, May 29, 2023, 8:30 PM
Reason: typo

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a