For positive integers $n$ and $k$, let $f(n, k)$ be the remainder when $n$ is divided by $k$, and for $n > 1$ let $F(n) =\displaystyle\max_{\substack{1\le k\le \frac{n}{2}}} f(n, k)$. Find the remainder when $\sum\limits_{n=20}^{100} F(n)$ is divided by $1000$.
Let's first do some observation.
- $F(20)=\displaystyle\max_{1<k\le 10}f(20,k)=f(20, 7)=6$ because $f(20,2)=0$, $f(20,3)=2$, $\cdots$, $f(20, 10) = 0$.
- $F(21)=\displaystyle\max_{1<k\le 10}f(21,k)=f(21, 8)=5$ because $f(21,2)=1$, $f(21,3)=0$, $\cdots$, $f(21, 10) = 1$.
- $F(22)=\displaystyle\max_{1<k\le 11}f(22,k)=f(22, 8)=6$ because $\cdots$.
- $F(23)=\displaystyle\max_{1<k\le 11}f(23,k)=f(23, 8)=7$ because $\cdots$.
- $F(24)=\displaystyle\max_{1<k\le 12}f(24,k)=f(24, 9)=6$ because $\cdots$.
- $F(25)=\displaystyle\max_{1<k\le 12}f(25,k)=f(25, 9)=7$ because $\cdots$.
- $F(26)=\displaystyle\max_{1<k\le 13}f(26,k)=f(26, 9)=8$ because $\cdots$.
- $\cdots$
The remainders, with the exception of the $F(20)$, appear to be in a group of $3$ consecutive integers with the first of each group increases by one: $$6, (5, 6, 7), (6, 7, 8), \cdots$$
Consider this is to be true, then
- $F(96) = 30$
- $F(97) = 31$
- $F(98) = 32$
- $F(99) = 31$
- $F(100) = 32$
It follows that $$F(20) + \cdots + F(100) = 6 + (5+6+7) + \cdots + (30 + 31+32)+31+32 = 1512$$
And the answer is $\boxed{512}$.
In order to prove the claim we made earl, i.e. the remainders are grouped in three, let's observe our trials above again. It appears that the $k$ which maximizes $F(n)$ also shows a pattern: $7, 8, 8, 8, 9, 9, 9, \cdots$.
We claim that $F(n)\displaystyle\max_{1<k\le \frac{n}{2}}f(n,k)$ has a solution $k=\lfloor{\frac{n}{3}}\rfloor$. If this holds, then the solution will complete. The proof is not difficult, but a bit tedious by a careful analysis of casework ($n\equiv 0, 1, 2\pmod{3}$). We will skip here.