Difference between revisions of "2023 AIME I Problems/Problem 10"

m
(Video Solution)
Line 99: Line 99:
  
 
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
 
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
 +
 +
 +
 +
==Solution 4==
 +
 +
We define <math>U' = \sum^{2023}_{n=1} {\frac{n^2-na}{5}}</math>. Since for any real number <math>x</math>, <math>\lfloor x \rfloor \le x \le \lfloor x \rfloor + 1</math>, we have <math>U \le U' \le U + 2023</math>. Now, since <math>-1000 \le U \le 1000</math>, we have <math>-1000 \le U' \le 3023</math>.
 +
 +
Now, we can solve for <math>U'</math> in terms of <math>a</math>. We have:
 +
<cmath>
 +
\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*}
 +
</cmath>
 +
So, we have <math>U' = \frac{2023(2024)(4047-3a)}{30}</math>, and <math>-1000 \le U' \le 3023</math>, so we have <math>-1000 \le \frac{2023(2024)(4047-3a)}{30} \le 3023</math>, or <math>-30000 \le 2023(2024)(4047-3a) \le 90690</math>. Now, <math>2023 \cdot 2024</math> is much bigger than <math>90690</math> or <math>30000</math>, and since <math>4047-3a</math> is an integer, to satsify the inequalities, we must have <math>4047 - 3a = 0</math>, or <math>a = 1349</math>, and <math>U' = 0</math>.
 +
 +
Now, we can find <math>U - U'</math>. We have:
 +
<cmath>
 +
\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*}.
 +
</cmath>
 +
Now, if <math>n^2-1349n \equiv 0 \text{ (mod 5)}</math>, then <math>\lfloor \frac{n^2-1349n}{5} \rfloor - \frac{n^2-1349n}{5} = 0</math>, and if <math>n^2-1349n \equiv 1 \text{ (mod 5)}</math>, then <math>\lfloor \frac{n^2-1349n}{5} \rfloor - \frac{n^2-1349n}{5} = -\frac{1}{5}</math>, and so on. Testing with <math>n \equiv 0,1,2,3,4, \text{ (mod 5)}</math>, we get <math>n^2-1349n \equiv 0,2,1,2,0 \text{ (mod 5)}</math> 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 <math>U - U'</math>, we get:
 +
<cmath>
 +
\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*}
 +
</cmath>
 +
Since <math>U' = 0</math>, this gives <math>U = -405</math>, and we have <math>a + U = 1349-405 = \boxed{944}</math>.
 +
 +
~ genius_007
  
 
==See also==
 
==See also==

Revision as of 14:10, 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 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

See also

2023 AIME I (ProblemsAnswer KeyResources)
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