Does there exist bijections f,g from positive integers to themselves st: g(n)=f(1)+f(2)+⋅⋅⋅+f(n)nholds 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)=f(1)+f(2)+⋅⋅⋅+f(n)nholds for any n? f(1)=g(1) ∀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, ∃t1 such that g(t1)=1 If t1>1 : f(t1)=t1−(t1−1)g(t1−1). But g(t1−1)≥2 (since g(t1−1)≠g(t1)=1) and so f(t1)≤2−t1<1, impossible So t1=1 and f(1)=g(1)=1 Suppose now that g(k)=k ∀k∈{1,...,n} Since g(x) is surjective, ∃tn+1 such that g(tn+1)=n+1 Since g(x) injective and g(k)=k ∀k∈{1,...,n}, tn+1≥n+1 Since ng(n) is stricly increasing, tn+1g(tn+1)>(tn+1−1)g(tn+1−1), which is tn+1(n+1)>(tn+1−1)g(tn+1−1) If tn+1≥n+2, then tn+1−1>n and g(tn+1−1)≥n+2 but above inequality implies tn+1tn+1−1(n+1)>g(tn+1−1) and so tn+1tn+1−1(n+1)>n+2 which easily implies tn+1<n+2, contradiction So tn+1=n+1 and g(n+1)=n+1 And so, since g(1)=1, we get that g(n)=n ∀n but this implies f(n)=2n−1, which is not surjective. And so No such bijections f(n),g(n)
17.08.2023 15:48
Obviously g(1)=f(1)=1 and ng(n)≥(n−1)g(n−1)⟹g(n)+g(n)n−1≥g(n−1)Hence, g(n)<g(n−1) implies g(n−1)>g(n)≥n Now we use induction on n to show g(m)=n⟹m=n. Assume g(k)=k for all k<n and let g(m)=n. If m>n, since g(m−1)≥n+1, g(m)<g(m−1)⟹g(m)≥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 no. Assume such bijections exist. Claim: g(1)=f(1)=1 Let g(a)=1. Notice 1=g(a)=f(1)+f(2)+⋯+f(a)a≤1+2+⋯+aa=a+12. So we must have a=1⇒g(1)=1⇒f(1)=1. Using recursion, (n+1)g(n+1)=ng(n)+f(n+1)⇒ng(n)<(n+1)g(n+1). Induction gives that n≤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)=f(1)+...+f(n)n≥n(n+1)2n=n+12hence g(k)>1 for k≥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≥4. So g(3)=2 but 6<1+5+f(3)≤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≤n, then g(n+1)=n+1. Assume that g(n+1)>n+1. Since g(k)=k for k≤n, we also have f(k)=2k−1 for k≤n. n+1=g(n+m)=f(1)+...+f(n+m)n+m=n2+f(n+1)+...+f(n+m)n+mSuppose that m>1. In addition, g(n+1),...,g(n+m−1)>n+1 hence max{g(n+1),...,g(n+m−1)}≥n+m. Let g(n+l)≥n+m. n+m≤g(n+l)=n2+f(n+1)+...+f(n+l)n+l<n2+f(n+1)+...+f(n+m)n+1which yields g(n+m)=n2+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.◼