Shrinking subset and product

Question

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.

Answer 1

OK, it seems that this is a counterexample.

Take 8 disjoint segments $I_1,\dots,I_8$ of length 1. Take 8 sets $$ S_1=\{1,2,3\}, \quad S_2=\{4,5,6\}, \quad S_3=\{1,2,4\}, \quad S_4=\{1,2,5\}, \\ S_5=\{1,2,6\}, \quad S_6=\{1,3,4\}, \quad S_7=\{1,3,5\}, \quad S_8=\{1,3,6\}. $$ Say that $I_i$ lies in $A_j$ iff $j\in S_i$, otherwise $I_i$ and $A_j$ are disjoint. Finally, set $c=2$.

In this situation, the optimal $B$ is $I_1\cup I_2$. where the product equals $1$. This follows from the fact that $\sum_j |B\cap A_j|\leq 6$, since any point is covered by at most three of the $A_j$.

Now set $A_1’=A_1\setminus I_1$. Consider the quantities $$ x=\left|B’\cap\left(\bigcup_{i=3}^8 I_i\right)\right|, \quad y=|B’\cap I_2|. $$ Then, by AM—GM, $$ |B’\cap A_1’|\leq x, \quad \prod_{j=2}^3 |B’\cap A_j|\leq (x/2+2-x-y)^2, \quad \prod_{j=4}^6 |B’\cap A_j|\leq (x/3+y)^3, $$ and the equalities are achievable simultaneously. Hence, in the optimal case, we have $$ \prod_{j=1}^6|B’\cap A_j|=x(2-x/2-y)^2(x/3+y)^3 =\frac{6x\cdot (36-9x-18y)^2\cdot (4x+12y)^3}{6\cdot 18^2\cdot 12^3}. $$

So we seek for a maximizer $(x_0,y_0)$ of $$ f(x,y)= 6x\cdot (36-9x-18y)^2\cdot (4x+12y)^3 $$ under the conditions $x.y\geq 0$, $x+y\leq 2$. We claim that such a maximizer has $x_0\geq 24/17$, which provides $|B’\cap A_1’|>|B\cap A_1|=1$, as desired.

Indeed, we have $$ f\left(\frac{24}{17},\frac{10}{17}\right) =\frac{144}{17}\cdot \left(\frac{216}{17}\right)^5. $$ On the other hand, if $x\leq 24/17$, by AM—GM we have $$ f(x,y)\leq 6x\cdot\left(\frac{2(36-9x-18y)+3(4x+12y)}5\right)^5 =6x\cdot\left(\frac{72-6x}5\right)^5; $$ the right hand part is an increasing function for $0\leq x\leq 2$, so $$ f(x,y)\leq 6\cdot \frac{24}{17}\cdot\left(\frac{72-6\cdot 24/17}5\right)^5 = f\left(\frac{24}{17},\frac{10}{17}\right), $$ as desired.

Answer 2

$\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_1^{\om_1}\cap\cdots\cap A_n^{\om_n}$ for $A=(A_1,\dots A_n)$ with $A_i\subseteq J$ for all $i\in[n]$, where $J$ is the segment in question; and, for $C\subseteq J$ and $\de\in\{0,1\}$, we let $C^\de:=C$ if $\de=1$ and $C^\de:=J\setminus C$ 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!

Answer 3

Great question, I also have a formulation, plus some observations.
Given a matrix $M$, find the vector $x$ such that $x\le \ell_i$ and $x\cdot1=c$ and $x$ maximizes $\Pi_i (M\cdot x)_i$.
Here each $x_i$ denotes the part of $B$ that falls in the intersection of some given $A$'s.
Equivalently, we could try to maximize $\Sigma_i \log (M\cdot x)_i$.
From Jensen's inequality, any two solutions $x$ give the same maximum.
Moreover, each $(M\cdot x)_i$ needs to be the same as well.