More combinatorics than algebra. We will solve both parts at once. Expanding the LHS, we have $$\sum_{i=1}^{n}(i+a_i)^k=\sum_{i=1}^{n} \sum_{k=0}^n \binom{n}{k} i^k a_i^{n-k}= \sum_{k=0}^n \binom{n}{k} \sum_{i=1}^{n}i^k a_i^{n-k},$$hence considering $\sum_{i=1}^{n}i^k a_i^{n-k}$, by rearrangement inequality smallest value of LHS is achieved when $a_1\ge a_2\ge \ldots \ge a_n.$ Given this, we now show that the multisets $\{i+a_i\}$ and $\{i+b_i\}$ are equal. Consider a $n\times n$ grid, and colour $a_1$ squares in the first column, $a_2$ in the second and so on, now apply "gravity" to pull all the coloured squares down, then $b_1$ are the number of coloured squares in the bottom row, $b_2$ coloured squares in the second row from the bottom and so on. Now for each row and column we add in its respective $i$ squares. Note that any coloured square that do not have a coloured square to its top or right(let this square be $A$) have the same number of squares we are counting in both its row and column. Hence the multiset condition is fulfilled when $A$ is coloured iff the multiset condition is fulfilled when $A$ is not coloured. Eventually all squares can be uncoloured where the multiset condition is clearly fulfilled, and we are done. Attached is a picture using the example provided in the question.

Attachments:

Notice that if $i>j$ and $a_i>a_j$, we can swap $a_i,a_j$, then the right hand side of the inequality is unchanged. Meanwhile, $$(i+a_i)^k+(j+a_j)^k\geq (i+a_j)^k+(j+a_i)^k$$Therefore, it suffices to deal with the case where $a_1\geq a_2\geq...\geq a_n$. Now let $m$ be the greatest integer such that $a_m=a_1$, now notice that if we replace $a_m$ by $a_m-1$, then the change in the left hand side will be $$(m+a_m)^k-(m+a_m-1)^k$$Meanwhile, notice that the only term that changes in the sequence $\{b_n\}$ is $b_{a_m}$, which changes from $m$ to $m-1$, hence it changes by $$(a_m+m)^k-(a_m+m-1)^k$$therefore the resulting inequality is equivalent to the original one. Now after finitely many operations we will arrive the state $a_1=...=a_n=0$ which the inequality obviously holds, this completes the proof.