Let $n$ be a positive integer. Let $s: \mathbb N \to \{1, \ldots, n\}$ be a function such that $n$ divides $m-s(m)$ for all positive integers $m$. Let $a_0, a_1, a_2, \ldots$ be a sequence such that $a_0=0$ and \[a_{k}=a_{k-1}+s(k) \text{ for all }k\ge 1.\]Find all $n$ for which this sequence contains all the residues modulo $(n+1)^2$. Proposed by N.V. Tejaswi
Problem
Source: India IMOTC 2024 Day 2 Problem 1
Tags: abstract algebra, number theory
31.05.2024 07:43
Will post solulu later ( in an hour) ; this was the only problem I completely solved.
31.05.2024 08:09
02.06.2024 16:46
02.06.2024 18:41
Nice one ! Then answer is $n+1$ is a power of two. Let's see that $a_k=s(0)+s(1)+\dots+s(k)$ so basically a term it is of the form $1+2+\dots+n+1+2+\dots+n+\dots+1+2+\dots+j$ where $0\le j\le n-1$ and the block $1,2,\dots n$ appears $k$ times So all of the terms are of the form $\frac{kn(n+1)}{2}+\frac{j(j+1)}{2}$ and the problem asks which $n$ have the property that all of the terms above span all residues classes mod $(n+1)^2$ We need the following claim: Claim: $n+1$ is even. Suppose by contradiction that it is odd.Then for each $r\in \{0,1,\dots n\}$ there exist $k$ and $j$ such that $(n+1)^2\mid \frac{kn(n+1)}{2}+\frac{j(j+1)}{2}$ so $(n+1)^2\mid kn(n+1)+j(j+1)-2r$ so $n+1\mid j(j+1)-2r$. But $j(j+1)$ spans at most $n$ residues,and $2r$ spans $n+1$ residues which is a contradiction $\blacksquare$ Let $n=2t-1$ and let's prove that $t$ is a power of two. We have that for each $r\in \{0,\dots 4t^2-1\}$ there exist $k\in \mathbb{N}$ and $0\le j\le n-1$ such that $4t^2\mid kt(2t-1)+\frac{j(j+1)}{2}-r$ But let's see that this is equivalent that for each $r$ there exist an $j$ such that $t\mid \frac{j(j+1)}{2}-r$. the first implication is easy because $t\mid kt(2t-1)$ and for the other implication use that $(2t-1,4t)=1$ so it has an inverse so you can find $k$ Define $f(j)=\frac{j(j+1)}{2}$ when $0\le j \le 2t-2$.observe that $f(j)\equiv f(2t-1-j) \pmod t$.so it suffices to consider $0\le j\le t-1$.so the problem becomes whcih $t$ have the property that $f$ is surjective mod $t$.But this is equivalent to $f$ being an injection. So $\frac{j(j+1)}{2} \equiv \frac{l(l+1)}{2} \pmod t \to j\equiv l \pmod t$. But this is equivalent with $2t\mid (j-l)(j+l+1) \to t\mid j-l$ If $t$ is a power of two then since exactly one of $j-l,j+l+1$ is even,$2t$ divides exactly one of them.But by bounding we get a contradiction so it works. If $t=2^m\cdot s$ where $s\ge 3$ is odd take $j=\frac{2^{m+1}+s-1}{2}$ and $l=\frac{|s-2^{m+1}|-1}{2}$.Then $j-l=min\{2,2^{m+1}\};j+l+1=max\{s,2^{m+1}\} $ so their product is $2t$ and their difference is not divisible by $t$ so we are done !! Comment:technical problem,but the ideas are easy to get and the calculation is not hard
15.06.2024 14:12
Rijul saini wrote: Let $n$ be a positive integer. Let $s: \mathbb N \to \{1, \ldots, n\}$ be a function such that $n$ divides $m-s(m)$ for all positive integers $m$. Let $a_0, a_1, a_2, \ldots$ be a sequence such that $a_0=0$ and \[a_{k}=a_{k-1}+s(k) \text{ for all }k\ge 1.\]Find all $n$ for which this sequence contains all the residues modulo $(n+1)^2$. Proposed by N.V. Tejaswi Let $x=an+b$ then we can see that $a_x=a\frac{n(n+1)}{2}+\frac{b(b+1)}{2}$ If $n=even$ then $a_{n(n+1)}=(n+1)\frac{n(n+1)}{2}\equiv 0(mod(n+1)^2))$ so in this case the sequanse haw period $n(n+1)$ so it can not contain all the residues modulo $(n+1)^2$. For $n=odd$ we have $n+1=2m+2$ we now can see that : $a\frac{n(n+1)}{2}=an(m+1)(mod (2m+2)^2)$ and since $(n,4m+2)=1$ we have that $a\frac{n(n+1)}{2}$ can take all the form $c*(m+1)(mod (2m+2)^2)$ So $\frac{b(b+1)}{2}$ should can take all residues $0,1,2,3,..,m(mod (m+1))$. If an odd prime number $p|m+1$ then we have contradiction since: $\frac{b(b+1)}{2}\equiv \frac{(-1-b)(1+(-1-b))}{2}(mod m+1)$ So $m+1=2^l$ then:$\frac{b(b+1)}{2}\equiv \frac{c(c+1)}{2}(mod(m+1))\Leftrightarrow m+1=2^l|\frac{(b-c)(b+c+1)}{2}$ From here esily we can see that $b=c$ so all $n+2^k-1$ works.
18.06.2024 06:24