Let $a_1,a_2,\cdots,a_n$ be a permutation of $1,2,\cdots,n$. Among all possible permutations, find the minimum of $$\sum_{i=1}^n \min \{ a_i,2i-1 \}.$$
Problem
Source: China Additional TST for IMO 2020, P5
Tags: inequalities, algebra
20.10.2020 06:37
JustPostChinaTST wrote: Let $a_1,a_2,\cdots,a_n$ be a permutation of $1,2,\cdots,n$. Among all possible permutations, find the minimum of $\sum_{i=1}^n \min \{ a_i,2i-1 \}$.
20.10.2020 06:59
the answer is that let a1>a2>...>an and then we see that a1 is n and an is 1 . and taking the sum we get the minimum
15.01.2021 09:02
Cool problem I claim that our answer is achieved when $a_i = n+1 - i$ for all $i$; this way, among the $n$ terms $b_i = \text{min}(a_i, 2i - 1)$, we will have $b_i = 2i-1$ for $i$ from $1$ up to $\lfloor \tfrac{n+2}{3}\rfloor$ and $b_i = n+1 - i$ for $i \geq \lceil \tfrac{n+2}{3} \rceil$. Note that in the sequence $b_n$, which ranges from $1$ to $n + 1 - \lceil \tfrac{n+2}{3} \rceil$, each odd number up to the upper bound appears twice, and each even number up to the upper bound appears once. We show that indeed, this is the minimum. In the sequence $b_n$, clearly each odd number appears at most twice, possibly once as an $a_i$ and another as a $2i - 1$. Each even number can only appear once; only possible as an $a_i$. Hence, the minimum is achieved when we greedily take all the smaller numbers, i.e two 1s, one 2, two 3s, and so on, which is what we have described in the first section. $\blacksquare$
04.04.2021 18:14
I will give another solution to this problems Obviously,min(x,y)=(1/2)*(x+y-abs(x-y)),andΣai=n(n-1)/2,Σ(2i-1)=n^2,so we only need to deal with the maximum of Σabs(2i-1-ai) it'easy to turn it into a quadratic function of x,here x=CARD({ai|ai>=2i-1}) the answer is achieved when ai=n+1-i for all i
04.04.2021 21:29
I first show if $a<b, c<d$ then $\min\{a,c\}+\min\{b,d\} \ge \min\{a,d\} + \min\{b,c\}$ Proof. It suffices to show $\min\{a,c\} - \min\{b,c\} \ge \min\{a,d\} - \min\{b,d\}$. Let $f(x)=\min\{x,c\}-\min\{x,d\}$. Note for $x\le c, f(x)=0,$ and for $c<x\le d, f(x)=c-x$ and if $x>d, f(x)=c-d$. Therefore, $f$ never increases. Therefore, the minimum can be obtained with $a_i$ are strictly decreasing, for if $a_i<a_j, i<j$ then we swap $a_i,a_j$.
27.06.2021 23:32
There are many solutions to a f(i) should be n+1 -i I want to give the sum: For n = 2k+1 Sum is k^2 + 3k, For n=2k Sum is k^2+2k-1