Prove that $y_1, . . . , y_n$ can be obtained from $x_1, . . ., x_n$ by a permutation if $x_1^{x_1}+...+x_n^{x_n}= y_1^{y_1}+...+y_n^{y_n}$ 
Let $x_1, x_2, . . . , x_n$ and $y_1, y_2, . . . , y_n$ be two sets of pairwise different positive integers numbers for which the equality
$$x_1^{x_1}+x_2^{x_2}+...+x_n^{x_n}= y_1^{y_1}+y_2^{y_2}+...+y_n^{y_n}$$
holds. Prove that the set $y_1, y_2, . . . , y_n$ can be obtained from the set $x_1, x_2, . . . , x_n$ by a permutation.

My work so far:
I used induction.
Let $n=1$ $$x_1^{x_1}= y_1^{y_1} \Rightarrow x_1=y_1$$
Let $n \ge 2$
I need help here.
 A: For any positive integer $N$,
$$N^N>\sum_{k=1}^{N-1}\,k^k\,.$$
If $N=1$, we have $1>0$.  For $N>1$, we get
$$\sum_{k=1}^{N-1}\,k^k\leq \sum_{k=1}^{N-1}\,N^k=\frac{N^N-N}{N-1}<N^N\,.$$
Thus, if $x_1<x_2<\ldots<x_n$ and $y_1<y_2<\ldots<y_n$, we must have $x_n=y_n$.  If $x_n<y_n$, then we have the following contradiction
$$\sum_{i=1}^n\,x_i^{x_i}\leq \sum_{k=1}^{y_n-1}\,k^k<y_n^{y_n}\leq \sum_{i=1}^n\,y_i^{y_i}\,.$$
Similarly, $x_n>y_n$ cannot happen either.  Now, you complete the proof by induction on $n$.

In fact, let $f:\mathbb{N}\to\mathbb{N}$ be a strictly increasing function such that, for a fixed integer $t\geq 0$, $f(1)\geq t$ and $$f(k+1)\geq 2\,f(k)-t\tag{*}$$
  holds for all $k\in\mathbb{N}$.  Here, $0\notin\mathbb{N}$.  Let $n$ be an arbitrary positive integer.  If each of the $n$-tuples $\left(x_1,x_2,\ldots,x_n\right)$ and $\left(y_1,y_2,\ldots,y_n\right)$ consists of pairwise distinct positive integers and
  $$\sum_{i=1}^n\,f\left(x_i\right)=\sum_{i=1}^n\,f\left(y_i\right)\,,\tag{#}$$
  then $\left(x_1,x_2,\ldots,x_n\right)$ and $\left(y_1,y_2,\ldots,y_n\right)$ are related by a permutation.

To show this general statement, suppose that $x_1<x_2<\ldots<x_n$ and $y_1<y_2<\ldots<y_n$.  If $n=1$, then the claim is obviously true.  Assume from now on that $n>1$.  
If $x_n<y_n:=m$, then $x_i\leq m-i$ for every $i=1,2,\ldots,n$.  Let $a:=f(m)$, whence $$a=f(m)>f(1)\geq t\,.$$  It can be easily seen by induction, using (*), that $$f(m-i)\leq \frac{1}{2^i}a+\left(1-\frac{1}{2^i}\right)t$$
for every $i=0,1,2,\ldots,m-1$.  Hence,
$$\sum_{i=1}^n\,f\left(x_i\right)\leq \sum_{i=1}^n\,\Biggl( \frac{1}{2^i}a+\left(1-\frac{1}{2^i}\right)t\Biggr)=\left(1-\frac{1}{2^n}\right)(a-t)+nt\,.$$
On the other hand,
$$f\left(y_i\right)\geq f(1)\geq t$$
for $i=1,2,\ldots,n-1$.  Thus,
$$\sum_{i=1}^n\,f\left(y_i\right)\geq f\left(y_n\right)+(n-1)t=a+(n-1)t\,.$$
Consequently,
$$\sum_{i=1}^n\,f\left(y_i\right)\geq (a-t)+nt>\left(1-\frac{1}{2^n}\right)(a-t)+nt\geq\sum_{i=1}^n\,f\left(x_i\right)\,.$$
This is a contradiction.  By symmetry, $x_n>y_n$ does not hold.  Therefore, $x_n=y_n$, and induction on $n$ completes the proof.
P.S.  The expansion coefficient $2$ is the best (i.e., smallest) constant.  In other words, one can show that there are strictly increasing functions $f:\mathbb{N}\to\mathbb{N}$ such that, for fixed $\gamma>0$ with $\gamma<2$ and $t\geq 0$, $f(1)\geq t$ and $$f(k+1)\geq \gamma f(k)-t$$ for all $k\in\mathbb{N}$ and that there exist, for some $n\in\mathbb{N}$, two $n$-tuples of pairwise distinct positive integers $\left(x_1,x_2,\ldots,x_n\right)$ and $\left(y_1,y_2,\ldots,y_n\right)$ which are not a permutation of one another and which satisfy (#).
