MathDB

5

Part of 2012 Finnish National High School Mathematics Competition

Problems(1)

Collatz function applied 40 times

Source: Finland 2012, Problem 5

5/5/2013
The Collatz's function is a mapping f:Z+→Z+f:\mathbb{Z}_+\to\mathbb{Z}_+ satisfying f(x)=\begin{cases} 3x+1,& \mbox{as }x\mbox{ is odd}\\ x/2, & \mbox{as }x\mbox{ is even.}\\ \end{cases} In addition, let us define the notation f1=ff^1=f and inductively fk+1=f∘fk,f^{k+1}=f\circ f^k, or to say in another words, fk(x)=f(…(f⏟k times(x)…).f^k(x)=\underbrace{f(\ldots (f}_{k\text{ times}}(x)\ldots ).
Prove that there is an x∈Z+x\in\mathbb{Z}_+ satisfying f40(x)>2012x.f^{40}(x)> 2012x.
functioninductionnumber theory unsolvednumber theory