Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2013 AIME II Problems/Problem 14"

(Problem 14)
 
Line 1: Line 1:
 
For positive integers <math>n</math> and <math>k</math>, let <math>f(n, k)</math> be the remainder when <math>n</math> is divided by <math>k</math>, and for <math>n > 1</math> let <math>F(n) = \max_{\substack{1\le k\le \frac{n}{2}}} f(n, k)</math>. Find the remainder when <math>\sum\limits_{n=20}^{100} F(n)</math> is divided by <math>1000</math>.
 
For positive integers <math>n</math> and <math>k</math>, let <math>f(n, k)</math> be the remainder when <math>n</math> is divided by <math>k</math>, and for <math>n > 1</math> let <math>F(n) = \max_{\substack{1\le k\le \frac{n}{2}}} f(n, k)</math>. Find the remainder when <math>\sum\limits_{n=20}^{100} F(n)</math> is divided by <math>1000</math>.
 +
 +
==Solution==
 +
 +
====Solution without strict proof====
 +
 +
We can find that
 +
 +
<math>20\equiv 6 \pmod{7}</math>
 +
 +
<math>21\equiv 5 \pmod{8}</math>
 +
 +
<math>22\equiv 6 \pmod{8}</math>
 +
 +
<math>23\equiv 7 \pmod{8}</math>
 +
 +
<math>24\equiv 6 \pmod{9}</math>
 +
 +
<math>25\equiv 7 \pmod{9}</math>
 +
 +
<math>26\equiv 8 \pmod{9}</math>
 +
 +
Observing these and we can find that the reminders are in groups of three continuous integers, considering this is true, and we get
 +
 +
<math>99\equiv 31 \pmod{34}</math>
 +
 +
<math>100\equiv 32 \pmod{34}</math>
 +
 +
So the sum is <math>5+3\times(6+...+31)+32\times 2=1512</math>, so the answer is <math>\boxed{512}</math>

Revision as of 03:48, 5 April 2013

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) = \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$.

Solution

Solution without strict proof

We can find that

$20\equiv 6 \pmod{7}$

$21\equiv 5 \pmod{8}$

$22\equiv 6 \pmod{8}$

$23\equiv 7 \pmod{8}$

$24\equiv 6 \pmod{9}$

$25\equiv 7 \pmod{9}$

$26\equiv 8 \pmod{9}$

Observing these and we can find that the reminders are in groups of three continuous integers, considering this is true, and we get

$99\equiv 31 \pmod{34}$

$100\equiv 32 \pmod{34}$

So the sum is $5+3\times(6+...+31)+32\times 2=1512$, so the answer is $\boxed{512}$

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2013_AIME_II_Problems/Problem_14&oldid=52139"