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"

m
(→‎Solution 4 (Calculus))
 
(24 intermediate revisions by 10 users not shown)
Line 1: Line 1:
−
==Problem 10==
+
==Problem==
 
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 integer strictly between <math>-1000</math> and <math>1000</math>. For that unique <math>a</math>, find <math>a+U</math>.
 
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 integer strictly between <math>-1000</math> and <math>1000</math>. For that unique <math>a</math>, find <math>a+U</math>.
  
 
(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>.)
  
−
==Solution (Bounds and Decimal Part Analysis)==
+
==Solution (Bounds and Decimal Part Analysis, Rigorous)==
  
 
Define <math>\left\{ x \right\} = x - \left\lfloor x \right\rfloor</math>.
 
Define <math>\left\{ x \right\} = x - \left\lfloor x \right\rfloor</math>.
Line 87: Line 87:
 
</cmath>
 
</cmath>
  
−
Therefor, <math>a + U = 1349 - 405 = \boxed{\textbf{(944) }}</math>.
+
Therefore, <math>a + U = 1349 - 405 = \boxed{\textbf{944}}</math>.
  
 
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
 
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
 +
 +
~minor edits by [https://artofproblemsolving.com/wiki/index.php/User:Kevinchen_yay KevinChen_Yay]
 +
 +
==Solution 2==
 +
 +
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
 +
 +
==Solution 3 (Quick)==
 +
 +
 +
We can view the floor function in this problem as simply subtracting the remainder of <math>n^2 - na</math> (mod <math>5</math>) from the numerator of 
 +
<math>\frac{n^2-na}{5}</math>. For example, <math>\left\lfloor \frac{7}{5} \right\rfloor = \frac{7-2}{5} = 1</math>.
 +
 +
Note that the congruence of  <math>n^2 - na</math> (mod <math>5</math>) loops every time <math>n</math> increases by 5. Also, note that the congruence of <math>a</math> (mod <math>5</math>) determines the set of congruences of <math>n^2 - na</math> for each congruence of <math>n</math> (mod <math>5</math>).
 +
 +
For example, if <math>a \equiv 1</math> (mod <math>5</math>), the set of remainders is <math>(0, 2, 1, 2, 0)</math> for <math>n \equiv 1,2,3,4,0</math> (mod <math>5</math>). Let the sum of these elements be <math>s</math>. Note that for each “loop” of the numerator (mod <math>5</math>), each element of the set will be subtracted exactly once, meaning <math>s</math> is subtracted once for each loop. The value of the numerator will loop <math>404</math> times (mod <math>5</math>) throughout the sum, as <math>5 \cdot 404=2020</math>. Then
 +
 +
<math>U \approx \frac {\left( \frac {n(n+1)(2n+1)}{6} - \frac{(a)(n)(n+1)}{2}  -404s \right)}{5}</math>
 +
 +
Where <math>n=2023</math>. Note that since <math>5 \cdot 404=2020</math>, this is an approximation for <math>U</math> because the equation disregards the remainder (mod <math>5</math>) when <math>n=2021, 2022</math>, and <math>2023</math> so we must subtract the first 3 terms of our set of congruences one extra time to get the exact value of <math>U</math> (*). However, we will find that this is a negligible error when it comes to the inequality <math>-1000<U<1000</math>, so we can proceed with this approximation to solve for <math>a</math>.
 +
 +
Factoring our approximation gives <math>U \approx \frac {\frac{(n)(n+1)(2n+1 - 3a)}{6}-404s}{5}</math>
 +
 +
 +
We set <math>a= \frac{(2n+1)}{3} = 1349</math> to make <math>\frac{(n)(n+1)(2n+1 - 3a)}{6}=0</math>, accordingly minimizing <math>|U|</math>, yielding  <math>U \approx
 +
\frac{-404s}{5}</math>
 +
 +
If <math>a</math> increases or decreases by <math>1</math>, then <math>U</math> changes by <math>\frac {(n)(n+1)}{2 \cdot 5} = \frac {2023 \cdot 2024}{10}</math>
 +
which clearly breaks the inequality on <math>U</math>. Therefore <math>a=1349 \equiv 4</math> (mod <math>5</math>) giving the set of remainders <math>(2,1,2,0,0)</math>, so <math>s=5</math> and our approximation yields <math>U \approx -404</math>. However, we must subtract 2, 1, and 2 (*) giving us <math>U = - 404 - \frac{(2+1+2)}{5} = - 405</math>, giving an answer of <math>1349-405= \boxed{944}</math>
 +
 +
~Spencer Danese
 +
 +
==Solution 4 (Calculus)==
 +
Consider the integral
 +
<cmath> \int_{0}^{2023} \dfrac{n^2-na}{5} \, dn. </cmath>
 +
We hope this will give a good enough appoximation of <math>U</math> to find <math>a.</math> However, this integral can be easily evaluated to be
 +
<cmath>\dfrac{1}{15}2023^3-\dfrac{a}{10}2023^2=2023^2\left(\dfrac{2023}{15}-\dfrac{a}{10}\right).</cmath>
 +
Because we want this to be as close to <math>0</math> as possible, we find that <math>a</math> should equal <math>1349.</math> Then, evaluating the sum becomes trivial. Set
 +
<cmath>U'=\sum_{n=1}^{2023}\dfrac{n^2-1349n}{5}</cmath>
 +
and
 +
<cmath>U''=\sum_{n=1}^{2023}\{\dfrac{n^2-1349n}{5}\}.</cmath>
 +
Then <math>U=U'-U''.</math> We can evaluate <math>U'</math> to be <math>0</math> and <math>U''</math> to be <math>-405</math> (using some basic number theory). Thus, <math>U=-405</math> and the answer is
 +
<cmath>1349+(-405)=\boxed{944}.</cmath>
 +
~[[BS2012]]
  
 
==Video Solution by Punxsutawney Phil==
 
==Video Solution by Punxsutawney Phil==
 +
 
https://youtu.be/jQVbNJr0tX8
 
https://youtu.be/jQVbNJr0tX8
  
−
==Video Solution==
+
==Video Solution by Steven Chen==
  
 
https://youtu.be/fxsPmL6wuW4
 
https://youtu.be/fxsPmL6wuW4
  
−
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
+
==Video Solution by Mathematical Dexterity==
 +
 
 +
https://www.youtube.com/watch?v=49XIe2jx9zg
  
 
==See also==
 
==See also==

Latest revision as of 19:24, 13 June 2024

Problem

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, Rigorous)

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*}

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

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

~minor edits by KevinChen_Yay

Solution 2

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

Solution 3 (Quick)

We can view the floor function in this problem as simply subtracting the remainder of $n^2 - na$ (mod $5$) from the numerator of $\frac{n^2-na}{5}$. For example, $\left\lfloor \frac{7}{5} \right\rfloor = \frac{7-2}{5} = 1$.

Note that the congruence of $n^2 - na$ (mod $5$) loops every time $n$ increases by 5. Also, note that the congruence of $a$ (mod $5$) determines the set of congruences of $n^2 - na$ for each congruence of $n$ (mod $5$).

For example, if $a \equiv 1$ (mod $5$), the set of remainders is $(0, 2, 1, 2, 0)$ for $n \equiv 1,2,3,4,0$ (mod $5$). Let the sum of these elements be $s$. Note that for each “loop” of the numerator (mod $5$), each element of the set will be subtracted exactly once, meaning $s$ is subtracted once for each loop. The value of the numerator will loop $404$ times (mod $5$) throughout the sum, as $5 \cdot 404=2020$. Then

$U \approx \frac {\left( \frac {n(n+1)(2n+1)}{6} - \frac{(a)(n)(n+1)}{2} -404s \right)}{5}$

Where $n=2023$. Note that since $5 \cdot 404=2020$, this is an approximation for $U$ because the equation disregards the remainder (mod $5$) when $n=2021, 2022$, and $2023$ so we must subtract the first 3 terms of our set of congruences one extra time to get the exact value of $U$ (*). However, we will find that this is a negligible error when it comes to the inequality $-1000<U<1000$, so we can proceed with this approximation to solve for $a$.

Factoring our approximation gives $U \approx \frac {\frac{(n)(n+1)(2n+1 - 3a)}{6}-404s}{5}$


We set $a= \frac{(2n+1)}{3} = 1349$ to make $\frac{(n)(n+1)(2n+1 - 3a)}{6}=0$, accordingly minimizing $|U|$, yielding $U \approx \frac{-404s}{5}$

If $a$ increases or decreases by $1$, then $U$ changes by $\frac {(n)(n+1)}{2 \cdot 5} = \frac {2023 \cdot 2024}{10}$ which clearly breaks the inequality on $U$. Therefore $a=1349 \equiv 4$ (mod $5$) giving the set of remainders $(2,1,2,0,0)$, so $s=5$ and our approximation yields $U \approx -404$. However, we must subtract 2, 1, and 2 (*) giving us $U = - 404 - \frac{(2+1+2)}{5} = - 405$, giving an answer of $1349-405= \boxed{944}$

~Spencer Danese

Solution 4 (Calculus)

Consider the integral \[\int_{0}^{2023} \dfrac{n^2-na}{5} \, dn.\] We hope this will give a good enough appoximation of $U$ to find $a.$ However, this integral can be easily evaluated to be \[\dfrac{1}{15}2023^3-\dfrac{a}{10}2023^2=2023^2\left(\dfrac{2023}{15}-\dfrac{a}{10}\right).\] Because we want this to be as close to $0$ as possible, we find that $a$ should equal $1349.$ Then, evaluating the sum becomes trivial. Set \[U'=\sum_{n=1}^{2023}\dfrac{n^2-1349n}{5}\] and \[U''=\sum_{n=1}^{2023}\{\dfrac{n^2-1349n}{5}\}.\] Then $U=U'-U''.$ We can evaluate $U'$ to be $0$ and $U''$ to be $-405$ (using some basic number theory). Thus, $U=-405$ and the answer is \[1349+(-405)=\boxed{944}.\] ~BS2012

Video Solution by Punxsutawney Phil

https://youtu.be/jQVbNJr0tX8

Video Solution by Steven Chen

https://youtu.be/fxsPmL6wuW4

Video Solution by Mathematical Dexterity

https://www.youtube.com/watch?v=49XIe2jx9zg

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=220478"