1
$\begingroup$

Given a segment and a value $c$ less than the segment length, let $A_1,\dots,A_n$ be disjoint finite unions of intervals on the segment. We choose a finite union of intervals $B$ with $|B|=c$ that maximizes $|B\cap A_1|\times\dots\times |B\cap A_n|$, where $|\cdot|$ denotes the length (i.e. Lebesgue measure). If there are many such $B$, we choose one arbitrarily.

Now, we shrink $A_1$ to $A_1'\subseteq A_1$, and choose $B'$ using the same procedure. Is it always true that $|B'\cap A_1'|\le |B\cap A_1|$?

$\endgroup$

1 Answer 1

2
$\begingroup$

$\newcommand\ta{\tilde a} \newcommand\tb{\tilde b} \newcommand{\ep}{\varepsilon}$The answer is yes at least in the case when the $A_i$'s are pairwise disjoint. Indeed, then we can restate the problem as follows (with $a_i$ in place of $|A_i|$ and $b_i$ in place of $|B\cap A_i|$):

Take any $a=(a_1,\dots,a_n)\in(0,\infty)^n$. Let $c\in(0,\sum_i a_i)$. Let $$B(a):=B_c(a):=\{b=(b_1,\dots,b_n)\colon \sum_i b_i=c, 0\le b_j\le a_j\ \forall i\}.$$ The set $B_c(a)$ is compact and nonempty, since $ta\in B_c(a)$ for $t:=c/\sum_i a_i\in(0,1)$.

Let then $b=(b_1,\dots,b_n)$ be any maximizer of $\pi(b):=b_1\cdots b_n$ over all $b\in B(a)$. In view of the last sentence of the previous paragraph, such a maximizer $b$ exists and $\pi(b)\in(0,\infty)$ for such $b$.

Take any $j\in[n]:=\{1,\dots,n\}$ and replace $a_j$ by some real \begin{equation} \ta_j\ge a_j, \tag{1} \end{equation} to get $\ta:=(\ta_1,\dots,\ta_n)$, where $\ta_i:=a_i$ for $i\ne j$. Let $\tb=(\tb_1,\dots,\tb_n)$ be any maximizer of $\pi(b)$ over all $b\in B(\ta)$. Does it then follow that $\tb_j\ge b_j$?

Let us show that the answer is yes. Indeed, without loss of generality (wlog) $$a_1\ge\dots\ge a_n>0.$$

If $b_i<b_{i+1}$ for some $i\in[n-1]$, then $0\le b_i<b_{i+1}\le a_{i+1}\le a_i$, and so, we can replace $b_i,b_{i+1}$ by $b_i+\ep,b_{i+1}-\ep$ with $\ep\in(0,\min(a_i-b_i,\frac{b_{i+1}-b_i}2))$, thus still satisfying the conditions on $b$ while making the value of $\pi$ greater, which contradicts the assumption that $b$ is a maximizer of $\pi$. So, \begin{equation} b_1\ge\dots\ge b_n>0.\tag{1.5} \end{equation}

Since $0\le b_j\le a_j$ for all $j$ and $\sum_i b_i=c<\sum_i a_i$, there is some $k\in[n]$ with $b_k<a_k$. If $k\ge2$ and $b_{k-1}>b_k$, then we can replace $b_{k-1},b_k$ by $b_{k-1}-\ep,b_k+\ep$ with $\ep\in(0,\min(a_k-b_k,\frac{b_{k-1}-b_k}2))$, thus still satisfying the conditions on $b$ while making the value of $\pi$ greater, which contradicts the assumption that $b$ is a maximizer of $\pi$. So, $$b_k<a_k\implies b_{k-1}=b_k<a_k\le a_{k-1}\implies b_{k-1}<a_{k-1}\implies\cdots.$$ So, there is some $m\in[n]$ such that \begin{equation} b_1=\cdots=b_m>b_{m+1}=a_{m+1}\ge\cdots \ge b_n=a_n>0,\tag{2} \end{equation} whence \begin{equation} b_i=\min(b_1,a_i)\tag{3} \end{equation} for all $i$.

Let us say that $i\in[n]$ is a drop point for $a$ if either (i) $i=1$ or (ii) $i\ge2$ and $a_{i-1}>a_i$. Let us then define the drop value at a drop point $i$ as $a_{i-1}-a_i$ if $i\ge2$ and as $\infty$ if $i=1$. For each $j\in[n]$, there is always a permutation of the indices leaving $a$ invariant after which $j$ becomes a drop point (of $a$). So, wlog $j$ in (1) is a drop point. Moreover, we may assume that $\ta_j-a_j$ is no greater than the drop value at $j$ (otherwise, increasing $\ta_j$ continuously until $\ta_j-a_j$ reaches the drop value at $j$, we switch from $j$ to the next drop point -- say $j_1$ -- of $a$ to the left of $j$ and continue continuously increasing $\ta_{j_1}$, etc.). Thus, wlog $$\ta_1\ge\dots\ge\ta_n>0.$$

So, similarly to (1.5), we get $\tb_1\ge\dots\ge \tb_n>0$ and hence, similarly to (3), we get \begin{equation} \tb_i=\min(\tb_1,\ta_i)\tag{4} \end{equation} for all $i$.

Take any $j\in[n]$ such that (1) holds. We have to show that then $\tb_j\ge b_j$. Suppose the contrary: \begin{equation} \tb_j<b_j. \tag{5} \end{equation} Then $\tb_j<b_j\le a_j\le\ta_j$.

Suppose now that $\exists i\in[n]\ \tb_i>\tb_j$. Then we can replace $\tb_i,\tb_j$ by $\tb_i-\ep,\tb_j+\ep$ with $\ep\in(0,\min(\ta_j-\tb_j,\frac{\tb_i-\tb_j}2))$, thus still satisfying the conditions on $\tb$ while making the value of $\pi$ greater, which contradicts the assumption that $\tb$ is a maximizer of $\pi$.

So, $\tb_j\ge\tb_i$ for all $i$. So, in view of (4), (5), and (3), $\tb_1=\tb_j<b_j\le b_1$, whence, by (3) and (4) $\tb_i\le b_i$ for all $i$, with $\tb_1<b_1$, so that $c=\sum_i\tb_i<\sum_i b_i=c$.

Thus, (5) leads to a contradiction. $\Box$.

$\endgroup$
3
  • $\begingroup$ I don't see why the restated problem is the same. In the original problem, the $|B\cap A_i|$'s can sum up to more than $c$ (the sets $A_i$'s can overlap). $\endgroup$
    – pi66
    Commented Oct 15, 2020 at 2:25
  • $\begingroup$ @pi66 : You are right. Somehow, my impression was that the $A_i$'s are disjoint. The current proof only works in this case, which seems already rather nontrivial. The general case seems much harder, unless there is a counterexample. $\endgroup$ Commented Oct 15, 2020 at 4:10
  • 1
    $\begingroup$ Thanks. Since this is indeed already rather nontrivial, I've edited the question so that I can accept your answer, and posted the general question here. $\endgroup$
    – pi66
    Commented Oct 17, 2020 at 4:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .