Any idea?

I have seen the canonical proof(http://om.edu.pl/sites/default/files/zadania/om/65-3rozwn.pdf ). I don't know how the man can find this solution. It looks like sth impossible, could you help me?

Solution inspired by numbersandnumbers: It's equivalent to show $\sum \log a_i > \sum \log b_i$. Consider $f(x)=\dfrac{\log x}{x}$, so $f'(x) = \dfrac{1-\log x}{x^2}$. Then clearly $f$ increases on $0<x<e$ and decreases on $x>e$. However, $f(4) = \dfrac{\log 4}{4} = \dfrac{\log 2}{2} = f(2)$, so we establish $f(3) > f(2)=f(4) > f(5) > f(6) > ...$. Clearly $b_1 \ge 4$. If $b_1=4$ then $a_1=2,a_2=3,n=1$, from which the conclusion follows. Otherwise, $b_1 > 4$. Then it follows that $f(a_i)>f(b_j)$ for all $i,j$. So $\sum \log a_i = \sum a_i f(a_i) \ge \sum a_i \min (f(a_1), f(a_2), ... f(a_k)) > \sum b_i \text{max} (f(b_1), f(b_2), ... f(b_n)) \ge \sum b_i f(b_i) = \sum \log b_i$, as desired.

Wow, great!

We want to use Karamata inequality for the $\log$, so we need to construct two sequences where one majorizes the other one. Let $C= \sum a_i - \sum b_i-(k-n-1)$ . Let $(y_i)$ be a reversed $(a_i)$ sequence. Now define $(x_i)$ as $(b_n, \ldots, C, \ldots, b_1, , 1, \ldots 1)$, where $1$ appears $k-n-1$ times and we place $C$ so that the sequence is decreasing. By the problem assumptions $(x_i)\succeq (y_i)$ and they are both decreasing. Thus by the Karamata inequality and $\log$'s concavity: $ \sum \log(x_i) \le \sum\log(y_i) \iff \sum \log b_i + \log C \le \sum \log a_i \implies \sum \log b_i < \sum \log a_i $.