Does there exist bijections $f,g$ from positive integers to themselves st: $$g(n)=\frac{f(1)+f(2)+ \cdot \cdot \cdot +f(n)}{n}$$holds for any $n$?
Problem
Source: Iran MO 3rd round 2023 , D1P2
Tags: algebra
16.08.2023 15:54
alinazarboland wrote: Does there exist bijections $f,g$ from positive integers to themselves st: $$g(n)=\frac{f(1)+f(2)+ \cdot \cdot \cdot +f(n)}{n}$$holds for any $n$? $f(1)=g(1)$ $\forall n>1$ : $f(n)=ng(n)-(n-1)g(n-1)$ (and so $ng(n)$ is a strictly increasing function) Since $g(x)$ is surjective, $\exists t_1$ such that $g(t_1)=1$ If $t_1>1$ : $f(t_1)=t_1-(t_1-1)g(t_1-1)$. But $g(t_1-1)\ge 2$ (since $g(t_1-1)\ne g(t_1)=1$) and so $f(t_1)\le 2-t_1<1$, impossible So $t_1=1$ and $f(1)=g(1)=1$ Suppose now that $g(k)=k$ $\forall k\in\{1,...,n\}$ Since $g(x)$ is surjective, $\exists t_{n+1}$ such that $g(t_{n+1})=n+1$ Since $g(x)$ injective and $g(k)=k$ $\forall k\in\{1,...,n\}$, $t_{n+1}\ge n+1$ Since $ng(n)$ is stricly increasing, $t_{n+1}g(t_{n+1})>(t_{n+1}-1)g(t_{n+1}-1)$, which is $t_{n+1}(n+1)>(t_{n+1}-1)g(t_{n+1}-1)$ If $t_{n+1}\ge n+2$, then $t_{n+1}-1>n$ and $g(t_{n+1}-1)\ge n+2$ but above inequality implies $\frac{t_{n+1}}{t_{n+1}-1}(n+1)>g(t_{n+1}-1)$ and so $\frac{t_{n+1}}{t_{n+1}-1}(n+1)>n+2$ which easily implies $t_{n+1}<n+2$, contradiction So $t_{n+1}=n+1$ and $g(n+1)=n+1$ And so, since $g(1)=1$, we get that $g(n)=n$ $\forall n$ but this implies $f(n)=2n-1$, which is not surjective. And so $\boxed{\text{No such bijections }f(n),g(n)}$
17.08.2023 15:48
Obviously $g(1)=f(1)=1$ and $$ng(n) \geq (n-1)g(n-1) \implies g(n)+\frac{g(n)}{n-1} \geq g(n-1)$$Hence, $g(n)< g(n-1)$ implies $g(n-1)>g(n)\geq n$ Now we use induction on $n$ to show $g(m)=n \implies m=n$. Assume $g(k)=k$ for all $k<n$ and let $g(m)=n$. If $m>n$, since $g(m-1)\geq n+1$, $g(m)<g(m-1) \implies g(m)\geq m$ which is a clear contradiction. Thus $m=n$. From that, we obtain $g(n)=n$ which is again contradicts with the fact that $f$ is bijective.
05.05.2024 01:11
The answer is $\boxed{\text{no}}$. Assume such bijections exist. Claim: $g(1)=f(1)=1$ Let $g(a)=1$. Notice $1=g(a)=\frac{f(1)+f(2)+\dots+f(a)}{a}\leq \frac{1+2+\dots+a}{a}=\frac{a+1}{2}$. So we must have $a=1\Rightarrow g(1)=1\Rightarrow f(1)=1$. Using recursion, $(n+1)g(n+1)=ng(n)+f(n+1)\Rightarrow ng(n)<(n+1)g(n+1)$. Induction gives that $n\leq g(n)$. Since $g(n)$ is a bijection $g(n)=n$ for all $n$. Now induction gives $f(n)=2n-1$, a contradiction.
29.07.2024 18:38
There doesn't exist such functions. \[g(n)=\frac{f(1)+...+f(n)}{n}\geq \frac{n(n+1)}{2n}=\frac{n+1}{2}\]hence $g(k)>1$ for $k\geq 2$ which gives that $f(1)=1=g(1)$. First let's show that $f(2)=3$. Supppose not. Since $2|f(2)+1, \ f(2)$ must be odd. $g(k)>2$ for $k\geq 4$. So $g(3)=2$ but $6<1+5+f(3)\leq 1+f(2)+f(3)=f(1)+f(2)+f(3)=6$ which is impossible. Thus, $f(2)=3$. Now we will show that if $g(k)=k$ for all $k\leq n,$ then $g(n+1)=n+1$. Assume that $g(n+1)>n+1$. Since $g(k)=k$ for $k\leq n,$ we also have $f(k)=2k-1$ for $k\leq n$. \[n+1=g(n+m)=\frac{f(1)+...+f(n+m)}{n+m}=\frac{n^2+f(n+1)+...+f(n+m)}{n+m}\]Suppose that $m>1$. In addition, $g(n+1),...,g(n+m-1)>n+1$ hence $max\{g(n+1),...,g(n+m-1)\}\geq n+m$. Let $g(n+l)\geq n+m$. \[n+m\leq g(n+l)=\frac{n^2+f(n+1)+...+f(n+l)}{n+l}< \frac{n^2+f(n+1)+...+f(n+m)}{n+1}\]which yields $g(n+m)=\frac{n^2+f(n+1)+...+f(n+m)}{n+m}>n+1$ which gives that $g(n)=n$ for all $n$. But then, $f$ cannot be a bijection.$\blacksquare$