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 "2010 AIME I Problems/Problem 10"
(→‎Solution 3: Casework and Brute Force)
Line 18: Line 18:
 
We immediately see that <math>a_3</math> can only be <math>0</math>, <math>1</math> or <math>2</math>. We also note that the maximum possible value for <math>10a_1 + a_0</math> is <math>990 + 99 = 1089</math>. We then split into cases:
 
We immediately see that <math>a_3</math> can only be <math>0</math>, <math>1</math> or <math>2</math>. We also note that the maximum possible value for <math>10a_1 + a_0</math> is <math>990 + 99 = 1089</math>. We then split into cases:
  
−
Case 1: <math>a_3 = 0</math>
+
Case 1: <math>a_3 = 0</math>.
 
We try to find possible values of <math>a_2</math>. We plug in <math>a_3 = 0</math> and <math>10a_1 + a_0 = 1089</math> to our initial equation, which gives us <math>2010 = 0 + 100a_2^2 + 1089</math>. Thus <math>a_2 \geq 10</math>. We also see that <math>a_2 \leq 20</math>. We now take these values of <math>a_2</math> and find the number of pairs <math>(a_1, a_0)</math> that work. If <math>a_2 = 10</math>, <math>10a_1 + a_0 = 1010</math>. We see that there are <math>8</math> possible pairs in this case. Using the same logic, there are <math>10</math> ways for <math>a_2 = 11, 12 \ldots 19</math>. For <math>a_2 = 20</math>, we get the equation <math>10a_1 + a_0 = 10</math>, for 2 ways. Thus, for <math>a_3 = 0</math>, there are <math>8 + 10 \cdot 9 + 2 = 100</math> ways.
 
We try to find possible values of <math>a_2</math>. We plug in <math>a_3 = 0</math> and <math>10a_1 + a_0 = 1089</math> to our initial equation, which gives us <math>2010 = 0 + 100a_2^2 + 1089</math>. Thus <math>a_2 \geq 10</math>. We also see that <math>a_2 \leq 20</math>. We now take these values of <math>a_2</math> and find the number of pairs <math>(a_1, a_0)</math> that work. If <math>a_2 = 10</math>, <math>10a_1 + a_0 = 1010</math>. We see that there are <math>8</math> possible pairs in this case. Using the same logic, there are <math>10</math> ways for <math>a_2 = 11, 12 \ldots 19</math>. For <math>a_2 = 20</math>, we get the equation <math>10a_1 + a_0 = 10</math>, for 2 ways. Thus, for <math>a_3 = 0</math>, there are <math>8 + 10 \cdot 9 + 2 = 100</math> ways.
  
−
Case 2: <math>a_3 = 1</math>
+
Case 2: <math>a_3 = 1</math>.
 
This case is almost identical to the one above, except <math>0 \leq a_2 \leq 10</math>. We also get 100 ways.
 
This case is almost identical to the one above, except <math>0 \leq a_2 \leq 10</math>. We also get 100 ways.
  
−
Case 3: <math>a_3 = 2</math>
+
Case 3: <math>a_3 = 2</math>.
 
If <math>a_3 = 2</math>, our initial equation becomes <math>100a_2 + 10a_1 + a_0 = 10</math>. It is obvious that <math>a_2 = 0</math>, and we are left with <math>10a_1 + a_0 = 10</math>. We saw above that there are <math>2</math> ways.
 
If <math>a_3 = 2</math>, our initial equation becomes <math>100a_2 + 10a_1 + a_0 = 10</math>. It is obvious that <math>a_2 = 0</math>, and we are left with <math>10a_1 + a_0 = 10</math>. We saw above that there are <math>2</math> ways.
  

Revision as of 16:15, 4 January 2016

Problem

Let $N$ be the number of ways to write $2010$ in the form $2010 = a_3 \cdot 10^3 + a_2 \cdot 10^2 + a_1 \cdot 10 + a_0$, where the $a_i$'s are integers, and $0 \le a_i \le 99$. An example of such a representation is $1\cdot 10^3 + 3\cdot 10^2 + 67\cdot 10^1 + 40\cdot 10^0$. Find $N$.

Solution 1

If we choose $a_3$ and $a_1$ such that $(10^3)(a_3) + (10)(a_1) \leq 2010$ there is a unique choice of $a_2$ and $a_0$ that makes the equality hold. So $N$ is just the number of combinations of $a_3$ and $a_1$ we can pick. If $a_3 = 0$ or $a_3 = 1$ we can let $a_1$ be anything from $0$ to $99$. If $a_3 = 2$ then $a_1 = 0$ or $a_1 = 1$. Thus $N = 100 + 100 + 2 = \fbox{202}$.

Solution 2

Note that $a_0 \equiv 2010\ (\textrm{mod}\ 10)$ and $a_1 \equiv 2010 - a_0\ (\textrm{mod}\ 100)$. It's easy to see that exactly 10 values in $0 \leq a_0 \leq 99$ that satisfy our first congruence. Similarly, there are 10 possible values of $a_1$ for each choice of $a_0$. Thus, there are $10 \times 10 = 100$ possible choices for $a_0$ and $a_1$. We next note that if $a_0$ and $a_1$ are chosen, then a valid value of $a_3$ determines $a_2$, so we dive into some simple casework:

  • If $2010 - 10a_1 - a_0 \geq 2000$, there are 3 valid choices for $a_3$. There are only 2 possible cases where $2010 - 10a_1 - a_0 \geq 2000$, namely $(a_1, a_0) = (1,0), (10,0)$. Thus, there are $3 \times 2 = 6$ possible representations in this case.
  • If $2010 - 10a_1 - a_0 < 1000$, $a_3$ can only equal 0. However, this case cannot occur, as $10a_1+a_0\leq 990+99 = 1089$. Thus, $2010-10a_1-a_0 \geq 921$. However, $2010-10a_1-a_0 = 1000a_3 + 100a_2 \equiv 0\ (\textrm{mod}\ 100)$. Thus, we have $2010-10a_1-a_0 \geq 1000$ always.
  • If $1000 \leq 2010 - 10a_1 - a_0 < 2000$, then there are 2 valid choices for $a_3$. Since there are 100 possible choices for $a_0$ and $a_1$, and we have already checked the other cases, it follows that $100 - 2 - 0 = 98$ choices of $a_0$ and $a_1$ fall under this case. Thus, there are $2 \times 98 = 196$ possible representations in this case.

Our answer is thus $6 + 0 + 196 = \boxed{202}$.

Solution 3: Casework and Brute Force

We immediately see that $a_3$ can only be $0$, $1$ or $2$. We also note that the maximum possible value for $10a_1 + a_0$ is $990 + 99 = 1089$. We then split into cases:

Case 1: $a_3 = 0$. We try to find possible values of $a_2$. We plug in $a_3 = 0$ and $10a_1 + a_0 = 1089$ to our initial equation, which gives us $2010 = 0 + 100a_2^2 + 1089$. Thus $a_2 \geq 10$. We also see that $a_2 \leq 20$. We now take these values of $a_2$ and find the number of pairs $(a_1, a_0)$ that work. If $a_2 = 10$, $10a_1 + a_0 = 1010$. We see that there are $8$ possible pairs in this case. Using the same logic, there are $10$ ways for $a_2 = 11, 12 \ldots 19$. For $a_2 = 20$, we get the equation $10a_1 + a_0 = 10$, for 2 ways. Thus, for $a_3 = 0$, there are $8 + 10 \cdot 9 + 2 = 100$ ways.

Case 2: $a_3 = 1$. This case is almost identical to the one above, except $0 \leq a_2 \leq 10$. We also get 100 ways.

Case 3: $a_3 = 2$. If $a_3 = 2$, our initial equation becomes $100a_2 + 10a_1 + a_0 = 10$. It is obvious that $a_2 = 0$, and we are left with $10a_1 + a_0 = 10$. We saw above that there are $2$ ways.

Totaling everything, we get that there are $100 + 100 + 2 = \boxed{202}$ ways.

See Also

2010 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=2010_AIME_I_Problems/Problem_10&oldid=74324"