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

Question

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.

Answer 1

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 (#).