Return to Answer

Thus, there are at most two $(y<x)$- and/or $(y>x)$-runs, and, by the above consideration of any two adjacent $(y<x)$- and $(y>x)$-runs, the function $x$ is a constant (say $a\ge0$), whereas $y$ takes at most two values $b_1,b_2$ such that $0\le b_1\le b_2$. If $b_1=b_2=b$, then the maximum of $\|x-y\|$ over $(x,y)\in Z$ is $c:=S\vee T$, attained when one of the functions $x,y$ is the constant $c$ while the other one is $0$.

Thus, there are at most two $(y<x)$- and/or $(y>x)$-runs, and, by the above consideration of any two adjacent $(y<x)$- and $(y>x)$-runs, wlog the function $x$ is a constant (say $a\ge0$), whereas $y$ takes at most two values $b_1,b_2$ such that $0\le b_1\le b_2$. If $b_1=b_2=b$, then the maximum of $\|x-y\|$ over $(x,y)\in Z$ is $c:=S\vee T$, attained when one of the functions $x,y$ is the constant $c$ while the other one is $0$.

Proof. By compactness and continuity, the maximum is attained. In the sequel, let $(x,y)$ be a point of attainment of this maximum. If $x_i=y_i$ for some $i\in[n]$, then we can remove this $i$, re-enumerate the coordinates of $x$ and $y$, and use induction on $n$. So, without loss of generality (wlog) $x_i\ne y_i$ for all $i$, and hence $n_-+n_+=n$.

Let us say that a subset $J$ of the set $[n]$ is connected if it is the intersection of $[n]$ with an interval. An $x$-run is a maximal connected nonempty set of constancy of the function $x\colon i\mapsto x_i$. An $(y<x)$-run is a maximal connected nonempty subset $J$ of $[n]$ such that $y_i<x_i$ for all $i\in J$. Similarly defined are the $y$-runs and $(y>x)$-runs. Replacing the $x$- and $y$-values in each $(y<x)$-run and in each $(y>x)$-run by the corresponding arithmetic means, wlog we have that $x$ and $y$ are constant in each such run; that each such run is contained in an $x$-run and in a $y$-run; this condition will be assumed in the rest of this proof.

Thus, there are at most two $(y<x)$- and/or $(y>x)$-runs, and, by the above consideration of any two adjacent $(y<x)$- and $(y>x)$-runs, the function $x$ is a constant (say $a\ge0$), whereas $y$ takes two values $b_1,b_2$ such that $0\le b_1\le b_2$. If $b_1=b_2=b$, then the maximum of $\|x-y\|$ over $(x,y)\in Z$ is $c:=S\vee T$, attained when one of the functions $x,y$ is the constant $c$ while the other one is $0$.

Proof. By compactness and continuity, the maximum is attained. In the sequel, let $(x,y)$ be a point of attainment of this maximum. If $x_i=y_i$ for some $i\in[n]$, then we can remove this $i$, re-enumerate the coordinates of $x$ and $y$, and use induction on $n$. So, without loss of generality (wlog) $x_i\ne y_i$ for all $i$.

Let us say that a subset $J$ of the set $[n]$ is connected if it is the intersection of $[n]$ with an interval. An $x$-run is a maximal connected nonempty set of constancy of the function $x\colon i\mapsto x_i$. An $(y<x)$-run is a maximal connected nonempty subset $J$ of $[n]$ such that $y_i<x_i$ for all $i\in J$. Similarly defined are the $y$-runs and $(y>x)$-runs. Replacing the $x$- and $y$-values in each $(y<x)$-run and in each $(y>x)$-run by the corresponding arithmetic means, wlog we have that $x$ and $y$ are constant in each such run; that is, each such run is contained in an $x$-run and in a $y$-run; this condition will be assumed in the rest of this proof.

Thus, there are at most two $(y<x)$- and/or $(y>x)$-runs, and, by the above consideration of any two adjacent $(y<x)$- and $(y>x)$-runs, the function $x$ is a constant (say $a\ge0$), whereas $y$ takes at most two values $b_1,b_2$ such that $0\le b_1\le b_2$. If $b_1=b_2=b$, then the maximum of $\|x-y\|$ over $(x,y)\in Z$ is $c:=S\vee T$, attained when one of the functions $x,y$ is the constant $c$ while the other one is $0$.

Let $x:=(x_1,\dots,x_n)$ and $y:=(y_1,\dots,y_n)$; we identify $x$ and $y$ with the corresponding functions on the set $[n]:=\{1,\dots,n\}$. Take any real $S,T\ge0$ and nonnegative integers $n_-$ and $n_+$ such that $n_-+n_+\le n$. Let $Z=Z(n,n_-,n_+,S,T)$ denote the set of all pairs $(x,y)\in[0,\infty)^n\times[0,\infty)^n$ such that $x_1\le\dots\le x_n$, $y_1\le\dots\le y_n$, $x_1+\dots+x_n\le S$, $y_1+\dots+y_n\le T$, the cardinality of the set $\{i\in[n]\colon y_i<x_i\}$ is $n_-$, and the cardinality of the set $\{i\in[n]\colon y_i>x_i\}$ is $n_+$.

Consider any two adjacent $(y<x)$- and $(y>x)$-runs. Wlog, we have here an $(y<x)$-run $K_1$ followed (to the right of $K_1$) by a $(y>x)$-run $K_2$, of cardinalities $k_1$ and $k_2$, respectively (resp.). For each $j=1,2$, let $a_j$ and $b_j$ be the constant values of $x$ and $y$, resp., in the run $K_j$, so that $b_1<a_1\le a_2<b_2$. To obtain a contradiction, suppose that, moreover, $a_1<a_2$. Let us change/vary $a_1,a_2,b_1,b_2$ by small amounts $da_1,da_2,db_1,db_2$, resp., such that $k_1 da_1+k_2 da_2=0$ and $k_1 db_1+k_2 db_2=0$, so that the sums $x_1+\dots+x_n$ and $y_1+\dots+y_n$ are unchanged. Then the change $d\|x-y\|$ of $\|x-y\|$ will be the same as the change of $k_1(a_1-b_1)+k_2(b_2-a_2)$, which is $k_1(da_1-db_1)+k_2(db_2-da_2)=2k_2(db_2-da_2)$. If we now take any small enough (in absolute value) $da_2,db_2$ such that $da_2<db_2<0$ (and choose $da_1$ and $db_1$ so as to satisfy the conditions $k_1 da_1+k_2 da_2=0$ and $k_1 db_1+k_2 db_2=0$), then the resulting pair $(x+dx,y+dy)$ will satisfy the condition $b_1<a_1<a_2<b_2$ and will still be in the set $Z$ (in particular, we will have $db_1>0$ and hence $b_1+db_1>0$). But then $d\|x-y\|=2k_2(db_2-da_2)>0$, which is the desired contradiction. Thus, $b_1<a_1=a_2<b_2$, that is, wlog at least one of the functions $x,y$ is constant on any two adjacent $(y<x)$- and $(y>x)$-runs.

Suppose now that there are at least three $(y<x)$- and/or $(y>x)$-runs. Then wlog there are three adjacent runs $K_1,K_2,K_3$, of which $K_1$ is the leftmost one and $K_3$ is the rightmost one, and, moreover, $K_1$ and $K_3$ are $(y<x)$-runs, whereas $K_2$ is a $(y>x)$-run. For each $j=1,2,3$, let $a_j$ and $b_j$ be the constant values of $x$ and $y$, resp., in the run $K_j$ and let $k_j$ be the cardinality of $K_j$, so that, in view of the above consideration of any two adjacent $(y<x)$- and $(y>x)$-runs, we have here $B_1:=b_1<A_1:=a_1=a_2<B_2:=b_2=b_3<A_2:=a_3$. Let us change/vary $A_1,A_2,B_1,B_2$ by small amounts $dA_1,dA_2,dB_1,dB_2$, resp., such that $(k_1+k_2) dA_1+k_3 dA_2=0$ and $k_1 dB_1+(k_2+k_3) dB_2=0$, so that the sums $x_1+\dots+x_n$ and $y_1+\dots+y_n$ are unchanged. Then the change $d\|x-y\|$ of $\|x-y\|$ will be the same as the change of $k_1(A_1-B_1)+k_2(B_2-A_1)+k_3(A_2-B_2)$, which is $k_1(dA_1-dB_1)+k_2(dB_2-dA_1)+k_3(dA_2-dB_2)=2k_2(dB_2-dA_1)$. If we now take any small enough (in absolute value) $dA_1,dB_2$ such that $dA_1<dB_2<0$ (and choose $dA_2$ and $dB_1$ so as to satisfy the conditions $(k_1+k_2) dA_1+k_2 dA_2=0$ and $k_1 dB_1+(k_2+k_3) dB_2=0$), then the resulting pair $(x+dx,y+dy)$ will satisfy the condition $B_1<A_1<B_2<A_2$ and will still be in the set $Z$ (in particular, we will have $dB_1>0$ and hence $B_1+dB_1>0$). But then $d\|x-y\|=2k_2(dB_2-dA_1)>0$, which is the desired contradiction.

Let $x:=(x_1,\dots,x_n)$ and $y:=(y_1,\dots,y_n)$; we identify $x$ and $y$ with the corresponding functions on the set $[n]:=\{1,\dots,n\}$. Take any real $S,T\ge0$ and nonnegative integers $n_-$ and $n_+$ such that $n_-+n_+\le n$. Let $Z=Z(n,n_-,n_+,S,T)$ denote the set of all pairs $(x,y)\in[0,\infty)^n\times[0,\infty)^n$ such that $x_1\le\dots\le x_n$, $y_1\le\dots\le y_n$, $x_1+\dots+x_n\le S$, $y_1+\dots+y_n\le T$, the cardinality of the set $\{i\in[n]\colon y_i\le x_i\}$ is $\ge n_-$, and the cardinality of the set $\{i\in[n]\colon y_i\ge x_i\}$ is $\ge n_+$.

Consider any two adjacent $(y<x)$- and $(y>x)$-runs. Wlog, we have here an $(y<x)$-run $K_1$ followed (to the right of $K_1$) by a $(y>x)$-run $K_2$, of cardinalities $k_1$ and $k_2$, respectively (resp.). For each $j=1,2$, let $a_j$ and $b_j$ be the constant values of $x$ and $y$, resp., in the run $K_j$, so that $b_1<a_1\le a_2<b_2$. To obtain a contradiction, suppose that, moreover, $a_1<a_2$. Let us change/vary $a_1,a_2,b_1,b_2$ by small amounts $da_1,da_2,db_1,db_2$, resp., such that $k_1 da_1+k_2 da_2=0$ and $k_1 db_1+k_2 db_2=0$, so that the sums $x_1+\dots+x_n$ and $y_1+\dots+y_n$ are unchanged. Then the change $d\|x-y\|$ of $\|x-y\|$ will be the same as the change of $k_1(a_1-b_1)+k_2(b_2-a_2)$, which is $k_1(da_1-db_1)+k_2(db_2-da_2)=2k_2(db_2-da_2)$. If we now take any small enough (in absolute value) $da_2,db_2$ such that $da_2<db_2<0$ (and choose $da_1$ and $db_1$ so as to satisfy the conditions $k_1 da_1+k_2 da_2=0$ and $k_1 db_1+k_2 db_2=0$), then the resulting pair $(x+dx,y+dy)$ will satisfy the condition $b_1+db_1<a_1+da_1<a_2+da_2<b_2+db_2$ and will still be in the set $Z$ (in particular, we will have $db_1>0$ and hence $b_1+db_1>0$). But then $d\|x-y\|=2k_2(db_2-da_2)>0$, which is the desired contradiction. Thus, $b_1<a_1=a_2<b_2$, that is, wlog at least one of the functions $x,y$ is constant on any two adjacent $(y<x)$- and $(y>x)$-runs.

Suppose now that there are at least three $(y<x)$- and/or $(y>x)$-runs. Then wlog there are three adjacent runs $K_1,K_2,K_3$, of which $K_1$ is the leftmost one and $K_3$ is the rightmost one, and, moreover, $K_1$ and $K_3$ are $(y<x)$-runs, whereas $K_2$ is a $(y>x)$-run. For each $j=1,2,3$, let $a_j$ and $b_j$ be the constant values of $x$ and $y$, resp., in the run $K_j$ and let $k_j$ be the cardinality of $K_j$, so that, in view of the above consideration of any two adjacent $(y<x)$- and $(y>x)$-runs, we have here $B_1:=b_1<A_1:=a_1=a_2<B_2:=b_2=b_3<A_2:=a_3$. Let us change/vary $A_1,A_2,B_1,B_2$ by small amounts $dA_1,dA_2,dB_1,dB_2$, resp., such that $(k_1+k_2) dA_1+k_3 dA_2=0$ and $k_1 dB_1+(k_2+k_3) dB_2=0$, so that the sums $x_1+\dots+x_n$ and $y_1+\dots+y_n$ are unchanged. Then the change $d\|x-y\|$ of $\|x-y\|$ will be the same as the change of $k_1(A_1-B_1)+k_2(B_2-A_1)+k_3(A_2-B_2)$, which is $k_1(dA_1-dB_1)+k_2(dB_2-dA_1)+k_3(dA_2-dB_2)=2k_2(dB_2-dA_1)$. If we now take any small enough (in absolute value) $dA_1,dB_2$ such that $dA_1<dB_2<0$ (and choose $dA_2$ and $dB_1$ so as to satisfy the conditions $(k_1+k_2) dA_1+k_2 dA_2=0$ and $k_1 dB_1+(k_2+k_3) dB_2=0$), then the resulting pair $(x+dx,y+dy)$ will satisfy the condition $B_1+dB_1<A_1+dA_1<B_2+dB_2<A_2+dA_2$ and will still be in the set $Z$ (in particular, we will have $dB_1>0$ and hence $B_1+dB_1>0$). But then $d\|x-y\|=2k_2(dB_2-dA_1)>0$, which is the desired contradiction.