Problem:
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)=max1≤k≤2nf(n,k). Find the remainder when ∑n=20100F(n) is divided by 1000.
Solution:
If m>1, then
f(3m,m+1)f(3m+1,m+1)f(3m+2,m+1)=m−2,=m−1, and =m
Furthermore,
f(3m,k)f(3m,m−1)f(3m,m)f(3m,k)<m−2 for k≤m−2,=3,=0, and =3m−2k<m−2 for m+1<k≤23m.
Therefore F(3m)=m−2. Because F(n+1)≤F(n)+1 for all n, it follows that F(3m+1)=m−1 and F(3m+2)=m. Thus
n=20∑100F(n)=m=7∑33(F(3m−1)+F(3m)+F(3m+1))=m=7∑33((m−1)+(m−2)+(m−1))=3m=7∑33(m−1)−27=3⋅227(6+32)−27=1512.
The requested remainder is 512.
The problems on this page are the property of the MAA's American Mathematics Competitions