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 "2023 AIME I Problems/Problem 10"

(Created page with "==Problem 10== There exists a unique positive integer <math>a</math> for which the sum <cmath>U=\sum_{n=1}^{2023}\left\lfloor\dfrac{n^{2}-na}{5}\right\rfloor</cmath> is an int...")
 
Line 3: Line 3:
  
 
(Note that <math>\lfloor x\rfloor</math> denotes the greatest integer that is less than or equal to <math>x</math>.)
 
(Note that <math>\lfloor x\rfloor</math> denotes the greatest integer that is less than or equal to <math>x</math>.)
 +
 +
==Bounds and Decimal Part Analysis==
 +
 +
Define <math>\left\{ x \right\} = x - \left\lfloor x \right\rfloor</math>.
 +
 +
First, we bound <math>U</math>.
 +
 +
We establish an upper bound of <math>U</math>. We have
 +
<cmath>
 +
\begin{align*}
 +
U & \leq \sum_{n=1}^{2023} \frac{n^2 - na}{5} \\
 +
& = \frac{1}{5} \sum_{n=1}^{2023} n^2 - \frac{a}{5} \sum_{n=1}^{2023} n \\
 +
& = \frac{1012 \cdot 2023}{5} \left( 1349 - a \right) \\
 +
& \triangleq UB .
 +
\end{align*}
 +
</cmath>
 +
 +
We establish a lower bound of <math>U</math>. We have
 +
<cmath>
 +
\begin{align*}
 +
U & =  \sum_{n=1}^{2023} \left(  \frac{n^2 - na}{5} - \left\{ \frac{n^2 - na}{5} \right\}  \right) \\
 +
& = \sum_{n=1}^{2023} \frac{n^2 - na}{5}
 +
- \sum_{n=1}^{2023} \left\{ \frac{n^2 - na}{5} \right\} \\
 +
& = UB -  \sum_{n=1}^{2023} \left\{ \frac{n^2 - na}{5} \right\} \\
 +
& \geq UB -  \sum_{n=1}^{2023} \mathbf 1 \left\{ \frac{n^2 - na}{5} \notin \Bbb Z \right\} .
 +
\end{align*}
 +
</cmath>
 +
 +
We notice that if <math>5 | n</math>, then <math>\frac{n^2 - na}{5} \in \Bbb Z</math>.
 +
Thus,
 +
<cmath>
 +
\begin{align*}
 +
U & \geq UB -  \sum_{n=1}^{2023} \mathbf 1 \left\{ \frac{n^2 - na}{5} \notin \Bbb Z \right\} \\
 +
& \geq UB -  \sum_{n=1}^{2023} \mathbf 1 \left\{ 5 \nmid n \right\} \\
 +
& = UB - \left( 2023 - \left\lfloor \frac{2023}{5} \right\rfloor \right) \\
 +
& = UB - 1619 \\
 +
& \triangleq LB .
 +
\end{align*}
 +
</cmath>
 +
 +
Because <math>U \in \left[ - 1000, 1000 \right]</math> and <math>UB - LB = 1619 < \left( 1000 - \left( - 1000 \right) \right)</math>, we must have either <math>UB \in \left[ - 1000, 1000 \right]</math> or <math>LB \in \left[ - 1000, 1000 \right]</math>.
 +
 +
For <math>UB \in \left[ - 1000, 1000 \right]</math>, we get a unique <math>a = 1349</math>.
 +
For <math>LB \in \left[ - 1000, 1000 \right]</math>, there is no feasible <math>a</math>.
 +
 +
Therefore, <math>a = 1349</math>. Thus <math>UB = 0</math>.
 +
 +
Next, we compute <math>U</math>.
 +
 +
Let <math>n = 5 q + r</math>, where <math>r = {\rm Rem} \ \left( n, 5 \right)</math>.
 +
 +
We have
 +
<cmath>
 +
\begin{align*}
 +
\left\{ \frac{n^2 - na}{5} \right\}
 +
& = \left\{ \frac{\left( 5 q + r \right)^2 - \left( 5 q + r \right)\left( 1350 - 1 \right)}{5} \right\} \\
 +
& = \left\{ 5 q^2 + 2 q r - \left( 5 q + r \right) 270 + q + \frac{r^2 + r}{5}  \right\} \\
 +
& = \left\{\frac{r^2 + r}{5}  \right\} \\
 +
& = \left\{
 +
\begin{array}{ll}
 +
0 & \mbox{ if } r = 0, 4 \\
 +
\frac{2}{5} & \mbox{ if } r = 1, 3 \\
 +
\frac{1}{5} & \mbox{ if } r = 2
 +
\end{array}
 +
\right. .
 +
\end{align*}
 +
</cmath>
 +
 +
Therefore,
 +
<cmath>
 +
\begin{align*}
 +
U & =  \sum_{n=1}^{2023} \left(  \frac{n^2 - na}{5} - \left\{ \frac{n^2 - na}{5} \right\}  \right) \\
 +
& = UB
 +
- \sum_{n=1}^{2023} \left\{ \frac{n^2 - na}{5} \right\} \\
 +
& = - \sum_{n=1}^{2023} \left\{ \frac{n^2 - na}{5} \right\} \\
 +
& = - \sum_{q=0}^{404} \sum_{r=0}^4 \left\{\frac{r^2 + r}{5}  \right\}
 +
+ \left\{ \frac{0^2 - 0 \cdot a}{5} \right\}
 +
+ \left\{ \frac{2024^2 - 2024a}{5} \right\} \\
 +
& = - \sum_{q=0}^{404} \left( 0 + 0 + \frac{2}{5} + \frac{2}{5} + \frac{1}{5} \right)
 +
+ 0 + 0 \\
 +
& = - 405 .
 +
\end{align*}
 +
</cmath>
 +
 +
Therefor, <math>a + U = 1349 - 405 = \boxed{\textbf{(944) }}</math>.
 +
 +
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
  
 
==Video Solution by Punxsutawney Phil==
 
==Video Solution by Punxsutawney Phil==
 
https://youtu.be/jQVbNJr0tX8
 
https://youtu.be/jQVbNJr0tX8
 +
 +
==Video Solution==
 +
 +
https://youtu.be/fxsPmL6wuW4
 +
 +
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
  
 
==See also==
 
==See also==

Revision as of 12:36, 8 February 2023

Problem 10

There exists a unique positive integer $a$ for which the sum \[U=\sum_{n=1}^{2023}\left\lfloor\dfrac{n^{2}-na}{5}\right\rfloor\] is an integer strictly between $-1000$ and $1000$. For that value $a$, find $a+U$.

(Note that $\lfloor x\rfloor$ denotes the greatest integer that is less than or equal to $x$.)

Bounds and Decimal Part Analysis

Define $\left\{ x \right\} = x - \left\lfloor x \right\rfloor$.

First, we bound $U$.

We establish an upper bound of $U$. We have \begin{align*} U & \leq \sum_{n=1}^{2023} \frac{n^2 - na}{5} \\ & = \frac{1}{5} \sum_{n=1}^{2023} n^2 - \frac{a}{5} \sum_{n=1}^{2023} n \\ & = \frac{1012 \cdot 2023}{5} \left( 1349 - a \right) \\ & \triangleq UB . \end{align*}

We establish a lower bound of $U$. We have \begin{align*} U & = \sum_{n=1}^{2023} \left( \frac{n^2 - na}{5} - \left\{ \frac{n^2 - na}{5} \right\} \right) \\ & = \sum_{n=1}^{2023} \frac{n^2 - na}{5} - \sum_{n=1}^{2023} \left\{ \frac{n^2 - na}{5} \right\} \\ & = UB - \sum_{n=1}^{2023} \left\{ \frac{n^2 - na}{5} \right\} \\ & \geq UB - \sum_{n=1}^{2023} \mathbf 1 \left\{ \frac{n^2 - na}{5} \notin \Bbb Z \right\} . \end{align*}

We notice that if $5 | n$, then $\frac{n^2 - na}{5} \in \Bbb Z$. Thus, \begin{align*} U & \geq UB - \sum_{n=1}^{2023} \mathbf 1 \left\{ \frac{n^2 - na}{5} \notin \Bbb Z \right\} \\ & \geq UB - \sum_{n=1}^{2023} \mathbf 1 \left\{ 5 \nmid n \right\} \\ & = UB - \left( 2023 - \left\lfloor \frac{2023}{5} \right\rfloor \right) \\ & = UB - 1619 \\ & \triangleq LB . \end{align*}

Because $U \in \left[ - 1000, 1000 \right]$ and $UB - LB = 1619 < \left( 1000 - \left( - 1000 \right) \right)$, we must have either $UB \in \left[ - 1000, 1000 \right]$ or $LB \in \left[ - 1000, 1000 \right]$.

For $UB \in \left[ - 1000, 1000 \right]$, we get a unique $a = 1349$. For $LB \in \left[ - 1000, 1000 \right]$, there is no feasible $a$.

Therefore, $a = 1349$. Thus $UB = 0$.

Next, we compute $U$.

Let $n = 5 q + r$, where $r = {\rm Rem} \ \left( n, 5 \right)$.

We have \begin{align*} \left\{ \frac{n^2 - na}{5} \right\} & = \left\{ \frac{\left( 5 q + r \right)^2 - \left( 5 q + r \right)\left( 1350 - 1 \right)}{5} \right\} \\ & = \left\{ 5 q^2 + 2 q r - \left( 5 q + r \right) 270 + q + \frac{r^2 + r}{5} \right\} \\ & = \left\{\frac{r^2 + r}{5} \right\} \\ & = \left\{ \begin{array}{ll} 0 & \mbox{ if } r = 0, 4 \\ \frac{2}{5} & \mbox{ if } r = 1, 3 \\ \frac{1}{5} & \mbox{ if } r = 2 \end{array} \right. . \end{align*}

Therefore, \begin{align*} U & = \sum_{n=1}^{2023} \left( \frac{n^2 - na}{5} - \left\{ \frac{n^2 - na}{5} \right\} \right) \\ & = UB - \sum_{n=1}^{2023} \left\{ \frac{n^2 - na}{5} \right\} \\ & = - \sum_{n=1}^{2023} \left\{ \frac{n^2 - na}{5} \right\} \\ & = - \sum_{q=0}^{404} \sum_{r=0}^4 \left\{\frac{r^2 + r}{5} \right\} + \left\{ \frac{0^2 - 0 \cdot a}{5} \right\} + \left\{ \frac{2024^2 - 2024a}{5} \right\} \\ & = - \sum_{q=0}^{404} \left( 0 + 0 + \frac{2}{5} + \frac{2}{5} + \frac{1}{5} \right) + 0 + 0 \\ & = - 405 . \end{align*}

Therefor, $a + U = 1349 - 405 = \boxed{\textbf{(944) }}$.

~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)

Video Solution by Punxsutawney Phil

https://youtu.be/jQVbNJr0tX8

Video Solution

https://youtu.be/fxsPmL6wuW4

~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)

See also

2023 AIME I (Problems • Answer Key • Resources)
Preceded by
Problem 9 		Followed by
Problem 11
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2023_AIME_I_Problems/Problem_10&oldid=188874"