Inequality with permutations

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

Inequality with permutations

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: 2019 Belarus Team Selection Test 7.3

The post below has been deleted. Click to close.

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

184 posts

#1 h Sep 2, 2019, 8:38 AM • 4 Y

Y by brokendiamond, Ab_Rin, Adventure10, farhad.fritl

Given a positive integer $n$ , determine the maximal constant $C_n$ satisfying the following condition: for any partition of the set $\{1,2,\ldots,2n \}$ into two $n$ -element subsets $A$ and $B$ , there exist labellings $a_1,a_2,\ldots,a_n$ and $b_1,b_2,\ldots,b_n$ of $A$ and $B$ , respectively, such that
$(a_1-b_1)^2+(a_2-b_2)^2+\ldots+(a_n-b_n)^2\ge C_n.$
(B. Serankou, M. Karpuk)

Z K Y

The post below has been deleted. Click to close.

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

349 posts

#3 h Jan 29, 2020, 8:13 AM • 1 Y

Y by Adventure10

How to solve this problem ???

Z K Y

The post below has been deleted. Click to close.

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

590 posts

XbenX

#5 h Jan 29, 2020, 11:07 AM • 1 Y

Y by Adventure10

We're trying to maximize $C_n=\sum_{i=1}^{n}(a_i-b_i)^2=\sum_{i=1}^{2n}i^2-2\sum_{i=1}^{n}a_ib_i=\frac{2n(2n+1)(4n+1)}{6}-2\sum_{i=1}^{n}a_ib_i$ , so we need to minimize $S:=\sum_{i=1}^{n}a_ib_i$ .

Lemma. The minimum of $S$ is achieved when none of the pairs $(a_i,b_i)$ are both greater than $n$ .

Proof. Assume not, then there are four numbers $i,j,k,l \in \{1,2,3,\dots,n\}$ such that $(n+i)(n+j)+lk$ appears in $S$ , but we can replace these numbers with $(n+i)l+(n+j)k$ and decrease $S$ because $(n+i)(n+j-l)\geq k(n+j-l)$ . $\blacksquare$

So, we can let $A=\{1,2,\dots ,n\}$ and $B=\{n+1,n+2,\dots ,2n\}$ and by rearrangement inequality we get that $S\geq \sum_{i=1}^{n} i(2n+1-i)=\frac{n(n+1)(2n+1)}{3}$ .
Hence, we have $C_n=\frac{2n(2n+1)(4n+1)}{6}-2S\leq \frac{n(2n+1)(2n-1)}{3}$ .

This post has been edited 1 time. Last edited by XbenX, Jan 29, 2020, 1:10 PM

Z K Y

The post below has been deleted. Click to close.

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

8 posts

#6 h Dec 23, 2020, 2:31 PM • 2 Y

Y by Aegaertargaryen1102, YOUsername

I don't quite understand. We have to find the maximum value of the sum for each partition and then the smallest of those, don't we?

Z K Y

The post below has been deleted. Click to close.

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

69 posts

#8 h May 7, 2021, 2:22 PM

Y by

XbenX wrote:

We're trying to maximize $C_n=\sum_{i=1}^{n}(a_i-b_i)^2=\sum_{i=1}^{2n}i^2-2\sum_{i=1}^{n}a_ib_i=\frac{2n(2n+1)(4n+1)}{6}-2\sum_{i=1}^{n}a_ib_i$ , so we need to minimize $S:=\sum_{i=1}^{n}a_ib_i$ .

Lemma. The minimum of $S$ is achieved when none of the pairs $(a_i,b_i)$ are both greater than $n$ .

Proof. Assume not, then there are four numbers $i,j,k,l \in \{1,2,3,\dots,n\}$ such that $(n+i)(n+j)+lk$ appears in $S$ , but we can replace these numbers with $(n+i)l+(n+j)k$ and decrease $S$ because $(n+i)(n+j-l)\geq k(n+j-l)$ . $\blacksquare$

So, we can let $A=\{1,2,\dots ,n\}$ and $B=\{n+1,n+2,\dots ,2n\}$ and by rearrangement inequality we get that $S\geq \sum_{i=1}^{n} i(2n+1-i)=\frac{n(n+1)(2n+1)}{3}$ .
Hence, we have $C_n=\frac{2n(2n+1)(4n+1)}{6}-2S\leq \frac{n(2n+1)(2n-1)}{3}$ .

Oh，you did it in a wrong place ，you need to find where S max is，not the miniment。But your method is right ，and i think the ture result is n。

This post has been edited 1 time. Last edited by indulged, May 7, 2021, 2:22 PM

Z K Y

The post below has been deleted. Click to close.

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

769 posts

#9 h Jun 24, 2023, 7:11 AM

Y by

$n$ is even: $\frac{13n^{3}-4n}{12}$
$n$ is odd: $\frac{13n^{3}-n}{12}$

This post has been edited 1 time. Last edited by Takeya.O, Jun 24, 2023, 7:12 AM
Reason: error

Z K Y

The post below has been deleted. Click to close.

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

769 posts

#10 h Jul 16, 2023, 6:13 AM

Y by

I don't know the time when the sum is minimized.

Z K Y

The post below has been deleted. Click to close.

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

40 posts

#11 h Jul 19, 2023, 7:28 AM

Y by

use karamata ineq.

Z K Y

The post below has been deleted. Click to close.

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

40 posts

#12 h Jul 23, 2023, 1:40 AM

Y by

Consruction:
if n=2k+1,take A={1,2,...,k,3k+2,...,4k+2} and B={k+1,...,3k+1}
if n=2k,take A={1,...,k,3k+1,...,4k} and B={k+1,...,3k}
Proof:
let c(k)=|a(k)-b(k)|，rearrange c(k) as d1≥d2≥...≥dn
if n=2k+1,we can prove that {dk}＞{3k+1,3k,...,k+1}
if n=2k,we have {dk}＞{3k-1,3k-1,3k-3,3k-3,...,k+1,k+1} (nontrivial but not hard)

Z K Y

The post below has been deleted. Click to close.

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

526 posts

#13 h Dec 14, 2024, 2:40 AM

Y by

I don't know why there isn't any full solution for this great problem! Nice and elegant integer inequality from 2019 RMMSL. XD

Let $s_i = a_i + b_i$ . Since $\sum{a_i^2} + \sum{b_i^2}$ is constant, we only need to find the maximum value of $\sum_{i = 1}^{n} a_ib_i$ where $A$ and $B$ are partitions of $[2n]$ , and $|A| = |B| = n$ . This is simply maximizing $\sum_{i = 1}^{n} s_i^2$ .

We claim that $|s_i - s_j| \le n$ for any $i < j$ both in the set $\{ 1, 2, \cdots, n\}$ . This is because $|s_i - s_j| = |a_i - a_j + b_i - b_j|$ . As $a_i \ge a_1 + i - 1$ and $a_j \le a_n - n + j$ , we have $a_i - a_j \ge a_1 - a_n + (n-1) + (i - j)$ . Also, $b_i - b_j \ge j - i$ . Therefore, we have that $|s_i - s_j| \le n$ . Now, we forget about our original definition of $s_i$ , and just focus on the fact that $s_i$ are integers that satisfies $|s_i - s_j| \le n$ with $\sum_{i = 1}^{n} s_i = n(2n+1)$ . As $|s_i - s_j| \le n$ , we can set an integer $t$ so that $s_i \in [t, t+n]$ for any $i$ . As the function $x \mapsto x^2$ is convex, we can force for some $s_i < s_j$ , changing $(s_i, s_j)$ into $(s_i - 1, s_j + 1)$ makes the value $\sum_{i = 1}^{n} s_i^2$ larger. If there are two $i, j$ such that $a < s_i < s_j < a+n$ , then we can force $s_i = a$ or $s_j = a+n$ so that the sum gets larger. Hence, we can see that only one value can lie in the interval $(t, t+n)$ . The remaining job is just tedious calculation, which I will omit. :pilot:

:pilot:

Now, we proved that (I actually did the calculation) $\sum s_i^2$ is maximized when the sequence of $s_i$ consists of $\lfloor n/2 \rfloor$ number of $\left \lfloor \dfrac{3n}{2} \right \rfloor$ and $\lceil n/2 \rceil$ number of $\left \lceil \dfrac{5n}{2} \right \rceil$ . Then, we can easily construct $A$ and $B$ so that $s_i$ becomes the prementioned sequence. Hence, we can calculate $C_n$ , which turns out to be $\sum_{i=1}^{n}{(a_i - b_i)^2} \ge \dfrac{2n(2n+1)(4n+1)}{3} - \left \lfloor \dfrac{n}{2} \right \rfloor \cdot \left \lfloor \dfrac{3n}{2} \right \rfloor^2 - \left \lceil \dfrac{n}{2} \right \rceil \cdot \left \lceil \dfrac{5n}{2} \right \rceil^2$

This post has been edited 1 time. Last edited by Seungjun_Lee, Dec 14, 2024, 2:41 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a