A function $f:\mathbb{N} \rightarrow \mathbb{N} $ is called nice if $f^a(b)=f(a+b-1)$, where $f^a(b)$ denotes $a$ times applied function $f$. Let $g$ be a nice function, and an integer $A$ exists such that $g(A+2018)=g(A)+1$. a) Prove that $g(n+2017^{2017})=g(n)$ for all $n \geq A+2$. b) If $g(A+1) \neq g(A+1+2017^{2017})$ find $g(n)$ for $n <A$.
Problem
Source: Serbia TST 2017 #3
Tags: function, algebra
21.05.2017 20:14
21.05.2017 20:40
ThE-dArK-lOrD wrote: It's clear that $t\neq 1$, otherwise $A$ doesn't exist. So $t=2017$ and $g(n)=g(n+2017)$ for all $n\geq A\geq i$. Remark; I'm not sure. If you can find any mistake, please let me know. It's not clear why $t=1$ would imply that $A$ doesn't exists.
21.05.2017 20:48
@above If $t=1$, we get $g(n)=g(n+1)$ for all $n\geqslant i$. Note that $A+2018\geqslant A\geqslant i$. So, $g(A+2018)=g(A)=g(i)$.
24.05.2017 06:29
ThE-dArK-lOrD wrote: So $g^{h+l}(A)\equiv g^{h+l-1}(A)-1 \pmod{t}$ for all $l\in \mathbb{Z}^+$. We get $g(A+v)=g^{v+1}(A)\equiv g(A)+v \pmod{t}$ for all $v\in \mathbb{Z}^+$ (we can set $v=v'+wt$ for any $v'$ and large enough $w\in \mathbb{Z}^+$). Why we have $g(A+v)=g^{v+1}(A)\equiv g(A)+v \pmod{t}$ rather than $g^{v+1}(A)\equiv g(A)-v \pmod{t}$ ?
24.05.2017 09:55
@above Sorry, by substituting $\ell\leftarrow \ell+1$ in $t\mid g^{h+\ell-1}(A)-A-2017-\ell$, we get $$g^{h+\ell}(A) \equiv g^{h+\ell-1}(A)\textcolor{red}{+} 1 \pmod t.$$Edited in #3.
25.05.2017 06:29
Thanks above. @smy2012 gives a nice solution for a): \[f(A+2)=f^{(3)}(A)=f^{(2)}(f(A))=f(f(A)+1)=f^{(2020)}(A)=f(A+2019),\]thus \[f(n)=f^{(n-A-1)}(A+2)=f^{(n-A-1)}(A+2)=f^{(n-A-1)}(A+2019)=f(n+2017),\forall n\ge A+2,\]so we are done.
23.12.2017 11:17
ThE-dArK-lOrD wrote:
Remark; I'm not sure. If you can find any mistake, please let me know. how do you get the value of g(i-1) when A=i-1
27.04.2020 14:01
@above The problem asks for only $g(n)$ when $n<A$. P.S. I have made some substantial edits to #3.
08.08.2021 16:36
Replace $g$ with $f$, $A$ with $M$ and $2017$ with $2021$ Let $P(m,n)$ denote the assertion that $f^n(m) = f(n+m-1) \forall n,m \in \mathbb{N}$ $$P(1,m) \implies \boxed{f^m(1) = f(m)} \text{ } \clubsuit$$So $f^k(m) = f^{k-1}(f(m)) = f^{k-1}(f^m(1))=f^{m+k-1}(1)$ $$P(f^k(m),n) \implies f^n(f^k(m)) = f(f^k(m)+n-1)$$But $f^n(f^k(m)) = f^n(f^{m+k-1}(1)) = f^{m+k+n-1}(1)=f(m+k+n-1)$. Thus $f(f^k(m)+n-1)=f(m+k+n-1)$ This gives that $f$ is eventually a cycle, but since the orbit of $1$ goes through everything in the range of $m$ (because of $\clubsuit$), we must have exactly one cycle, and that too in the orbit of $1$. Let the cycle length be $c$. Then we must have $\boxed{c \mid f^k(m) -m-k}$. Let this assertion be denoted by $Q(m,k)$ $$Q(M,1) \implies c \mid f(M)-M-1$$$$Q(M+2022,1) \implies c \mid f(M+2022) - M -2022 -1 = f(M)-M-2022$$Hence $\boxed{c \mid 2021}$. See that $f^{2024}(M) = f(f^{2023}(M)) = f(f(M+2022)) = f(f(M) + 1)$, but also $f(f(M)+1) = f(f(f(M))) = f^3(M)$ So, we have $f(M+2) = f^3(M) = f^{2024}(M)$ So, from $f(f(f(M))) = f(M+2)$ onwards, $f$ is a cycle, so from original eqn, $f$ is periodic mod $2021$ from then onwards. Now, we claim we must have $|f(n) - n - 1| \ge M$ or $f(n) - n - 1 =0$ for all $n < M$. Suppose we had $f(N) - N - 1 = L < M$ for some $N$. Then, since we had $f(f^k(m) + n - 1) = f(m+k+n-1)$, putting $k = 1$ we get $f(f(m)+n-1) = f(m+n)$, and putting $m = N$, we get that $f(f(M)+n-1) = f(M+n) \implies f(N+n+L) = f(N+n)$ which means, letting $z = N+n$, $f(z) = f(z+L)$ and so $f(z)$ is part of the cycle for every $z \ge N+1$, but this means that for a number $f(M+1)$ must also be part of the cycle, impossible by condition (ii) given. Now, we will show that $f(n) = n+1$ for all $n < M$ by induction. First, the base case $n = 1$, since if $f(1) - 1 - 1 \neq 0$, then $f(1) \ge M+1+1 = M+2$ meaning $f(2) = f(M+2)$ which is part of the cycle, impossible. Repeating the same thing for other numbers, we obtain that $f(n) = n+1$ for all $n < M$ @below - It's literally the same, except I did a version of the problem which was phrased slightly differently. I've added the changes though
09.08.2021 06:57
L567 wrote: Let $P(m,n)$ denote the assertion that $f^n(m) = f(n+m-1) \forall n,m \in \mathbb{N}$ \newline $$P(1,m) \implies \boxed{f^m(1) = f(m)} \text{ } \clubsuit$$So $f^k(m) = f^{k-1}(f(m)) = f^{k-1}(f^m(1))=f^{m+k-1}(1)$ $$P(f^k(m),n) \implies f^n(f^k(m)) = f(f^k(m)+n-1)$$But $f^n(f^k(m)) = f^n(f^{m+k-1}(1)) = f^{m+k+n-1}(1)=f(m+k+n-1)$. Thus $f(f^k(m)+n-1)=f(m+k+n-1)$ This gives that $f$ is eventually a cycle, but since the orbit of $1$ goes through everything in the range of $m$ (because of $\clubsuit$), we must have exactly one cycle, and that too in the orbit of $1$. Let the cycle length be $c$. Then we must have $\boxed{c \mid f^k(m) -m-k}$. Let this assertion be denoted by $Q(m,k)$ $$Q(M,1) \implies c \mid f(M)-M-1$$$$Q(M+2022,1) \implies c \mid f(M+2022) - M -2022 -1 = f(M)-M-2022$$Hence $\boxed{c \mid 2021}$. See that $f^{2024}(M) = f(f^{2023}(M)) = f(f(M+2022)) = f(f(M) + 1)$, but also $f(f(M)+1) = f(f(f(M))) = f^3(M)$ So, we have $f(M+2) = f^3(M) = f^{2024}(M)$ So, from $f(f(f(M))) = f(M+2)$ onwards, $f$ is a cycle, so from original eqn, $f$ is periodic mod $2021$ from then onwards. Now, we claim we must have $|f(n) - n - 1| \ge M$ or $f(n) - n - 1 =0$ for all $n < M$. Suppose we had $f(N) - N - 1 = L < M$ for some $N$. Then, since we had $f(f^k(m) + n - 1) = f(m+k+n-1)$, putting $k = 1$ we get $f(f(m)+n-1) = f(m+n)$, and putting $m = N$, we get that $f(f(M)+n-1) = f(M+n) \implies f(N+n+L) = f(N+n)$ which means, letting $z = N+n$, $f(z) = f(z+L)$ and so $f(z)$ is part of the cycle for every $z \ge N+1$, but this means that for a number $f(M+1)$ must also be part of the cycle, impossible by condition (ii) given. Now, we will show that $f(n) = n+1$ for all $n < M$ by induction. First, the base case $n = 1$, since if $f(1) - 1 - 1 \neq 0$, then $f(1) \ge M+1+1 = M+2$ meaning $f(2) = f(M+2)$ which is part of the cycle, impossible. Repeating the same thing for other numbers, we obtain that $f(n) = n+1$ for all $n < M$ The condition given is different mate, read the question again
09.08.2021 08:57
@above its essentially the same except that 2017 thing, and well we know why he used 2021
06.09.2021 19:28
Solution. a) Claim 1. $g(g(a)+b)=g(a+b+1)$ Proof. $g(g(a)+b)=g^{b}(g(a))=g(a+b+1).\square$ Claim 2. If $g(a)=g(b) \Rightarrow g(x)=g(x+b-a), \forall x \ge a$ Proof. $g(a)=g(b) \Rightarrow g^k(a)=g^k(b) \Rightarrow g(a+k)=g(b+k) \Rightarrow g(x)=g(x+b-a), \forall x \ge a. \square$ Claim 3.$g(a)=g(a+2017), \forall a\ge A+2.$ Proof. $g(A+2018)=g(A)+1\Rightarrow g(g(A+2018))=g(g(A)+1) \Rightarrow g(A+2+2017)=g(A+2).\square$ By Claim 3 we get that $g(a+2017^{2017})=g(a),\forall a\ge A+2.\blacksquare$ b) Claim 4.If $g(a)=b \Rightarrow g(x)=g(x+b-a-1), \forall x\ge a+1$ Proof. This is trivial by Claim 2.$\square$ Lets define terms "part" "periodic part", "enventualy periodic" and "non-periodic part" We say $f$ is "eventualy periodic" such that $\exists g:N\longrightarrow N$ and $k$ such that $g(x-k)=f(x),\forall x\ge k$ and $g$ is a periodic function i.e $g(x)=g(x+a)$. Let $a$ be the smallest number such that $g(x)=g(x+a)$, we define the "periodic part" as the sequnence $s_k$ thats created by $s_i=g(i),\forall i < k$ and the "non periodic part" as the sequence $t_k$ thats created by $t_i=f(i)$. Claim 5. Let $s_k$ be the non periodic part than $s_i=i+1,i/leq k-1$ Proof. If $p=g(t)\neq t+1$ than $g(g(t))=g(t+1)=g(p)$ by claim 4 we have that this is in the periodic part thus if $g(a)\in$ non periodic part(except the last term) $g(a)=a+1.\square$ Claim 6.If a function has $g(x+a)=g(x+b)$ and $g(x+c)=g(x+d),\forall x\in N \Rightarrow g(x+min[a,c]+gcd(b,d))$ Proof. By bezout theorem $\exists m,n$ such that $km-bn=gcd(b,d)$ thus for big enough $x, g(x)=g(x+gcd(b,d))$ but from $g(x+a)=g(x+b) $and$ g(x+c)=g(x+d) $ we get $g(x+min[a,c]+gcd(b,d)).\square$ By Claim 6 the periodic part can only be of lengh $1$ or $2017$. Now we will look at cases. Claim7. $g(A+1)$ is in the non periodic part Proof. $g(A+1)\neq g(A+1+2017^{2017})=g(A+2018)$ thus it is not in the periodic part.$\square$ Thus by Claim 7 if $n<A \Rightarrow g(n)=n+1.\blacksquare$