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$.
Problem
Source: Polish MO Finals P6 2023
Tags: algebra, combinatorics, interval
20.05.2023 15:55
Any answer?
21.05.2023 07:01
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.
26.05.2023 11:42
You can prove the problem by simply inducting on n.
26.05.2023 20:44
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.