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}$
Problem
Source: Iranian National Olympiad (3rd Round) 2007
Tags: floor function, number theory proposed, number theory
Igor87
10.09.2007 21:04
I think there is a typo.It should be $ a\not|\ b$
Omid Hatami
10.09.2007 21:05
No, as I see, I am right.
Igor87
10.09.2007 21:31
Perhaps i'm misunderstanding If $ a=2$ $ b=4$ $ \Delta=\delta$ there sholud exist $ r,s$ such that $ 2=4r+s$ and $ \delta(s)<\delta(r)$ Now $ \delta(s)=\delta(2-4r)=\delta(2r-1)$ But it's easy to show that $ \delta(2r-1)\ge\delta(r)$ Where is the error?
Omid Hatami
10.09.2007 21:34
Oh it must be $ \Delta(s)\leq\Delta(b)$.
Rust
10.09.2007 21:41
Let $ b=2^{k},a=2^{k}+3,k\ge 3$, then $ s=3+(1-r)2^{k}$ and $ \delta(s)>\delta(b),\ \delta(s)>\delta(r)$.
Omid Hatami
10.09.2007 21:46
OK, but I don't think it proves the problem.
Omid Hatami
25.07.2008 12:40
Official Solution: For (a), let $ a,b\in\mathbb{Z}$ be such that $ b\neq0$ and $ b\nmid a$. Now divide $ a$ by $ b$ and write $ a = br' + s'$ where $ 0 < s' < |b|$. If $ s' < \frac {|b|}2$, then put $ r = r',s = s'$; and if $ s'\geq \frac {|b|}2$ then put $ r = r'\pm1,s' = s - |b|$. (the sign $ \pm$ is the same as $ b$'s sign) One can easily see that $ a = br + s$ and $ |s|\leq\frac {|b|}2$ which shows that $ \delta(s)\leq\delta(b) - 1$. For (b), let $ \Delta_0(n)$ be the minimum of $ \Delta(n)$ for every degree map $ \Delta$. It suffices to show that $ \Delta_0$ is a degree map. Given $ a,b$, there exists a degree map $ \Delta$ for which $ \Delta_0(b) = \Delta(b)$. Now take the $ r,s$ given by $ \Delta$. So $ a = br + s$ and $ \Delta(s) < \Delta(b)$. But then $ \Delta_0(s)\leq\Delta(s) < \Delta(b) = \Delta_0(b)$ which shows that this $ r,s$ work for $ \Delta_0$ too. Now for (c): For $ n = \pm1$, $ \delta(n)\geq\Delta_0(n)\geq1 = \delta(n)$ which shows that $ \delta(n) = \Delta_0(n)$. Let $ n$ be a number such that $ \Delta_0(n) < \delta(n)$. If there are many, choose one with the minimum $ \Delta_0(n)$. $ n\neq\pm1$ because of the previous result. Now take $ a = \lfloor\frac n2\rfloor$ and $ b = n$. Then $ b\nmid a$ because $ a\neq\pm1$. Let $ r,s$ be such that $ \Delta_0(s) < \Delta_0(n)$ and $ a = br + s$. Since $ \Delta_0(s) < \Delta_0(n)$, we have $ \Delta_0(s) = \delta(s)$. But it can be easily shown that whatever the value of $ s$ is, $ |s|\geq\lfloor\frac {|n|}2\rfloor$ which is at least $ \delta(n) - 1$. So $ \delta(n)\geq\Delta_0(n) > \delta(n) - 1$ which shows that $ \Delta_0(n) = \delta(n)$. A contradiction!