For a given $n,k$ and the sequence $<a_i>_{i=1}^{n} \in (k-1,k)$, find the least number of sequence $<x_i>_{i=1}^{n}$ satisfying this condition: For an arbitrary set $I\subseteq\{1,2,\cdot\cdot\cdot , n \}, |I|=k$, there exists $\sum_{i \in I} x_i \leq \sum_{i \in I} a_i$. Find the maximum of the number of sequence btw I think the date of the contest is wrong... this year is 2017

And I'm not sure whether the "maximum" means number of sequence or their actual values...

Let $n > k$ be two natural numbers and let $a_1,\ldots,a_n$ be real numbers in the open interval $(k-1,k)$. Let $x_1,\ldots,x_n$ be positive reals such that for any subset $I \subset \{1,\ldots,n \}$ satisfying $|I| = k$, one has $$\sum_{i \in I} x_i \leq \sum_{i \in I} a_i.$$Find the largest possible value of $x_1 x_2 \cdots x_n$.

fattypiggy123 wrote: Let $n > k$ be two natural numbers and let $a_1,\ldots,a_n$ be real numbers in the open interval $(k-1,k)$. Let $x_1,\ldots,x_n$ be positive reals such that for any subset $I \subset \{1,\ldots,n \}$ satisfying $|I| = k$, one has $$\sum_{i \in I} x_i \leq \sum_{i \in I} a_i.$$Find the largest possible value of $x_1 x_2 \cdots x_n$. Ah that phrase meant multiple?! I didn't know that

Actually it doesn't --- Sqing's version seems to be wrong. As for the year issue, the olympiad used to be held in January and then it was pushed earlier to Novemeber/December. So to keep the year consistent, we call this the 2018 olympiad although it is held in 2017.

fattypiggy123 wrote: Actually it doesn't --- Sqing's version seems to be wrong. Thanks.

Skravin wrote:

btw I think the date of the contest is wrong... this year is 2017 China National Olympiad 2017

fattypiggy123 wrote: Actually it doesn't --- Sqing's version seems to be wrong. As for the year issue, the olympiad used to be held in January and then it was pushed earlier to Novemeber/December. So to keep the year consistent, we call this the 2018 olympiad although it is held in 2017. ahh

sqing wrote: Given the positive integer $n ,k$ $(n>k)$ and $ a_1,a_2,\cdots ,a_n\in (k-1,k)$ ,if positive number $x_1,x_2,\cdots ,x_n$ satisfying:For any set $\mathbb{I} \subseteq \{1,2,\cdots,n\}$ ,$|\mathbb{I} |=k$,have $\sum_{i\in \mathbb{I} }x_i\le \sum_{i\in \mathbb{I} }a_i$ , find the maximum value of $x_1x_2\cdots x_n.$

Can someone pls provide English solution? I don't know Chinese .

vsathiam wrote: Can someone pls provide English solution? I don't know Chinese . Translation with a bit more explanation: When $k = 1$ the result is obvious. Suppose $k > 1$. Write $a_i = x_i + b_i$ and WLOG $b_1 \le b_2 \le ... \le b_l < 0 \le b_{l+1} \le ... \le b_n, c_1 = - b_1, c_2 = -b_2,...,c_l = -b_l$. If $l = 0$ then we are done. Suppose $l \ge 1$. Next we prove that $\prod x_i \le \prod a_i$, i.e. $\prod (a_i - b_i) \le \prod a_i$. $$\prod (a_i - b_i) = \prod_{i=1}^l (a_i + c_i) \prod_{i=l+1}^n (a_i - b_i) \le \prod a_i$$$$\iff \prod (1+\frac{c_i}{a_i}) \prod (1-\frac{b_i}{a_i}) \le 1.$$The given condition $\sum x_i \le \sum a_i \forall \mathbb I$ essentially is equivalent to $$b_1 + ... + b_k \ge 0 \qquad \qquad (*)$$The above implies $k \ge l+1$. So it suffices to show that when $(*)$ holds, $$\prod (1+\frac{c_i}{k-1}) \prod (1-\frac{b_i}{k}) \le 1.$$Set $b_{l+1} + ... + b_k = t (\ge \sum_{i=1}^l c_i)$. For the finish: by spamming Jensen on $\ln(1+x)$/AM-GM on the products repeatedly we have \begin{align*} \text{LHS} &\le (1+\frac{t}{l(k-1)})^l(\prod_{i=l+1}^k(1-\frac{b_i}k))(1-\frac{b_k}k)\\ & \le (1+\frac{t}{l(k-1)})^l\prod_{i=l+1}^{k+1}(1-\frac{t}{(k-l)k})\\ & = (1+\frac{t}{l(k-1)})^l(1-\frac{t}{(k-l)k})^{k+1-l}\\ & \le \left(1+ \frac t{k+1} \cdot \left(\frac 1 {k-1} - \frac{k+1-l}{(k-l)k}\right)\right)^{k+1} \le 1\\ \end{align*}so we are done.

The answer is $a_1...a_n$. We proceed by induction on $n,k$. The case $n=2$ and $k=1$ is obvious. Now suppose all smaller case holds. Now define $t_i=x_i-a_i$ for each $1\leq i\leq n$. If $t_i=0$ for some $i$ then we are done. WLOG assume $t_1\geq t_2\geq...\geq t_m> 0> t_{m+1}\geq...\geq t_n$, then $$\sum_{i\in I}t_i\leq 0 \hspace{20pt}(1)$$for all $|I|=k$. We first show a lemma. Lemma. Let $P$ be a polynomial of degree $n$ with $1$ negative root and $n-1$ positive roots, say $y_1<0<y_2\leq...\leq y_{n}$. Suppose $f(0)>0$ and $f'(0)<0$, then $f'(x)<0$ in the whole interval $x\in [0,y_2]$ Proof. Notice that by Rolle's theorem there is a root of $f'(x)$ in each of the intervals $[y_i,y_{i+1}]$. Since $f'(x)$ has at most $n-1$ roots we conclude that it has exactly one root in the interval $[y_1,y_2]$. Since $f(0)>0$ we conclude that $f(x)>0$ in the interval $x\in[y_1,y_2]$. Therefore, $f'(x)<0$ in some left-neighborhood of $y=x_2$. Since $f'$ only changes sign once in the interval $[y_1,y_2]$ we conclude thaat $f'(x)<0$ in the whole interval $x\in [0,y_2]$ Now we divide into two cases: Case I: $t_m\leq (k-1)$. Define $b_i=a_i-\frac{t_m}{k-1}$. Then by normalization we may assume $b_i\in (k-2,k-1)$ and $$\sum_{j\in I}b_i\geq \sum_{j\in I}x_i$$where $|I|=k-1$ and $I\subset\{1,2,...,n\}\setminus\{m\}$. Therefore, by inductive hypothesis we have $$\prod_{i\neq m}x_i\leq \prod_{i\neq m}b_i=\prod_{i\neq m}(a_i-\frac{t_m}{k-1})$$Therefore, denoting $t_m$ by $t$, $$\prod_{i=1}^na_i\leq (a_m+t)\prod_{i\neq m}(a_i-\frac{t}{k-1})$$Denote this polynomial in $t$ by $f(t)$. Notice that $$f(0)=a_1...a_n>0$$$$f'(0)=a_1a_2...a_n\left(-\frac{1}{k-1}\sum_{i\neq m}\frac{1}{a_i}+\frac{1}{a_1}\right)<a_1a_2...a_n\left(-\frac{n-1}{(k-1)k}+\frac{1}{k-1}\right)=0$$so by the lemma we have $f(t)<f(0)=a_1...a_n$ as desired. Case II: $t_m>k-1$ Therefore, obviously $m<k$, let $p=k-m$. Notice that if we replace $t_1,...,t_m$ by $t_1-p\epsilon,...,t_m-p\epsilon$ and $t_{m+1},...,t_n$ by $t_{m+1}+m\epsilon,...,t_n+m\epsilon$ where $t_m-p\epsilon\geq 0\geq t_n+m\epsilon$ then $(1)$ still holds. We call this an $\epsilon$-operation. Now suppose after carrying out an $\epsilon_1$-operation, $t_m$ becomes $k-1$ and that after carrying out an $\epsilon_2$-operation, $t_{m+1}$ becomes $1$. Denote $\epsilon=\min\{\epsilon_1,\epsilon_2\}$. Suppose after carrying out an $\epsilon$-operation, $t_1,t_2,...,t_n$ becomes $s_1,s_2,...,s_n$. Define the polynomial $f$ by $$f(t)=(a_1+s_1+pt)(a_2+s_2+pt)...(a_m+s_m+pt)(a_{m+1}+s_{m+1}-mt)...(a_n+s_n-mt)$$Again notice that $$f(0)=(a_1+s_1)...(a_1+s_n)>0$$$$f'(0)=(a_1+s_1)(a_2+s_2)...(a_n+s_n)\left(p\sum_{i=1}^m\frac{1}{a_i+s_i}-m\sum_{i=m+1}^n\frac{1}{a_i+s_i}\right)<\frac{1}{pm}\left(\frac{1}{a_m+s_m}-\frac{1}{a_{m+1}+s_{m+1}}\right)<0$$Therefore, by the lemma we have $$x_1x_2...x_n=f(\epsilon)<f(0)$$and $f(0)\leq a_1...a_n$ by Case I so we are done.