For a positive integer $n$, let $R(n)$ be the sum of the remainders when $n$ is divided by $1,2, \cdots , n$. For example, $R(4) = 0 + 0 + 1 + 0 = 1,$ $R(7) = 0 + 1 + 1 + 3 + 2 + 1 + 0 = 8$. Find all positive integers such that $R(n) = n-1$.
Problem
Source: RMO 2024 Q2
Tags: number theory, Bounding
03.11.2024 13:58
Bound $n$, then check for remaining $n$.
03.11.2024 14:09
lol, look at AMC 12B 2021 P25, it basically asks R(N)=R(N+1) for 2 digit numbers, did that problem a few months ago,
03.11.2024 14:16
trivial, check n/2 + 1, n/2 + 2, n/2 + 3, ..., n - 1 do the same for n. odd with n-1/2
03.11.2024 14:26
alexanderhamilton124 wrote: trivial, check n/2 + 1, n/2 + 2, n/2 + 3, ..., n - 1 Us bro.
03.11.2024 14:26
Check remainders when $n$ is divided by $[n/2],[n/2]+1,.......n-1$ , prove their sum greater than $n$ for $n\geq 10$ Now case check to get $n=1,5$.
03.11.2024 14:59
We see that $n=1$ works. Henceforth, suppose $n>1$. For even $n$, consider the positive integers $\frac{n}{2}+1, \frac{n}{2}+2, \frac{n}{2}+3$. The remainders when $n$ is divided by these integers are $\frac{n}{2}-1, \frac{n}{2}-2, \frac{n}{2}-3$, respectively. But then, for $n>10$, we have $R(n)\geq \frac{3n}{2}-6>n-1$, so $n\leq 10$ is forced. Checking the cases, we see that no such even $n$ exists. For odd $n$, consider the positive integers $\frac{n+1}{2}, \frac{n+1}{2}+1, \frac{n+1}{2}+2$. The remainders when $n$ is divided by these integers are $\frac{n-1}{2}, \frac{n-1}{2}-1, \frac{n-1}{2}-2$, respectively. But then, for $n>7$, we have $R(n)\geq \frac{3(n-1)}{2}-3>n-1$, so $n\leq 7$ is forced. Checking the cases, we see that only $n=5$ works. Therefore, the answer is $\boxed{n=1, 5}$ only.
03.11.2024 15:42
From the OMC RMO livesolve. solved with rawlat_vanak, AdhityaMV, zvfrozel, and mathscrazy. Denote $k = \left\lfloor \frac{n}{2} \right\rfloor + 1$. We note that for all $k \leq x \leq n$ we have $n (\bmod x) = n-x$. As a result, we have \[R(n) = \sum \limits_{i = 1}^{n} {n (\bmod ~ i)} \geq \sum \limits_{i = k}^{n} (n-i) = \binom{\left \lceil \frac{n}{2} \right \rceil}{2}\]If $R(n) = n-1$, we therefore obtain $n \leq 9$. Checking all $n$ from $1$ through $9$, we obtain that the only two values that fit are $n \in \{1,5\}$. $\square$
04.11.2024 18:09
Do we need to include the manual checking from 1 to 9 in the answer sheet?Otherwise how much marks would be deducted
04.11.2024 20:06
In this question I found all value $R(n)$ from $n=1 to 20$ Then there was a special sequence formed in the second half of the sum and it went like $0+1+2+3+....$ So I wrote, "With observation in the sum of $R(n)$ in the second half of the sum is a sequence with sum $\frac{k(k+1)}{2}$. I proved that if n is even then the second half will be like $1+2+3+..........(\frac{n-2}{2})$ which gave me sum of this half as$( \frac{n-2}{2})(\frac{n}{2})$ Now, $R(n) >( \frac{n-2}{2})(\frac{n}{2})$ Got a quadratic solved it and got it as $n^2-2n+8<0$
Again I proved that for n is odd the second half is like $1,2,3...\frac{n-1}{2}$ Again got a quadractic $\frac{n^2}{7}-\frac{8n}{7}+1<0$ From here i got two values of n= ${{1,5}}$.
04.11.2024 20:08
L_BarySaneTan37 wrote: Do we need to include the manual checking from 1 to 9 in the answer sheet?Otherwise how much marks would be deducted It depends on many factors. First is examiner. Second, If you somewhere mentioned, by observation we get this. SO it is always better to mention it. Well can't say anything here.
05.11.2024 11:20
ez bounding problem got n >= 10 (not works) then n = 1 , 5
05.11.2024 13:27
$OG!$ I will try to write as far as I remember the exact same quotation as I did in the contest We denote by $r_i(N)$, the remainder when $N$ is divided by $i$, so $R(n)= r_1(n)+r_2(n)+ \cdots r_n(n)$ Case1: $n>10$ Case1a: $n$ is even Set $n=2k$ observe that $r_{k+1}(2k) = k-1$ $r_{k+2}(2k) = k-2$ $\cdots$ $r_{2k-1}(2k) = 1$ So $2k-1=R(n)=R(2k)=r_1(2k)+r_2(2k)+ \cdots r_{2k}(2k) \geq r_{k+1}(2k)+ r_{k+2}(2k) + \cdots r_{2k-1}(2k) = k-1+k-2 \cdots 1 = \frac{k(k-1)}{2}$ as $R(n)=n-1$. So $2k-1 \geq \frac{k(k-1)}{2} \iff 0 \geq k^2-5k+2= k(k-5)+2$ But, since, $n>10 \implies 2k >10 \implies k>5 \implies 0 \geq k(k-5)+2>2 \implies 0>2.$ A contradiction! Hence, no solutions Case1b: $n$ is odd Set $n=2k+1$ observe that $r_{k+1}(2k+1) = k$ $r_{k+2}(2k+1) = k-1$ $\cdots$ $r_{2k}(2k+1) = 1$ So $2k=R(n)=R(2k+1)=r_1(2k+1)+r_2(2k+1)+ \cdots r_{2k+1}(2k+1) \geq r_{k+1}(2k+1)+ r_{k+2}(2k+1) + \cdots r_{2k}(2k+1)=k+k-1+k-2 \cdots 1 = \frac{k(k+1)}{2}$ as $R(n)=n-1$. So, $2k \geq \frac{k(k+1)}{2} \iff 0 \geq k^2-3k= k(k-3)$ But, since $n>10 \implies 2k+1 >10 \implies k>4.5 \implies k>4 \implies 0 \geq k(k-3)>0 \implies 0>0.$ A contradiction! Hence, no solutions Thus, $n \leq 10$ Now, on checking for $n=1,2,3 \cdots 10$ We easily get $n=1$ and $n=5$ as the only solutions.