Combinatorial inequality for n-tuples with sum 1

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Combinatorial inequality for n-tuples with sum 1

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: 2nd Memorial Mathematical Competition "Aleksandar Blazhevski - Cane" - Problem 3

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

351 posts

#1 h Jan 12, 2021, 9:03 PM • 1 Y

Y by superagh

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

293 posts

#2 h Jan 13, 2021, 7:51 AM • 2 Y

Y by steppewolf, Mango247

mk and Mk

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Mathematicsislovely

245 posts

Mathematicsislovely

#3 h Apr 25, 2021, 1:49 PM • 3 Y

Y by amar_04, steppewolf, Mango247

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$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a