For any given integers $m,n$ such that $2\leq m<n$ and $(m,n)=1$. Determine the smallest positive integer $k$ satisfying the following condition: for any $m$-element subset $I$ of $\{1,2,\cdots,n\}$ if $\sum_{i\in I}i> k$, then there exists a sequence of $n$ real numbers $a_1\leq a_2 \leq \cdots \leq a_n$ such that $$\frac1m\sum_{i\in I} a_i>\frac1n\sum_{i=1}^na_i$$
Problem
Source: CWMI 2016 P8
Tags: algebra, inequalities, number theory
20.08.2016 22:31
It quite straightforward. Note that $a_1,a_2,...,a_n$ satisfy all conditions if and only if $(a_1,a_2,....,a_n)=(a_1+w,a_2+w,...,a_n+w)$ satisfy all conditions. So, we can assume that $a_1=0$. Moreover, for any set $I=\{ i_1,i_2,...,i_m\}$ be the $m$-element subset of $\{ 1,2,...,n\}$ that satisfy the condition where $i_1<i_2<...<i_m$, we get that for each $a_1,a_2,...,a_n$ satisfy $\frac1m\sum_{i\in I} a_i>\frac1n\sum_{i=1}^na_i$ with $a_1\leq a_2 \leq \cdots \leq a_n$ then $(a_1,a_2,...,a_n)=(0,0,...,0,a_{i_1},a_{i_1},....,a_{i_1},a_{i_2},a_{i_2},...,a_{i_2},....,a_{i_m},a_{i_m},....,a_{i_m})$ satisfy both conditions. We get that $$\frac{a_{i_1}+a_{i_2}+....+a_{i_m}}{m} \geq \frac{\Big( \sum_{j=1}^{m-1}{a_{i_j}(i_{j+1}-i_j)}\Big) +a_{i_m}(n-i_m+1)}{n} \iff \Big( \sum_{j=1}^{m-1}{a_{i_j}(n-m(i_{j+1}-i_j)}\Big) +a_{i_m}(n-m(n-i_m+1))\geq 0.$$For each $k=2,3,...,m$, let $t_{i_k}=a_{i_k}-a_{i_{k-1}}>0$. The inequality reduce to $$a_{i_1}(mn-m(n-i_1+1))+\sum_{j=2}^{m}{t_{i_j}((m-(j-1))n-m(n-i_j+1))}\geq 0$$where $t_{i_2},t_{i_3},...,t_{i_m}>0,a_{i_1}\geq 0$. So, there not exist such $a_{i_1},t_{i_1},t_{i_2},...,t_{i_m}$ if and only if $$mn-m(n-i_1+1),(m-(j-1))n-m(n-i_j+1)<0$$for all $j=2,3,...,m$. This mean that if $i_1=1=\Big\lfloor \frac{n(1-1)}{m}+1\Big\rfloor,i_j=\Big\lfloor \frac{n(j-1)}{m}+1\Big\rfloor$ for all $j=2,3,...,m$ then there not exists $a_1,a_2,...,a_n$. So, $k\geq 1+\sum_{j=2}^{m}{\Big\lfloor \frac{n(j-1)}{m}+1\Big\rfloor}$. And for those value of $k$ we get that $\sum_{j=1}^{m}{\Big( i_j-\Big\lfloor \frac{n(j-1)}{m}+1\Big\rfloor\Big)} >0$. This gives there exist $h\in \{ 1,2,...,m\}$ that $i_h>\Big\lfloor \frac{n(h-1)}{m}+1\Big\rfloor$, then choosing $t_{i_h} \rightarrow \infty $ make the inequality holds. Hence, the smallest value of $k$ is $$\sum_{j=1}^{m}{\Big( \Big\lfloor \frac{n(j-1)}{m}+1\Big\rfloor\Big)} =\sum_{j=1}^{m}{\Big( 1+\frac{n(j-1)}{m}\Big)} -\Big( \frac{0}{m}+\frac{1}{m}+....+\frac{m-1}{m}\Big) =\frac{(n-1)(m-1)}{2}+m.$$