IMO Shortlist 2011, Number Theory 4

11202012, 11:54 AM
Post: #1




IMO Shortlist 2011, Number Theory 4
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+2a1)t(n+a1)\] are divisible by 4. Proposed by Gerhard Wöginger, Austria $\quad$ src 

11202012, 12:20 PM
Post: #2




Solution by nunoarala: IMO Shortlist 2011, Number Theory 4
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^{k1}$. This integer is of the form $2^{k}x+2^{k1}$, with $x\in \mathbb{Z}$. Then, $t(n+a)t(n)=t(2^{k}x+2^{k}m+2^{k1})t(2^{k}x+2^{k1})=(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$. 

« Next Oldest  Next Newest »
