• 0 Votes - 0 Average
• 1
• 2
• 3
• 4
• 5
 IMO Shortlist 2011, Number Theory 4
11-20-2012, 11:54 AM
Post: #1
 elim Moderator     Posts: 578 Joined: Feb 2010 Reputation: 0
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+2a-1)-t(n+a-1)$ are divisible by 4.

Proposed by Gerhard Wöginger, Austria $\quad$ src
11-20-2012, 12:20 PM
Post: #2
 elim Moderator     Posts: 578 Joined: Feb 2010 Reputation: 0
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^{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$.
 « Next Oldest | Next Newest »

Forum Jump: