Reduzindo subconjunto e produto

Question

Dado um segmento e um valor $c$ menor que o comprimento do segmento, deixe $A_1,\dots,A_n$ser uniões finitas de intervalos no segmento. Nós escolhemos uma união finita de intervalos$B$ com $|B|=c$ que maximiza $|B\cap A_1|\times\dots\times |B\cap A_n|$, Onde $|\cdot|$denota o comprimento (ou seja, medida de Lebesgue). Se houver muitos assim$B$, escolhemos um arbitrariamente.

Agora, nós encolhemos $A_1$ para $A_1'\subseteq A_1$e escolha $B'$usando o mesmo procedimento. É sempre verdade que$|B'\cap A_1'|\le |B\cap A_1|$?

E se $A_1,\dots,A_n$são uniões finitas disjuntas , a resposta é positiva, como mostrado aqui .

Answer 1

OK, parece que este é um contra-exemplo.

Pegue 8 segmentos disjuntos $I_1,\dots,I_8$ de comprimento 1. Pegue 8 conjuntos $$ S_1=\{1,2,3\}, \quad S_1=\{4,5,6\}, \quad S_1=\{1,2,4\}, \quad S_1=\{1,2,5\}, \quad S_1=\{1,2,6\}, \quad S_1=\{1,3,4\}, \quad S_1=\{1,3,5\}, \quad S_1=\{1,3,6\}. $$ Diz isso $I_i$ encontra-se em $A_j$ sse $j\in S_i$, de outra forma $I_i$ e $A_j$são disjuntos. Finalmente, defina$c=2$.

Nesta situação, o ótimo $B$ é $I_1\cup I_2$. onde o produto é igual$1$. Isso decorre do fato de que$\sum_j |B\cap A_j|\leq 6$, uma vez que qualquer ponto é coberto por no máximo três dos $A_j$.

Agora definido $A_1’=A_1\setminus I_1$. Considere as quantidades$$ x=\left|B’\cap\left(\bigcup_{i=3}^8 I_i\right)\right|, \quad y=|B’\cap I_2|. $$ Então, por 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, $$e as igualdades são alcançáveis ​​simultaneamente. Portanto, no caso ideal, temos$$ \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}. $$

Então, buscamos um maximizador $(x_0,y_0)$ do $$ f(x,y)= 6x\cdot (36-9x-18y)^2\cdot (4x+12y)^3 $$ sob as condições $x.y\geq 0$, $x+y\leq 2$. Afirmamos que tal maximizador tem$x_0\geq 24/17$, que provê $|B’\cap A_1’|>|B\cap A_1|=1$, como desejado.

Na verdade, nós temos $$ f\left(\frac{24}{17},\frac{10}{17}\right) =\frac{144}{17}\cdot \left(\frac{216}{17}\right)^5. $$ Por outro lado, se $x\leq 24/17$, por AM — GM temos $$ 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; $$ a parte direita é uma função crescente para $0\leq x\leq 2$, então $$ 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), $$ como desejado.

Answer 2

$\newcommand\om\omega\newcommand\Om\Omega\newcommand\de\delta$Como na resposta vinculada, esse problema nos conjuntos pode ser reformulado como o seguinte problema nos números reais.

Deixei $\Om:=\{0,1\}^n$. Para cada$\om\in\Om$ e cada $i\in[n]:=\{1,\dots,n\}$, deixei $\om_i$ denotar o $i$ª coordenada do vetor $\om$, de modo que $\om=(\om_1,\dots,\om_n)$.

Para qualquer $a=(a^\om)\in[0,\infty)^\Om$ e qualquer $c\in[0,\sum_{\om\in\Om} a^\om]$, deixei $$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\}.$$

Deixei $b(a)=b_c(a)$ seja qualquer maximizador de $$\pi(b):=\prod_{i=1}^n\sum_{\om\in\Om\colon\,\om_i=1}b^\om$$ No geral $b\in B(a)$.

Pegue agora qualquer $u=(u^\om)\in[0,\infty)^\Om$ de tal modo que $u^\om\le a^\om$ para todos $\om\in\Om$ com $\om_1=1$ e $u^\om=a^\om$ para todos $\om\in\Om$ com $\om_1=0$. Deixei$b(u)=b_c(u)$ seja qualquer maximizador de $\pi(b)$ No geral $b\in B(u)$. Isso segue necessariamente que$$\sum_{\om\in\Om\colon\,\om_i=1}b(u)^\om\le\sum_{\om\in\Om\colon\,\om_i=1}b(a)^\om?$$

Nesta reafirmação, para todos $\om\in\Om$

• $a^\om$ apoia $|A^\om|$, Onde $A^\om:=A_1^{\om_1}\cap\cdots\cap A_n^{\om_n}$ para $A=(A_1,\dots A_n)$ com $A_i\subseteq J$ para todos $i\in[n]$, Onde $J$é o segmento em questão; e para$C\subseteq J$ e $\de\in\{0,1\}$, Nós deixamos $C^\de:=C$ E se $\de=1$ e $C^\de:=J\setminus C$ E se $\de=0$;
• $b^\om$ apoia $|B\cap A^\om|$.

Vemos que mesmo o problema reformulado, em termos de números reais, diz respeito à maximização da função não convexa / não côncava. $\pi(\cdot)$ sobre um politopo de dimensão $2^n-1$, definido por $2^{n+1}$desigualdades afins. Além disso, precisamos comparar as soluções de dois desses problemas. Isso parece difícil! Se alguém puder responder a esta pergunta, pode ser um momento bastante instrutivo!

Answer 3

Ótima pergunta, também tenho uma formulação, além de algumas observações.
Dada uma matriz$M$, encontre o vetor $x$ de tal modo que $x\le \ell_i$ e $x\cdot1=c$ e $x$ maximiza $\Pi_i (M\cdot x)_i$.
Aqui cada$x_i$ denota a parte de $B$ que cai na intersecção de algum dado $A$'s.
Da mesma forma, podemos tentar maximizar$\Sigma_i \log (M\cdot x)_i$.
Da desigualdade de Jensen, quaisquer duas soluções$x$dê o mesmo máximo.
Além disso, cada$(M\cdot x)_i$ precisa ser o mesmo também.