Given a positive integer $n \geq 3$, let $C_{n}$ be the collection of all $n$-tuples $a=(a_{1},a_{2},...,a_{n})$ of nonnegative reals $a_i$, $i=1,...,n$, such that $a_{1}+a_{2}+...+a_{n}=1$. For $k \in \left \{ 1,...,n-1 \right \}$ and $a \in C_{n}$, consider the sum set $\sigma_{k}(a) = \left \{a_{1}+...+a_{k},a_{2}+...+a_{k+1},...,a_{n-k+1}+...+a_{n} \right \}$. Show the following. (a) There exist $m_k=\max\{\min\sigma_k(a):a\in\mathcal{C}_n\}$ and $M_k=\min\{\max\sigma_k(a):a\in\mathcal{C}_n\}$. (b) It holds that $\displaystyle{1\leq\sum_{k=1}^{n-1}(\frac{1}{M_k}-\frac{1}{m_k})\leq n-2}$. Moreover, on the left side, equality is attained only for finitely many values of $n$, whereas on the right side, equality holds for infinitely values of $n$.
Problem
Source: 2nd Memorial Mathematical Competition "Aleksandar Blazhevski - Cane" - Problem 3
Tags: combinatorics, inequalities
25.04.2021 16:49
We claim that ,$m_k=\frac{1}{\left\lfloor{\frac{n}{k}}\right\rfloor}$ which can be acheived by taking $a_r=\frac{1}{\left\lfloor{\frac{n}{k}}\right\rfloor}$ for $k|r$ and $r\le n$ and $a_r=0$ for all other $r$. Again we claim that,$M_k=\frac{1}{\left\lceil{\frac{n}{k}}\right\rceil}$ which can be acheived by takink $a_{ck+1}=\frac{1}{\left\lceil{\frac{n}{k}}\right\rceil}$ such that $ck+1\le n$ and $a_r=0$ for all other $a_r$. We will prove the claims by contradiction.WRite $n=kq+r$ for $r<k$.Then $\left\lfloor{\frac{n}{k}}\right\rfloor$ Assume, $m_k>\frac{1}{\left\lfloor{\frac{n}{k}}\right\rfloor}$.Then there is $a\in C_n$ such that any consecutive $k$-sum is greater than $\frac{1}{\left\lfloor{\frac{n}{k}}\right\rfloor}$. In particular, \begin{align*} a_1+a_2+\dots +a_k&>\frac{1}{\left\lfloor{\frac{n}{k}}\right\rfloor}\\ a_{k+1}+a_{k+2}\dots+a_{2k}&>\frac{1}{\left\lfloor{\frac{n}{k}}\right\rfloor}\\ &\phantom\equiv\vdots \\ a_{(q-1)k+1}+\dots a_{qk}> & \frac{1}{\left\lfloor{\frac{n}{k}}\right\rfloor} \end{align*} The sum of the left hand sides is atmost 1,while the sum of the right hand sides is 1.So contradiction. Similarly,Assume that, $M_k<\frac{1}{\left\lceil{\frac{n}{k}}\right\rceil}$.Then,there is a $a\in C_n$ such that any consecutive $k$-sum is less than $\frac{1}{\left\lceil{\frac{n}{k}}\right\rceil}$.In particular we have, \begin{align*} a_1+a_2+\dots +a_k &<\frac{1}{\left\lceil{\frac{n}{k}}\right\rceil}\\ a_{k+1}+\dots +a_{2k}&<\frac{1}{\left\lceil{\frac{n}{k}}\right\rceil}\\ &\phantom\equiv\vdots \\ a_{(q-1)k+1}+\dots a_{qk} &<\frac{1}{\left\lceil{\frac{n}{k}}\right\rceil}\\ a_{n-k+1}+\dots +a_n &<\frac{1}{\left\lceil{\frac{n}{k}}\right\rceil}\\ \end{align*}The sum of the left hand sides are atleast 1,while the sum ofthe right hand sides are 1.Contradiction. For the second part we ned to find $\sum_{k=1}^{n-1}(\frac{1}{M_k}-\frac{1}{m_k})$ Which is equal to $$\sum_{k=0}^n\left\lceil{\frac{n}{k}}\right\rceil -\left\lfloor{\frac{n}{k}}\right\rfloor$$ Now observe that,$\left\lceil{\frac{n}{k}}\right\rceil -\left\lfloor{\frac{n}{k}}\right\rfloor=0$ when $k|n$ and otherwise it is 1. Hence the total sum is $n-d(n)$ where $d(n)$ is the number of divisors of $n$. Finally, $d(n)\ge2$ equality holds for all primes.Hence,Equality in right hand side holds infinitely many times. Also $n-d(n)=1$ only for some values of $n$ since $d(n)\le 2\sqrt n$ .[$d(n)=O(n^{\varepsilon})$]. we are done. $\blacksquare$