IMO Shortlist 2011, Number Theory 4 - Printable Version +- OMath! ( http://math.elinkage.net)+-- Forum: Math Forums ( /forumdisplay.php?fid=4)+--- Forum: Number Theory ( /forumdisplay.php?fid=7)+--- Thread: IMO Shortlist 2011, Number Theory 4 ( /showthread.php?tid=702) |

IMO Shortlist 2011, Number Theory 4 - elim - 11-20-2012 11:54 AM
For each positive integer $k,$ let $t(k)$ be the largest odd divisor of $k.$ Determine all positive integers $a$ for which there exists a positive integer $n,$ such that all the differences \[t(n+a)-t(n); t(n+a+1)-t(n+1), \ldots, t(n+2a-1)-t(n+a-1)\] are divisible by 4. Proposed by Gerhard Wöginger, Austria $\quad$ src Solution by nunoarala: IMO Shortlist 2011, Number Theory 4 - elim - 11-20-2012 12:20 PM
For any positive integer $a$, let $S_{a}:=\{n:4\mid t(n+a)-t(n)\}$. The problem is equivalent to finding the values of $a$ for which $S_{a}$ contains $a$ consecutive elements. 1st case: $a$ is even. Let $a=2^{k}m$, where $k\geq 1$ and $m$ is odd. Since $a=2^{k}m\geq 2^{k}$, among $a$ consecutive integers there must be one whose remainder upon divison by $2^{k}$ is $2^{k-1}$. This integer is of the form $2^{k}x+2^{k-1}$, with $x\in \mathbb{Z}$. Then, $t(n+a)-t(n)=t(2^{k}x+2^{k}m+2^{k-1})-t(2^{k}x+2^{k-1})=(2x+2m+1)-(2x+1)=2m$. So if $S_{a}$ contains $a$ consecutive elements, we must have $4\mid 2m$, which contradicts the oddness of $m$. Therefore there are no solutions with $a$ even. 2nd case: $a$ is odd. For $a=1$ take $n=4$; for $a=3$ take $n=1$; for $a=5$ take $n=4$. Now let's prove that $a=7$ is not a solution. Among $7$ consecutive integers, exactly one remainder modulo $8$ doesn't appear. So there is either an integer of the form $8x+3$ or an integer of the form $8x+6$. If there is an integer of the form $8x+3$, then we must have $4\mid t(8x+10)-t(8x+3)=(4x+5)-(8x+3)=-4x+2$, which is absurd. If there is an integer of the form $8x+6$, then we must have $4\mid t(8x+13)-t(8x+6)=(8x+13)-(4x+3)=4x+10$, which is absurd. Now assume $a>8$. Among $a$ consecutive integers there is one of the form $8x+2$ and one of the form $8x+6$. If $a=4m+1$, then we must have $4\mid t(8x+4m+3)-t(8x+2)=(8x+4m+3)-(4x+1)=4x+4m+2$, which is absurd. If $a=4m+3$, then we must have $4\mid t(8x+4m+9)-t(8x+6)=(8x+4m+9)-(4x+3)=4x+4m+6$, which is absurd. The solutions are $a=1$, $a=3$ and $a=5$. |