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

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

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$

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

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

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