Difference between revisions of "2013 AIME I Problems/Problem 15"

Latest revision as of 13:34, 25 December 2024

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

Note:

$17 + 15 + \cdots + 1 = 81 \neq 272$ . The theory seems right until the actual counting starts.

~Aarush12.

@@ Line 10: / Line 10: @@
-==Solution2==
+==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
+== Note: ==
+<math>17 + 15 + \cdots + 1 = 81 \neq 272</math>. The theory seems right until the actual counting starts.
+~Aarush12.
 == See also ==
 {{AIME box|year=2013|n=I|num-b=14|after=Last Problem}}
 {{MAA Notice}}

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

Page

Toolbox

Search