it's easy to solve the problem for the cases where $n=p$ is prime or $n=p^2$ or when $n=pq$ with primes $p,q$. Now assume that $n$ is not in these forms.$\bigstar$ Note that if $(a,n)=1$ then $(n-a,n)=1$ and exactly one of $a,n-a$ is greater than $\frac{n}{2}$ and the other is less than $\frac{n}{2}$ ;so if we assume $a<\frac{n}{2}$ then $|\frac{n}{2}-a|+|\frac{n}{2}-(n-a)|=n-2a$. hence $\sum_{i=1}^k |a_i-\frac{n}{2}|=\frac{n\phi(n)}{2}-2S (1)$ where $S$ is sum of positive integers less than $\frac{n}{2}$ and relatively prime to $n$. Let $p$ be the least prime divisor of $n$ and $T$ be the sum of positive integers that are relatively prime to $m=\frac{n}{p}$. obviously $S\ge T=\frac{m\phi(m)}{2}\ge pm=n$ (because $\phi(m)>2p (2)$ with the condition $\bigstar$). From $(1),(2)$ we get $\sum_{i=1}^k |a_i-\frac{n}{2}|=\frac{n\phi(n)}{2}-2S\le \frac{n\phi(n)}{2}-2n=\frac{n(\phi(n)-4)}{2}$. Q.E.d

Actually the scale of $\sum_{i=1}^k |a_i-\frac{n}{2}| $ is $ \frac{n\phi(n)}{4} $ . One can actually get the real number by exclusion-inclusion principle, but a kittle different case by case.

Let's calculate $ f_i(n)=\sum_{p|i}^{ } |i-\frac{n}{2}| $.(For integer $ p $ such that no prime $ q $ is $ q^2|p $. $ p|n $, $ 0<i<n $.) Case1) $ p $ is even: 1)$ n \equiv 2 (mod 4) $: let's say $ n=p(2k+1) $. Then, $ f_i(n)=pk^2=\frac{(n-p)^2}{4p} $. 2)$ n \equiv 0 (mod 4) $: let's say $ n=2pk $. Then, $ f_i(n)=pk(k-1)=\frac{n(n-2p)}{4p} $. Case2) $ p $ is odd: 1)$ n $ is odd: let's say $ n=p(2k+1) $. Then, $ f_i(n)=pk^2=\frac{(n-p)^2}{4p} $. 2)$ n $ is even: let's say $ n=2pk $. Then, $ f_i(n)=pk(k-1)=\frac{n(n-2p)}{4p} $. Then, we use exclusion-inclusion principle.

@above I don't think that's true for $n=26$. It is given that $k=\phi (n) > 8$. It is well-known that $\phi(n) \equiv 0 \pmod{2}$ for all $n \ge 3$. It is very easy to prove that $\sum_{i=1}^k a_i = \frac{nk}{2}$. (1) Since $a_{i} + a_{k-i} = n$, we have $a_{\frac{k}{2}} < \frac{n}{2} < a_{\frac{k}{2}+1}$. Now we need to prove that $$\sum_{i=1}^{\frac{k}{2}} \frac{n}{2} - a_i + \sum_{i=\frac{k}{2}+1}^k a_i-\frac{n}{2} < \frac{n(k-4)}{2}$$ Using (1), we can reduce the problem into proving that $S=\sum_{i=1}^{\frac{k}{2}} a_i > n$, or the following statement - The sum of numbers less than $\frac{n}{2}$ and relatively prime with $n$ is larger than $n$. Let $f(n)$ as $\frac{n \pm 1}{3}$ if $n \equiv \mp 1 \pmod{3}$, or $\frac{n}{3} \pm 1 \not\equiv 0 \pmod{3}$ if $n \equiv 0 \pmod{3}$ (Basically, we choose an integer that is closest to $\frac{n}{3}$ but is not $\frac{n}{3}$.) (If $\frac{n}{3}$ is an integer, we choose $f(n)$ so that it is not a multiple of $3$) It is easy to check that $f(n)$ is relatively prime with $n$ and that $\frac{n}{3}-1 \le f(n) \le \frac{n}{3}+1$. Case 1. $n$ is odd. We check $n<30$ by hand. Assume $n>30$. Denote $n$ as $2^k+m$, where $1 \le m \le 2^k-1$. We have $\frac{2^k+1}{3}-1 \le f(n) \le \frac{2^{k+1}-1}{3}+1$, so $2^{k-2} < f(n) < 2^k $. Also, we have $f(n) \le \frac{n}{3}+1 < \frac{n-1}{2}$ for $n>9$. Now we have $$S \ge 1+2+ \cdots + 2^{k-2} + f(n) + \frac{n-1}{2} \ge 2^{k-1}-1 + \frac{n}{3}-1 + \frac{n-1}{2} > \frac{n}{4}-1+\frac{n}{3}-1+\frac{n-1}{2} = \frac{13}{12}n-\frac{5}{2} > n$$since we have assumed that $n>30$. Case 2. $n$ is a multiple of $4$. If $n$ is a multiple of $4$, note that $(x,n)=1 \iff (\frac{n}{2}-x,n)$ which is easy to check. Since $k>8$, we have $S = \frac{1}{2} \cdot \frac{n}{2} \cdot \frac{k}{2} = \frac{nk}{8} > n$ as desired. Case 3. $n=4m+2$. We check $m \le 7$ by hand. Note that $(2m-1,4m+2)=1$, and $m+1 \le \frac{4m+2}{3}-1 \le f(4m+2) \le \frac{4m+2}{3}+1 < 2m-1$ Now either $m$ or $m+1$ is odd, and that number is relatively prime with $n$. Let this number be $t$. Therefore, $$S \ge 1+t+f(4m+2)+2m-1 \ge 1+m+\frac{4m+2}{3}-1+2m-1 = \frac{13}{3}m-\frac{1}{3} > 4m+2=n$$as desired. We have exhausted all cases, and we are done. $\blacksquare$

Can't we just divide the case of n when it is odd and even? I think we don't need to classify in that complicated way

PARISsaintGERMAIN wrote: Can't we just divide the case of n when it is odd and even? I think we don't need to classify in that complicated way similar solution exists so that it seems strange to believe that it has described all but it really describes all the cases so that the conclusion happens this solution bases on the limit of maximum possible prime as factor