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
Problem
Source: IMO Shortlist 2011, Number Theory 4
Tags: number theory, IMO Shortlist, combinatorics
nunoarala
12.07.2012 06:08
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$.
ISHO95
09.01.2013 19:36
answer the problem $a=1,3,5$.
bobthesmartypants
11.07.2016 05:44
Case 1: $a\equiv 0\pod{2}$
Case 1a) If $a\equiv 2\pod{4}$: if $n$ is odd then $n\equiv 1,3\pod{4}$ while $n+a\equiv 3,1\pod{4}$ so $t(n+a)-t(n)\equiv 2\pod{4}$ contradiction. The same logic holds with $n+1$ and $n+a+1$ if $n$ is even.
Case 1b) If $a\equiv 4\pod{8}$: the differences are $t(k+i)-t(k)$ where $i\equiv 4\pod{8}$. Consider $k,k+i\equiv 2\pod{4}$. Since $v_2(k)=v_2(k+i)=1$, $t(k)=\dfrac{k}{2}, t(k+i)=\dfrac{k+i}{2}$ so $\dfrac{k}{2}\equiv \dfrac{k+i}{2}\pod{4}\iff k\equiv k+i\pod{8}\iff i\equiv 0\pod{8}$ contradiction.
Case 1c) If $a\equiv 0\pod{8}$: now the previous contradiction no longer holds. In addition, when $k$ is odd $k+i\equiv k\pod{8}\implies t(k+i)\equiv t(k)\pod{8}$ which works. What remains is to consider $k\equiv 0\pod{4}$. In this case $t(k)=t\left(\dfrac{k}{4}\right), t(k+i)=t\left(\dfrac{k+i}{4}\right)$ so we can reduce the problem to when $a\mapsto \dfrac{a}{4}$. In particular, any case where $v_2(a) \ge 3$ reduces to the truth of a case when $v_2(a)=1,2$; but we know that there are no solutions in these cases so the evens have no solutions.
Case 2: $a\equiv 1\pod{2}$
We do the arithmetic combined for $a\equiv 1\pod{4}$ and $a\equiv 3\pod{4}$, with them differentiated by a semicolon. We have differences of the form $t(k+i)-t(k)$ where $i\equiv 1;3\pod{4}$. Consider when $k\equiv 2\pod{4}$: Then $k+i\equiv 3;1\pod{4}\implies t(k+i)\equiv 3;1\pod{4}\implies t(k)\equiv 3;1\pod{4}$. Since $v_2(k)=1$, $t(k) \equiv 3;1\pod{4}\implies \dfrac{k}{2}\equiv 3;1\pod{4}\implies k\equiv 6;2\pod{8}\quad (*)$.
However, notice that for $a\ge 9;11$, there exists $k_1,k_2\in [n, n+a-1]$ such that $k_1\equiv k_2\equiv 2\pod{4}$ and $|k_1-k_2|=4$; but this means $k_1\equiv k_2\equiv 6;2\pod{8}$ contradiction with $|k_1-k_2|=4$. Thus, it remains to check $a=1, 3, 5, 7$.
It is easy to see $a=7$ does not work because if there does not exist $k_1, k_2\in [n, n+a-1]$ with the above property there certainly does exist $k_1, k_2\in [n+a, n+2a-1]$ contradiction.
For $a=1$ and $a=3$, $n=1$ works. For $a=5$, $n=4$ works. Thus, our only solutions are $\boxed{a=1,3,5}$
rterte
12.09.2016 14:38
2011 N4 seems to be the easiest number theory problem in 2011 ISL.
Kayak
24.08.2017 19:36
Someone please proofread my crappy solution (BTW, I have seen lot harder N1 than this)
Note: (a) There's only two possible values of $t \; (modulo \; 4)$: they are $1$ and $3$. (b) For two consecutive odds $c, c+2$, $t(c)$ and $t(c+2k)$ are not equivalent modulo $4$ for any $k$ odd, $t(c+4k) \equiv t(c)$ for any integer $k$ (c) $t(2^k c) = t(c)$, for any $k, c$.
It's trivial to see $a \in \{1,3,5\}$ is a valid set of solutions (check $n=1$, $a=1,3$ and $n=3$, $a=5$), and we claim these are the only one, i.e:
Claim: For any positive integer $n$ and integer $a > 5$, there exists $n \leq i < i+a \leq n+2a-1$ such that $t(i) \equiv t(i+a) + 2 \; \; (modulo \; 4)$, i.e $t(i)$ not equivalent to $t(i+a)$ modulo $4$.
ProofLet $v_2(i)$ denotes the highest power of $2$ dividing $i$. We consider the three possible cases:
Case-1: $a = 2^k$, i.e $a$ is a perfect power of $2$.
ProofIn any $2^k$ consecutive integers, there's one integer $i$ such that $i \equiv 2^{k-1} \; \; (modulo 2^k)$, so $v_2(i) = k-1$, let $i = 2^{k-1}c$, where $2 \nmid c$. Now, $t(i+2^k) = t(2^{k-1}c+2^{k-1}(2)) = t(2^{k-1} (c+2))= t(c+2)$, and $t(i) = t(c)$. Now, as $c$ is odd, $t(c)$ is not equivalent to $t(c+2)$ modulo $4$ (from Note)
Case-2: $a=2^k c$, where $k > 0$ and $ 2 \nmid c$.
ProofNote that $a \equiv 2^{k} \; \; (modulo 2^{k+1})$. Now, from any $a$ consecutive integers, we can pick an integer $i$ such that $i \equiv 2^{k-1} \; \; (modulo 2^{k} )$, so $i = 2^{k-1}c'$, where $2 \nmid c'$. Now, $t(i) = t(2^{k-1} c')= t(c')$, and $t(i+a) = t(2^{k-1}c'+2^{k}c) = t(2^{k-1}(c+2c')) = t(c+2c')$. Now, from Note, we're done.
Case-3: $a=c$, where $c>5$ and $2 \nmid c$.
ProofAs $a \geq 7$, we can choose odd integers $i, i+4$ from $n, \cdots, n+a$ such that both $i+a, i+a+4$ is in the range, such that $i+a = 2*c_1$, and $i+a+4 = 2(c_1+2)$, where $2 \nmid c_1, c_1+2$. Now, let WLOG $t(i) \equiv t(i+a) = t(2c_1) = 1$. Then, $t(i+4) \equiv 1$, but $t(i+a+4) = t(2(c_1+2)) = t(c_1+2)$, and from Note, we're done, because by construction both $c_1$ and $c_1+2$ are odd.
And it's trivial to check from Note that $a=2,4$ is impossible.
blacksheep2003
09.10.2020 17:09
The answer is $a = 1$, $3$, $5$. We see that these work by choosing $n = 1$, $11$, $4$, respectively. We now show that there are no other solutions.
We consider cases of $a$ mod $4$
Case I: $a \equiv 0$ mod $4$
Assume, for the sake of contradiction, that $a$ has the property in question. Let $2^k$ be the largest power of $2$ dividing $a$. Therefore, we can choose $c < a$ such that $n + c \equiv n + c + a \equiv 2^{k - 1}$ mod $2^k$. Then, $4|t(n + c + a) - t(n + c) = \frac{n + c + a}{2^{k - 1}} - \frac{n + c}{2^{k - 1}} = \frac{a}{2^{k - 1}}$, so we find that $2^{k + 1}|a$, which contradicts our assumption that $2^k$ was the largest power of $2$ dividing $a$.
Case II: $a \equiv 1$ mod $4$
We already know that $a = 1$, $a = 5$ works, so assume $a > 5$ and $a$ satisfies the property in question. Therefore, we can choose $c < 4$ such that $n + c \equiv 1$ mod $4$, $n + c + a \equiv 2$ mod $4$. Then, $4|t(n + c + a) - t(n + c) = \frac{n + c + a}{2} - (n + c) = \frac{a - (n + c)}{2}$, so we find that $8|a - (n + c)$. However, replacing $c$ with $c + 4$ yields similar results, so we obtain $8|a - (n + c + 4)$ as well, which is a contradiction.
Case III: $a \equiv 2$ mod $4$
Assume, for the sake of contradiction, that $a$ has the property in question. Therefore, we can choose $c < a$ such that $n + c$, $n + c + a$ are odd. Then, $4|t(n + c + a) - t(n + c) = (n + c + a) - (n + c) = a$, which is a contradiction.
Case IV: $a \equiv 3$ mod $4$
We already know that $a = 3$ is a solution, so assume $a > 3$ and $a$ satisfies the property in question. Therefore, we can choose $c < 4$ such that $n + c \equiv 2$ mod $4$, $n + c + a \equiv 1$ mod $4$. Then, $4|t(n + c + a) - t(n + c) = n + c + a - \frac{n + c}{2} = a + \frac{n + c}{2}$, so we find that $8|n + c + 2a$. Furthermore, $n + c + 1 \equiv 3$ mod $4$, $n + c + 1 + a \equiv 2$ mod $4$, and $4|t(n + c + 1 + a) - t(n + c + 1) = \frac{n + c + 1 + a}{2} - (n + c + 1) = \frac{a - (n + c + 1)}{2}$, hence $8|a - (n + c + 1)$, but since $8|n + c + 2a$ also, this gives us $8|3a - 1$, so $a \ne 7$. Then, $a > 7$, so replacing $c$ with $c + 4$, we obtain similarly $8 |n + c + 4 + 2a$, which is a contradiction.
Thus, we have shown that $a = 1$, $3$, $5$ are the only solutions, as desired $\blacksquare$
bora_olmez
25.06.2021 20:28
A bit disappointed that there was no cool construction involved in the problem. Solved with L567
We claim that the answer is only $a=1,3,5$.
$\textbf{Claim:}$ $a \equiv 0 \pmod{2}$ doesn't work.
$\textbf{Proof)}$
Write $a=2^lb$ (assume for now that $b \neq 1$) for maximal $l$ (i.e, $b$ - odd).
Pick $k \in \{n,...,n+a-1\}$ such that $k = 2^{l-1}m$ such that $m$ is odd.
Notice that there exists such an $l$ because $\{n,...,n+a-1\}$ is surjective $\pmod{2^l}$ and we can therefore pick $k \equiv 2^{l-1} \pmod{2^l}$ from which we have:
$$t(2^{l-1}(2b+m))-t(2^{l-1}m) = 2b$$Notice that $b$ is odd and we get a contradiction. $\square$
$\textbf{Claim:}$ If $a \equiv 1 \pmod{2}$ and $a \geq 9$, then $a$ also doesn't work.
$\textbf{Proof)}$
Take $b \in \{n,..,n+a\}$ such that $b = 4k+2$ for some $k \in \mathbb{N}$ such that $4k+6$ is also in $\{n,...,n+a\}$, then we have that $t(4k+2+a) - t(4k+2) = 2k+1+a$ and $t(4k+6+a)-t(4k+6) = 2k+3+a$ from which we get an immediate contradiction. $\square$
We therefore have to check $a \in \{1,3,5,7\}$ and we get that only $a=1,3,5$ work using $n=32769,8193,131076$. $\blacksquare$
IAmTheHazard
15.05.2022 19:13
Fake problem The answer is $a=1,3,5$, which work by using $n=1,1,4$ respectively. We consider the following two cases. Case 1: $a$ is even. Then let $k=\nu_2(a)>0$ and write $a=2^kb$. Among any $a$ consecutive integers, one must have $\nu_2$ equal to $k-1$, so it's of the form $2^km+2^{k-1}$. Then, $t(2^km+2^{k-1})=2m+1$, and $t(2^km+2^{k-1}+a)=t(2^k(b+m)+2^{k-1})=2(b+m)+1$, so their difference is $2b$. As $b$ is odd this means $4 \nmid 2b$, contradiction. So we get no solutions for this case. Case 2: $a$ is odd. Then let $a=2b+1$. Suppose there exists some term $x$ in $n,\ldots,n+a-1$ such that $x \equiv 2 \pmod{8}$. Then $t(x)=\tfrac{x}{2}$, and $t(x+a)=x+a$, so we require $4 \mid x+a-\tfrac{x}{2} \implies 8 \mid x+2a \implies 8 \mid 2a+2$. Likewise if there exists some term $y \equiv 6 \pmod{8}$, we require $8 \mid 2a+6$. But these cannot simultaneously be satisfied, so we immediately obtain $a \leq 8$ (else $n,\ldots,n+a-1$ covers all residues modulo $8$). It remains to eliminate $a=7$. We only have to consider $n \equiv 3,7 \pmod{8}$, otherwise $n,\ldots,n+a-1$ will cover both $2$ and $6$ modulo $8$. In this case, there exists some term $z \equiv 3 \pmod{8}$, so $t(z)=z$ and $t(z+a)=\tfrac{z+7}{2}$ as $z+a \equiv 2 \pmod{8}$. But then we require $4 \mid z-\tfrac{z+7}{2} \implies 8 \mid z-7$, which is impossible. Thus $a=7$ does not work, so we are left with $a=1,3,5$ as desired. $\blacksquare$
awesomeming327.
14.04.2023 15:50
If $2\mid a$ let $\nu_2(a)=k$. Since $a\ge 2^k$, we can always find $0\le i\le a-1$ such that $n+a+i$, $n+i\equiv 2^{k-1}\pmod {2^k}$. Then, \[\nu_2\left(t(n+a+i)-t(n+i)\right)=\nu_2\left(\frac{n+a+i}{2^{k-1}}-\frac{n+i}{2^{k-1}}\right)=\nu_2\left(\frac{a}{2^{k-1}}\right)=1\]so evens don't work. $~$ If $2\nmid a$ and $a\ge 7$ then we can always find two values $0\le i\le a-1$ such that $n+i\equiv 2\pmod 4$ or two consecutive values that $n+a+i\equiv 2\pmod 4$. Both are basically the same thing, so let it be the former. Let $n+i$ and $n+i+4$ be our two values $\equiv 2\pmod 4$. $~$ Note that $n+a+i$ is odd, so $t(n+a+i+4)\equiv t(n+a+i)\pmod 4$. It is clear that $t(n+i+4)\not\equiv t(n+i)\pmod 4$ so the differences cannot both be zero. Thus, only $a=1$, $3$, $5$ can work. They do work, when $n=1$, $1$ and $4$ respectively.
sman96
30.05.2023 16:40
$\boxed{\textbf{Claim 1: } a \text{ can't be even.}}$ $\underline{\text{Proof:}}$ Let, $a = 2^xk$ where $k$ is an odd number. Now, $\exists m\in\{n, n+1, \dots, n+a-1\}$ s.t. $m\equiv 2^{x-1}\pmod{2^x}$. Therefore, $m = 2^{x-1} + 2^xd$. Now, \begin{align*} t(m+a)-t(m) &= t(2^{x-1} + 2^xd + 2^xk) - t(2^{x-1} + 2^xd)\\ &= (1+2d+2k)-(1+2d)\\ &= 2k \end{align*}But, $2k \equiv 2 \not\equiv 0 \pmod 4$. So, our claim is proved. $\square$ $\boxed{\textbf{Claim 1: } a < 6 \text{.}}$ $\underline{\text{Proof:}}$ FTSOC, let $a \geq 6$. Then one of, $\{n, n+1, \dots, n+a-1\}$ and $\{n+a, \dots, n+2a-1\}$ will have at least two element congruent to $2\pmod 4$. Case 1: two of $\{n, n+1, \dots, n+a-1\}$ are $2\pmod4$. Let two of them be, $2k, 2k+4$. Then, \begin{align*} t(2k+a)-t(2k) &= 2k+a - k\\ &= k+a \end{align*}And, \begin{align*} t(2k+4+a)-t(2k+4) &= 2k+4+a - k - 2\\ &= k+a+2 \end{align*}Clearly, both of them can't be divisible by $4$. Case 2: two of $\{n+a, \dots, n+2a-1\}$ are $2\pmod4$. Similar to Case 1, take $2k-a$ and $2k+4-a$. So, This claim is also proved. $\square$ Now, for $a\in \{1,3\}$ we take $n=1$. And for $a = 5$ we just take $n = 4$ and we are done. $\blacksquare$
signifance
18.09.2023 04:50
Easy but also a super fun problem (initially I misread as largest odd prime and I was like what the -) The key is to get rid of all a even; from there it's much easier to compute mod 4 since odd divisors are easy. Indeed, if a is even let $v_2(a)=k$, and take $i:n+a+i\equiv n+i\equiv 2^{k-1}\pmod{2^k}$ (we know there exists i since $a\ge 2^k$ so i can go over all residues). There is now a direct contradiction (we were motivated earlier since now we can definitively find odd divisor) since $$v_2(t(a+n+i)-t(n+i))=v_2(\frac{a+n+i}{2^{k-1}}-\frac{n+i}{2^{k-1}})=1.$$Now, if $a\ge 7$ is odd, take i=2 mod 4 and i'=i+4 both in the set: $t(a+4k+2)-t(4k+2)=a+2k+1$, so to satisfy problem we would need $a=-2k-1\pmod 4$; on the other hand, $t(a+4k+6)-t(4k+6)=a+2k+3\Rightarrow a=-2k-3\pmod 4$, contradiction. To finish, note that a=1,3,5 all work with n=1,1,4.
sansgankrsngupta
16.07.2024 14:26
Try the modified problem : 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(a); t(n+a+1)-t(a+1), \ldots, t(n+2a-1)-t(2a-1)\]are divisible by 4.
L13832
17.07.2024 16:06
My proof is similar to the above ones ig becoz that was the most obvious way dealing mod 4 and for even it was straightforward contradiction.
Answer: $\boxed{a=1,3,5}$
Case I: a is even
Let $a=2^km$ here $k$ is taken to be maximum and $m$ is odd, and we want \[\displaystyle v_2(t(a+n+r)-t(n+r))=v_2\biggl(\frac{a+n+r}{2^{k-1}}-\frac{n+r}{2^{k-1}}\biggr)=1.\]for a contradiction.
So we need $n+r \equiv 2^{k-1} \pmod{2^k}$ but this is obviously true because we are going over remainders$\pmod{2^k}$.
Case II: a is odd
In the set $\{n,n+1,\dotsc,n+a-1\}$ if some numbers are $2\pmod 4$, they can be $4k+2$ and $4k+6$ (we do this to get a contradiction, I already tried for $1$ and $5$ $\pmod{4}$, didn't get a contradiction so....) so we have
$t(4k+2+a)-t(4k+2)=2k+1+a$ and
$t(4k+6+a)-t(4k+6)=2k+3+a$
which both cannot be divisible by $4$ so we get a contradiction when $a>6$.
Now checking for odd $a\leq 6$ we see that $a=1,3,5$