2023 AIME I Problems/Problem 10

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 unique $a$ , find $a+U$ .

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

Solution (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)

Solution 4

We define $U' = \sum^{2023}_{n=1} {\frac{n^2-na}{5}}$ . Since for any real number $x$ , $\lfloor x \rfloor \le x \le \lfloor x \rfloor + 1$ , we have $U \le U' \le U + 2023$ . Now, since $-1000 \le U \le 1000$ , we have $-1000 \le U' \le 3023$ .

Now, we can solve for $U'$ in terms of $a$ . We have: $\begin{align*} U' &= \sum^{2023}_{n=1} {\frac{n^2-na}{5}} \\ &= \sum^{2023}_{n=1} {\frac{n^2}{5} - \frac{na}{5}} \\ &= \sum^{2023}_{n=1} {\frac{n^2}{5}} - \sum^{2023}_{n=1} {\frac{na}{5}} \\ &= \frac{\sum^{2023}_{n=1} {{n^2}} - \sum^{2023}_{n=1} {na}}{5} \\ &= \frac{\frac{2023(2023+1)(2023 \cdot 2 + 1)}{6} - \frac{a \cdot 2023(2023+1)}{2} }{5} \\ &= \frac{2023(2024)(4047-3a)}{30} \\ \end{align*}$ So, we have $U' = \frac{2023(2024)(4047-3a)}{30}$ , and $-1000 \le U' \le 3023$ , so we have $-1000 \le \frac{2023(2024)(4047-3a)}{30} \le 3023$ , or $-30000 \le 2023(2024)(4047-3a) \le 90690$ . Now, $2023 \cdot 2024$ is much bigger than $90690$ or $30000$ , and since $4047-3a$ is an integer, to satsify the inequalities, we must have $4047 - 3a = 0$ , or $a = 1349$ , and $U' = 0$ .

Now, we can find $U - U'$ . We have: $\begin{align*} U - U' &= \sum^{2023}_{n=1} {\lfloor \frac{n^2-1349n}{5} \rfloor} - \sum^{2023}_{n=1} {\frac{n^2-1349n}{5}} \\ &= \sum^{2023}_{n=1} {\lfloor \frac{n^2-1349n}{5} \rfloor - \frac{n^2-1349n}{5}} \end{align*}.$ Now, if $n^2-1349n \equiv 0 \text{ (mod 5)}$ , then $\lfloor \frac{n^2-1349n}{5} \rfloor - \frac{n^2-1349n}{5} = 0$ , and if $n^2-1349n \equiv 1 \text{ (mod 5)}$ , then $\lfloor \frac{n^2-1349n}{5} \rfloor - \frac{n^2-1349n}{5} = -\frac{1}{5}$ , and so on. Testing with $n \equiv 0,1,2,3,4, \text{ (mod 5)}$ , we get $n^2-1349n \equiv 0,2,1,2,0 \text{ (mod 5)}$ respectively. From 1 to 2023, there are 405 numbers congruent to 1 mod 5, 405 numbers congruent to 2 mod 5, 405 numbers congruent to 3 mod 5, 404 numbers congruent to 4 mod 5, and 404 numbers congruent to 0 mod 5. So, solving for $U - U'$ , we get: $\begin{align*} U - U' &= \sum^{2023}_{n=1} {\lfloor \frac{n^2-1349n}{5} \rfloor - \frac{n^2-1349n}{5}} \\ &= 404 \cdot 0 - 405 \cdot \frac{2}{5} - 405 \cdot \frac{1}{5} - 405 \cdot \frac{2}{5} - 404 \cdot t0 \\ &= -405(\frac{2}{5}+\frac{1}{5}+\frac{2}{5}) \\ &= -405 \end{align*}$ Since $U' = 0$ , this gives $U = -405$ , and we have $a + U = 1349-405 = \boxed{944}$ .

~ genius_007

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

Page

Toolbox

Search