Given a segment and a value $c$ less than the segment length, let $A_1,\dots,A_n$ be 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|$?

If $A_1,\dots,A_n$ are disjoint finite unions, the answer is positive, as shown here.


$\newcommand\om\omega\newcommand\Om\Omega\newcommand\de\delta$As in the linked answer, this problem on sets can be restated as the following problem on real numbers.

Let $\Om:=\{0,1\}^n$. For each $\om\in\Om$ and each $i\in[n]:=\{1,\dots,n\}$, let $\om_i$ denote the $i$th coordinate of the vector $\om$, so that $\om=(\om_1,\dots,\om_n)$.

For any $a=(a^\om)\in[0,\infty)^\Om$ and any $c\in[0,\sum_{\om\in\Om} a^\om]$, let $$B(a):=B_c(a):=\Big\{b=(b^\om)\in[0,\infty)^\Om\colon0\le b^\om\le a^\om\ \forall\om\in\Om,\sum_{\om\in\Om\setminus\{(0,\dots,0)\}}b^\om=c\Big\}.$$

Let $b(a)=b_c(a)$ be any maximizer of $$\pi(b):=\prod_{i=1}^n\sum_{\om\in\Om\colon\,\om_i=1}b^\om$$ over all $b\in B(a)$.

Take now any $u=(u^\om)\in[0,\infty)^\Om$ such that $u^\om\le a^\om$ for all $\om\in\Om$ with $\om_1=1$ and $u^\om=a^\om$ for all $\om\in\Om$ with $\om_1=0$. Let $b(u)=b_c(u)$ be any maximizer of $\pi(b)$ over all $b\in B(u)$. Does it then necessarily follow that $$\sum_{\om\in\Om\colon\,\om_i=1}b(u)^\om\le\sum_{\om\in\Om\colon\,\om_i=1}b(a)^\om?$$

In this restatement, for all $\om\in\Om$

  • $a^\om$ stands for $|A^\om|$, where $A^\om:=A^{\om_1}\cap\cdots\cap A^{\om_n}$ and, for $\de\in\{0,1\}$ and $A\subseteq J$, where $J$ is the segment in question, we let $A^\de:=A$ if $\de=1$ and $A^\de:=J\setminus A$ if $\de=0$;
  • $b^\om$ stands for $|B\cap A^\om|$.

We see that even the restated problem, in terms of real numbers, concerns maximizing the non-convex/non-concave function $\pi(\cdot)$ over a polytope of dimension $2^n-1$, defined by $2^{n+1}$ affine inequalities. Moreover, we need to compare solutions of two such problems. This seems hard! If someone can answer this question, it could be quite an instructive moment!

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.