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 "2013 AIME I Problems/Problem 15"

(→‎Solution)
(→‎Solution 2)
 
(8 intermediate revisions by 4 users not shown)
Line 1: Line 1:
−
==Problem 15==
+
==Problem ==
−
Let <math>N</math> be the number of ordered triples <math>(A,B,C)</math> of integers satisfying the conditions (a) <math>0\le A<B<C\le99</math>, (b) there exist integers <math>a</math>, <math>b</math>, and <math>c</math>, and prime <math>p</math> where <math>0\le b<a<c<p</math>, (c) <math>p</math> divides <math>A-a</math>, <math>B-b</math>, and <math>C-c</math>, and (d) each ordered triple <math>(A,B,C)</math> and each ordered triple <math>(b,a,c)</math> form arithmetic sequences. Find <math>N</math>.
+
Let <math>N</math> be the number of ordered triples <math>(A,B,C)</math> of integers satisfying the conditions  
 +
(a) <math>0\le A<B<C\le99</math>,  
 +
(b) there exist integers <math>a</math>, <math>b</math>, and <math>c</math>, and prime <math>p</math> where <math>0\le b<a<c<p</math>,  
 +
(c) <math>p</math> divides <math>A-a</math>, <math>B-b</math>, and <math>C-c</math>, and  
 +
(d) each ordered triple <math>(A,B,C)</math> and each ordered triple <math>(b,a,c)</math> form arithmetic sequences. Find <math>N</math>.
  
−
==Solution 1==
+
==Solution==
−
From condition (d), we have <math>(A,B,C)=(B-D,B,B+D)</math> and <math>(b,a,c)=(a-d,a,a+d)</math>. Condition <math>\text{(c)}</math> states that <math>p\mid B-D-a</math>, <math>p|B-a+d</math>, and <math>p\mid B+D-a-d</math>. We subtract the first two to get <math>p\mid-d-D</math>, and we do the same for the last two to get <math>p\mid 2d-D</math>. We subtract these two to get <math>p\mid 3d</math>. So <math>p\mid 3</math> or <math>p\mid d</math>. The second case is clearly impossible, because that would make <math>c=a+d>p</math>, violating condition <math>\text{(b)}</math>. So we have <math>p\mid 3</math>, meaning <math>p=3</math>. Condition <math>\text{(b)}</math> implies that <math>(b,a,c)=(0,1,2)</math> or <math>(a,b,c)\in (1,0,2)\rightarrow (-2,0,2)\text{ }(D\equiv 2\text{ mod 3})</math>. Now we return to condition <math>\text{(c)}</math>, which now implies that <math>(A,B,C)\equiv(-2,0,2)\pmod{3}</math>. Now, we set <math>B=3k</math> for increasing positive integer values of <math>k</math>. <math>B=0</math> yields no solutions. <math>B=3</math> gives <math>(A,B,C)=(1,3,5)</math>, giving us <math>1</math> solution. If <math>B=6</math>, we get <math>2</math> solutions, <math>(4,6,8)</math> and <math>(1,6,11)</math>. Proceeding in the manner, we see that if <math>B=48</math>, we get 16 solutions. However, <math>B=51</math> still gives <math>16</math> solutions because <math>C_\text{max}=2B-1=101>100</math>. Likewise, <math>B=54</math> gives <math>15</math> solutions. This continues until <math>B=96</math> gives one solution. <math>B=99</math> gives no solution. Thus, <math>N=1+2+\cdots+16+16+15+\cdots+1=2\cdot\frac{16(17)}{2}=16\cdot 17=\boxed{272}</math>.
+
From condition (d), we have <math>(A,B,C)=(B-D,B,B+D)</math> and <math>(b,a,c)=(a-d,a,a+d)</math>. Condition <math>\text{(c)}</math> states that <math>p\mid B-D-a</math>, <math>p | B-a+d</math>, and <math>p\mid B+D-a-d</math>. We subtract the first two to get <math>p\mid-d-D</math>, and we do the same for the last two to get <math>p\mid 2d-D</math>. We subtract these two to get <math>p\mid 3d</math>. So <math>p\mid 3</math> or <math>p\mid d</math>. The second case is clearly impossible, because that would make <math>c=a+d>p</math>, violating condition <math>\text{(b)}</math>. So we have <math>p\mid 3</math>, meaning <math>p=3</math>. Condition <math>\text{(b)}</math> implies that <math>(b,a,c)=(0,1,2)</math> or <math>(a,b,c)\in (1,0,2)\rightarrow (-2,0,2)\text{ }(D\equiv 2\text{ mod 3})</math>. Now we return to condition <math>\text{(c)}</math>, which now implies that <math>(A,B,C)\equiv(-2,0,2)\pmod{3}</math>. Now, we set <math>B=3k</math> for increasing positive integer values of <math>k</math>. <math>B=0</math> yields no solutions. <math>B=3</math> gives <math>(A,B,C)=(1,3,5)</math>, giving us <math>1</math> solution. If <math>B=6</math>, we get <math>2</math> solutions, <math>(4,6,8)</math> and <math>(1,6,11)</math>. Proceeding in the manner, we see that if <math>B=48</math>, we get 16 solutions. However, <math>B=51</math> still gives <math>16</math> solutions because <math>C_\text{max}=2B-1=101>100</math>. Likewise, <math>B=54</math> gives <math>15</math> solutions. This continues until <math>B=96</math> gives one solution. <math>B=99</math> gives no solution. Thus, <math>N=1+2+\cdots+16+16+15+\cdots+1=2\cdot\frac{16(17)}{2}=16\cdot 17=\boxed{272}</math>.
  
−
== Solution 2 ==
+
 
−
Condition c gives us that <math>A \equiv a \pmod p</math>, etc. Condition d then tells us that C and c can be expressed as <math>2B - A</math> and <math>2a - b</math>, respectively. However, plugging what we got from condition c into this, we find that <math>3a \equiv 3b \pmod p</math>. From there, we branch off into two cases; either <math>p = 3</math>, or <math>a \equiv b \pmod p</math>. Realize then that the second case leads to a contradiction, due to condition b. Then, <math>p = 3</math> means that <math>(b,a,c)</math> must be <math>(0, 1, 2)</math>. The bash from there is pretty similar to what was done in Solution 1. We get <math>\boxed{272}</math>. - Spacesam
+
==Solution 2==
 +
Let <math>(A, B, C)</math> = <math>(B-x, B, B+x)</math> and <math>(b, a, c) = (a-y, a, a+y)</math>. Now the 3 differences would be
 +
<cmath>\begin{align}
 +
\label{1} &A-a = B-x-a \\
 +
\label{2} &B - b = B-a+y \\
 +
\label{3} &C - c = B+x-a-y
 +
\end{align}</cmath>
 +
 
 +
Adding equations <math>(1)</math> and <math>(3)</math> would give <math>2B - 2a - y</math>. Then doubling equation <math>(2)</math> would give <math>2B - 2a + 2y</math>. The difference between them would be <math>3y</math>. Since <math>p|\{(1), (2), (3)\}</math>, then <math>p|3y</math>. Since <math>p</math> is prime, <math>p|3</math> or <math>p|y</math>. However, since <math>p > y</math>, we must have <math>p|3</math>, which means <math>p=3</math>.
 +
 
 +
 
 +
If <math>p=3</math>, the only possible values of <math>(b, a, c)</math> are <math>(0, 1, 2)</math>. Plugging this into our differences, we get
 +
<cmath>\begin{align*}
 +
&A-a = B-x-1 \hspace{4cm}(4)\\
 +
&B - b = B \hspace{5.35cm}(5)\\
 +
&C - c = B+x-2 \hspace{4cm}(6)
 +
\end{align*}</cmath>
 +
The difference between <math>(4)</math> and <math>(5)</math> is <math>x+1</math>, which should be divisible by 3. So <math>x \equiv 2 \mod 3</math>. Also note that since <math>3|(5)</math>, <math>3|B</math>. Now we can try different values of <math>x</math> and <math>B</math>:
 +
 
 +
When <math>x=2</math>, <math>B=3, 6, ..., 96 \Rightarrow 17</math> triples.
 +
 
 +
When <math>x=5</math>, <math>B=6, 9, ..., 93\Rightarrow 15</math> triples..
 +
 
 +
... and so on until
 +
 
 +
When <math>x=44</math>, <math>B=45\Rightarrow 1</math> triple.  
 +
 
 +
So the answer is <math>17 + 15 + \cdots + 1 = \boxed{272}</math>
 +
 
 +
~SoilMilk
  
 
== See also ==
 
== See also ==
 
{{AIME box|year=2013|n=I|num-b=14|after=Last Problem}}
 
{{AIME box|year=2013|n=I|num-b=14|after=Last Problem}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Latest revision as of 22:14, 26 May 2023

Problem

Let $N$ be the number of ordered triples $(A,B,C)$ of integers satisfying the conditions (a) $0\le A<B<C\le99$, (b) there exist integers $a$, $b$, and $c$, and prime $p$ where $0\le b<a<c<p$, (c) $p$ divides $A-a$, $B-b$, and $C-c$, and (d) each ordered triple $(A,B,C)$ and each ordered triple $(b,a,c)$ form arithmetic sequences. Find $N$.

Solution

From condition (d), we have $(A,B,C)=(B-D,B,B+D)$ and $(b,a,c)=(a-d,a,a+d)$. Condition $\text{(c)}$ states that $p\mid B-D-a$, $p | B-a+d$, and $p\mid B+D-a-d$. We subtract the first two to get $p\mid-d-D$, and we do the same for the last two to get $p\mid 2d-D$. We subtract these two to get $p\mid 3d$. So $p\mid 3$ or $p\mid d$. The second case is clearly impossible, because that would make $c=a+d>p$, violating condition $\text{(b)}$. So we have $p\mid 3$, meaning $p=3$. Condition $\text{(b)}$ implies that $(b,a,c)=(0,1,2)$ or $(a,b,c)\in (1,0,2)\rightarrow (-2,0,2)\text{ }(D\equiv 2\text{ mod 3})$. Now we return to condition $\text{(c)}$, which now implies that $(A,B,C)\equiv(-2,0,2)\pmod{3}$. Now, we set $B=3k$ for increasing positive integer values of $k$. $B=0$ yields no solutions. $B=3$ gives $(A,B,C)=(1,3,5)$, giving us $1$ solution. If $B=6$, we get $2$ solutions, $(4,6,8)$ and $(1,6,11)$. Proceeding in the manner, we see that if $B=48$, we get 16 solutions. However, $B=51$ still gives $16$ solutions because $C_\text{max}=2B-1=101>100$. Likewise, $B=54$ gives $15$ solutions. This continues until $B=96$ gives one solution. $B=99$ gives no solution. Thus, $N=1+2+\cdots+16+16+15+\cdots+1=2\cdot\frac{16(17)}{2}=16\cdot 17=\boxed{272}$.


Solution 2

Let $(A, B, C)$ = $(B-x, B, B+x)$ and $(b, a, c) = (a-y, a, a+y)$. Now the 3 differences would be \begin{align} \label{1} &A-a = B-x-a \\ \label{2} &B - b = B-a+y \\ \label{3} &C - c = B+x-a-y \end{align}

Adding equations $(1)$ and $(3)$ would give $2B - 2a - y$. Then doubling equation $(2)$ would give $2B - 2a + 2y$. The difference between them would be $3y$. Since $p|\{(1), (2), (3)\}$, then $p|3y$. Since $p$ is prime, $p|3$ or $p|y$. However, since $p > y$, we must have $p|3$, which means $p=3$.


If $p=3$, the only possible values of $(b, a, c)$ are $(0, 1, 2)$. Plugging this into our differences, we get \begin{align*} &A-a = B-x-1 \hspace{4cm}(4)\\ &B - b = B \hspace{5.35cm}(5)\\ &C - c = B+x-2 \hspace{4cm}(6) \end{align*} The difference between $(4)$ and $(5)$ is $x+1$, which should be divisible by 3. So $x \equiv 2 \mod 3$. Also note that since $3|(5)$, $3|B$. Now we can try different values of $x$ and $B$:

When $x=2$, $B=3, 6, ..., 96 \Rightarrow 17$ triples.

When $x=5$, $B=6, 9, ..., 93\Rightarrow 15$ triples..

... and so on until

When $x=44$, $B=45\Rightarrow 1$ triple.

So the answer is $17 + 15 + \cdots + 1 = \boxed{272}$

~SoilMilk

See also

2013 AIME I (Problems • Answer Key • Resources)
Preceded by
Problem 14 		Followed by
Last Problem
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=2013_AIME_I_Problems/Problem_15&oldid=193570"