Problem

Source: Iranian National Olympiad (3rd Round) 2007

Tags: floor function, number theory proposed, number theory



We call the mapping $ \Delta:\mathbb Z\backslash\{0\}\longrightarrow\mathbb N$, a degree mapping if and only if for each $ a,b\in\mathbb Z$ such that $ b\neq0$ and $ b\not|a$ there exist integers $ r,s$ such that $ a = br+s$, and $ \Delta(s) <\Delta(b)$. a) Prove that the following mapping is a degree mapping: \[ \delta(n)=\mbox{Number of digits in the binary representation of }n\] b) Prove that there exist a degree mapping $ \Delta_{0}$ such that for each degree mapping $ \Delta$ and for each $ n\neq0$, $ \Delta_{0}(n)\leq\Delta(n)$. c) Prove that $ \delta =\Delta_{0}$