MathDB

Q1

Part of STEMS 2021 Math Cat C

Problems(1)

Infinitely many functions which win and lose

Source: STEMS 2021 Math Cat C Q1

1/25/2021
Let M>1M>1 be a natural number. Tom and Jerry play a game. Jerry wins if he can produce a function f:N→Nf: \mathbb{N} \rightarrow \mathbb{N} satisfying
[*]f(M)≠Mf(M) \ne M [/*] [*] f(k)<2kf(k)<2k for all k∈Nk \in \mathbb{N}[/*] [*] ff(n)(n)=nf^{f(n)}(n)=n for all n∈Nn \in \mathbb{N}. For each ℓ>0\ell>0 we define fℓ(n)=f(fℓ−1(n))f^{\ell}(n)=f\left(f^{\ell-1}(n)\right) and f0(n)=nf^0(n)=n[/*]
Tom wins otherwise. Prove that for infinitely many MM, Tom wins, and for infinitely many MM, Jerry wins.
Proposed by Anant Mudgal
functionalgebracombinatorics