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 "1993 AIME Problems/Problem 4"

m
m (→‎Solution 1)
 
(30 intermediate revisions by 16 users not shown)
Line 2: Line 2:
 
How many ordered four-tuples of integers <math>(a,b,c,d)\,</math> with <math>0 < a < b < c < d < 500\,</math> satisfy <math>a + d = b + c\,</math> and <math>bc - ad = 93\,</math>?
 
How many ordered four-tuples of integers <math>(a,b,c,d)\,</math> with <math>0 < a < b < c < d < 500\,</math> satisfy <math>a + d = b + c\,</math> and <math>bc - ad = 93\,</math>?
  
 +
__TOC__
 
== Solution ==
 
== Solution ==
−
{{solution}}
+
=== Solution 1 ===
 +
Let <math>k = a + d = b + c</math> so <math>d = k-a, b=k-c</math>. It follows that <math>(k-c)c - a(k-a) = (a-c)(a+c-k) = (c-a)(d-c) = 93</math>. Hence <math>(c - a,d - c) = (1,93),(3,31),(31,3),(93,1)</math>.
 +
 
 +
Solve them in terms of <math>c</math> to get
 +
<math>(a,b,c,d) = (c - 93,c - 92,c,c + 1),</math> <math>(c - 31,c - 28,c,c + 3),</math> <math>(c - 1,c + 92,c,c + 93),</math> <math>(c - 3,c + 28,c,c + 31)</math>. The last two solutions don't follow <math>a < b < c < d</math>, so we only need to consider the first two solutions.
 +
 
 +
The first solution gives us <math>c - 93\geq 1</math> and <math>c + 1\leq 499</math> <math>\implies 94\leq c\leq 498</math>, and the second one gives us <math>32\leq c\leq 496</math>.
 +
 
 +
So the total number of such quadruples is <math>405 + 465 = \boxed{870}</math>.
 +
 
 +
=== Solution 2 ===
 +
Let <math>b = a + m</math> and <math>c = a + m + n</math>. From <math>a + d = b + c</math>, <math>d = b + c - a = a + 2m + n</math>.
 +
 
 +
Substituting <math>b = a + m</math>, <math>c = a + m + n</math>, and <math>d = b + c - a = a + 2m + n</math> into <math>bc - ad = 93</math>,
 +
<cmath>
 +
bc - ad = (a + m)(a + m + n) - a(a + 2m + n) = m(m + n). = 93 = 3(31)
 +
</cmath>
 +
Hence, <math>(m,n) = (1,92)</math> or <math>(3,28)</math>.
 +
 
 +
For <math>(m,n) = (1,92)</math>, we know that <math>0 < a < a + 1 < a + 93 < a + 94 < 500</math>, so there are <math>405</math> four-tuples. For <math>(m,n) = (3,28)</math>, <math>0 < a < a + 3 < a + 31 < a + 34 < 500</math>, and there are <math>465</math> four-tuples. In total, we have <math>405 + 465 = \boxed{870}</math> four-tuples.
 +
 
 +
=== Solution 3 ===
 +
Square both sides of the first equation in order to get <math>bc</math> and <math>ad</math> terms, which we can plug <math>93</math> in for.
 +
<cmath>\begin{align*}
 +
(a+d)^2 = (b+c)^2 &\implies a^2 + 2ad + d^2 = b^2 + 2bc + c^2 \\
 +
&\implies 2bc-2ad = a^2-b^2 + d^2-c^2 \\
 +
&\implies 2(bc-ad) = (a-b)(a+b)+(d-c)(d+c)
 +
\end{align*}</cmath>
 +
We can plug <math>93</math> in for <math>bc - ad</math> to get <math>186</math> on the left side, and also observe that <math>a-b = c-d</math> after rearranging the first equation. Plug in <math>c-d</math> for <math>a-b</math>.
 +
 
 +
<math>186 = (c-d)(a+b) + (d-c)(d+c) \implies 186 = -(d-c)(a+b) + (d-c)(d+c) \implies 186 = (d-c)(d+c-a-b)</math>
 +
 
 +
Now observe the possible factors of <math>186</math>, which are <math>1 \cdot 186, 2\cdot 93, 3 \cdot 62, 6\cdot 31</math>. <math>(d-c)</math> and <math>(d+c-a-b)</math> must be factors of <math>186</math>, and <math>(d+c-a-b)</math> must be greater than <math>(d-c)</math>.
 +
 
 +
<math>1 \cdot 186</math> work, and yields <math>405</math> possible solutions.
 +
<math>2 \cdot 93</math> does not work, because if <math>c-d = 2</math>, then <math>a+b</math> must differ by 2 as well, but an odd number <math>93</math> can only result from two numbers of different parity. <math>c-d</math> will be even, and <math>a+b</math> will be even, so <math>c+d - (a+b)</math> must be even.
 +
<math>3 \cdot 62</math> works, and yields <math>465</math> possible solutions, while <math>6 \cdot 31</math> fails for the same reasoning above.
 +
 
 +
Thus, the answer is <math>405 + 465 = \boxed{870}</math>
 +
 
 +
===Solution 4===
 +
 
 +
Add the two conditions together to get <math>a+d+ad+93=b+c+bc</math>. Rearranging and factorising with SFFT, <math>(a+1)(d+1)+93=(b+1)(c+1)</math>. This implies that for every quadruple <math>(a,b,c,d)</math>, we can replace <math>a\longrightarrow a+1</math>, <math>b\longrightarrow b+1</math>, etc. and this will still produce a valid quadruple. This means, that we can fix <math>a=1</math>, and then just repeatedly add <math>1</math> to get the other quadruples.
 +
 
 +
Now, our conditions are <math>b+c=d+1</math> and <math>bc=d+93</math>. Replacing <math>d</math> in the first equation, we get <math>bc-b-c=92</math>. Factorising again with SFFT gives <math>(b-1)(c-1)=93</math>. Since <math>b<c</math>, we have two possible cases to consider.
 +
 
 +
Case 1: <math>b=2</math>, <math>c=94</math>. This produces the quadruple <math>(1,2,94,95)</math>, which indeed works.
 +
 
 +
Case 2: <math>b=4</math>, <math>c=32</math>. This produces the quadruple <math>(1,4,32,35)</math>, which indeed works.
 +
 
 +
Now, for case 1, we can add <math>1</math> to each term exactly <math>404</math> times (until we get the quadruple <math>(405,406,498,499)</math>), until we violate <math>d<500</math>. This gives <math>405</math> quadruples for case 1.
 +
 
 +
For case 2, we can add <math>1</math> to each term exactly <math>464</math> times (until we get the quadruple <math>(465,468,496,499)</math>). this gives <math>465</math> quadruples for case 2.
 +
 
 +
In conclusion, having exhausted all cases, we can finish. There are hence <math>405+465=\boxed{870}</math> possible quadruples.
 +
 
 +
===Solution 5===
 +
 
 +
Let <math>r = d-c</math>. From the equation <math>a+d = b+c</math>, we have <cmath> r = d-c = b-a , </cmath> so <math>b = a+r</math> and <math>c = d-r</math>. We then have <cmath> 93 = (a+r)(d-r) - ad = rd - ra - r^2 = r(d-a-r) . </cmath> Since <math>c > b</math>, <math>d-r > a+r</math>, or <math>d-a-r > r</math>. Since the prime factorization of 93 is <math>3 \cdot 31</math>, we must either have <math>r=1</math> and <math>d-a-r = 93</math>, or <math>r=3</math> and <math>d-a-r = 31</math>. We consider these cases separately.
 +
 
 +
If <math>r=1</math>, then <math>d-a = 94</math>, <math>b= a+1</math>, and <math>c = d-1</math>. Thus <math>d</math> can be any integer between 95 and 499, inclusive, and our choice of <math>d</math> determines the four-tuple <math>(a,b,c,d)</math>. We therefore have <math>499-95+1 = 405</math> possibilities in this case.
 +
 
 +
If <math>r=3</math>, then <math>d-a = 34</math>, <math>b = a+3</math>, and <math>c=d-3</math>. Thus <math>d</math> can be any integer between 35 and 499, inclusive, and our choice of <math>d</math> determines the four-tuple <math>(a,b,c,d)</math>, as before. We therefore have <math>499-35+1 = 465</math> possibilities in this case.
 +
 
 +
Since there are 405 possibilities in the first case and 465 possibilities in the second case, in total there are <math>405 + 465 = \boxed{870}</math> four-tuples.
 +
 
 +
==Solution 6==
 +
 
 +
Assume <math>d = x+m, a = x-m, c = x+n</math>, and <math>b = x-n</math>. This clearly satisfies the condition that <math>a+d = b+c</math> since (<math>2x = 2x</math>) . Now plug this into <math>bc-ad = 93</math>. You get <math>(x+n)(x-n) - (x+m)(x-m) = 93 \Rightarrow m^2 - n^2 = 93 \Rightarrow (m-n)(m+n) = 93</math>
 +
 
 +
Since <math>m>n</math> (as given by the condition that <math>a<b<c<d</math>), <math>m+n>m-n</math> and <math>m</math> and <math>n</math> are integers, there are two cases we have to consider since <math>93 = 3\cdot 31</math>. We first have to consider <math>m-n = 1, m+n = 93</math>, and then consider <math>m-n=3, m+n = 31</math>.
 +
 
 +
In the first case, we get <math>m=47, n=46</math> and in the second case we get <math>m=17, n=14</math>. Now plug these values (in separate cases) back into <math>a,b,c,d</math>. Since the only restriction is that all numbers have to be greater than <math>0</math> or less than <math>500</math>, we can write two inequalities. Either <math>x+47 < 500, x-47 > 0</math>, or <math>x+17 < 500, x-17 > 0</math> (using the inequalities given by <math>d</math> and <math>a</math>, and since <math>b</math> and <math>c</math> are squeezed in between <math>d</math> and <math>a</math>, we only have to consider these two inequalities).
 +
 
 +
This gives us either <math>47 < x < 453</math> or <math>17 < x < 483</math>, and using simple counting, there are <math>405</math> values for <math>x</math> in the first case and <math>465</math> values for <math>x</math> in the second case, and hence our answer is <math>405+465 = \boxed{870}</math>
  
 
== See also ==
 
== See also ==
 
{{AIME box|year=1993|num-b=3|num-a=5}}
 
{{AIME box|year=1993|num-b=3|num-a=5}}
 +
 +
[[Category:Intermediate Algebra Problems]]
 +
{{MAA Notice}}

Latest revision as of 15:27, 19 December 2023

Problem

How many ordered four-tuples of integers $(a,b,c,d)\,$ with $0 < a < b < c < d < 500\,$ satisfy $a + d = b + c\,$ and $bc - ad = 93\,$?

Solution

Solution 1

Let $k = a + d = b + c$ so $d = k-a, b=k-c$. It follows that $(k-c)c - a(k-a) = (a-c)(a+c-k) = (c-a)(d-c) = 93$. Hence $(c - a,d - c) = (1,93),(3,31),(31,3),(93,1)$.

Solve them in terms of $c$ to get $(a,b,c,d) = (c - 93,c - 92,c,c + 1),$ $(c - 31,c - 28,c,c + 3),$ $(c - 1,c + 92,c,c + 93),$ $(c - 3,c + 28,c,c + 31)$. The last two solutions don't follow $a < b < c < d$, so we only need to consider the first two solutions.

The first solution gives us $c - 93\geq 1$ and $c + 1\leq 499$ $\implies 94\leq c\leq 498$, and the second one gives us $32\leq c\leq 496$.

So the total number of such quadruples is $405 + 465 = \boxed{870}$.

Solution 2

Let $b = a + m$ and $c = a + m + n$. From $a + d = b + c$, $d = b + c - a = a + 2m + n$.

Substituting $b = a + m$, $c = a + m + n$, and $d = b + c - a = a + 2m + n$ into $bc - ad = 93$, \[bc - ad = (a + m)(a + m + n) - a(a + 2m + n) = m(m + n). = 93 = 3(31)\] Hence, $(m,n) = (1,92)$ or $(3,28)$.

For $(m,n) = (1,92)$, we know that $0 < a < a + 1 < a + 93 < a + 94 < 500$, so there are $405$ four-tuples. For $(m,n) = (3,28)$, $0 < a < a + 3 < a + 31 < a + 34 < 500$, and there are $465$ four-tuples. In total, we have $405 + 465 = \boxed{870}$ four-tuples.

Solution 3

Square both sides of the first equation in order to get $bc$ and $ad$ terms, which we can plug $93$ in for. \begin{align*} (a+d)^2 = (b+c)^2 &\implies a^2 + 2ad + d^2 = b^2 + 2bc + c^2 \\ &\implies 2bc-2ad = a^2-b^2 + d^2-c^2 \\ &\implies 2(bc-ad) = (a-b)(a+b)+(d-c)(d+c) \end{align*} We can plug $93$ in for $bc - ad$ to get $186$ on the left side, and also observe that $a-b = c-d$ after rearranging the first equation. Plug in $c-d$ for $a-b$.

$186 = (c-d)(a+b) + (d-c)(d+c) \implies 186 = -(d-c)(a+b) + (d-c)(d+c) \implies 186 = (d-c)(d+c-a-b)$

Now observe the possible factors of $186$, which are $1 \cdot 186, 2\cdot 93, 3 \cdot 62, 6\cdot 31$. $(d-c)$ and $(d+c-a-b)$ must be factors of $186$, and $(d+c-a-b)$ must be greater than $(d-c)$.

$1 \cdot 186$ work, and yields $405$ possible solutions. $2 \cdot 93$ does not work, because if $c-d = 2$, then $a+b$ must differ by 2 as well, but an odd number $93$ can only result from two numbers of different parity. $c-d$ will be even, and $a+b$ will be even, so $c+d - (a+b)$ must be even. $3 \cdot 62$ works, and yields $465$ possible solutions, while $6 \cdot 31$ fails for the same reasoning above.

Thus, the answer is $405 + 465 = \boxed{870}$

Solution 4

Add the two conditions together to get $a+d+ad+93=b+c+bc$. Rearranging and factorising with SFFT, $(a+1)(d+1)+93=(b+1)(c+1)$. This implies that for every quadruple $(a,b,c,d)$, we can replace $a\longrightarrow a+1$, $b\longrightarrow b+1$, etc. and this will still produce a valid quadruple. This means, that we can fix $a=1$, and then just repeatedly add $1$ to get the other quadruples.

Now, our conditions are $b+c=d+1$ and $bc=d+93$. Replacing $d$ in the first equation, we get $bc-b-c=92$. Factorising again with SFFT gives $(b-1)(c-1)=93$. Since $b<c$, we have two possible cases to consider.

Case 1: $b=2$, $c=94$. This produces the quadruple $(1,2,94,95)$, which indeed works.

Case 2: $b=4$, $c=32$. This produces the quadruple $(1,4,32,35)$, which indeed works.

Now, for case 1, we can add $1$ to each term exactly $404$ times (until we get the quadruple $(405,406,498,499)$), until we violate $d<500$. This gives $405$ quadruples for case 1.

For case 2, we can add $1$ to each term exactly $464$ times (until we get the quadruple $(465,468,496,499)$). this gives $465$ quadruples for case 2.

In conclusion, having exhausted all cases, we can finish. There are hence $405+465=\boxed{870}$ possible quadruples.

Solution 5

Let $r = d-c$. From the equation $a+d = b+c$, we have \[r = d-c = b-a ,\] so $b = a+r$ and $c = d-r$. We then have \[93 = (a+r)(d-r) - ad = rd - ra - r^2 = r(d-a-r) .\] Since $c > b$, $d-r > a+r$, or $d-a-r > r$. Since the prime factorization of 93 is $3 \cdot 31$, we must either have $r=1$ and $d-a-r = 93$, or $r=3$ and $d-a-r = 31$. We consider these cases separately.

If $r=1$, then $d-a = 94$, $b= a+1$, and $c = d-1$. Thus $d$ can be any integer between 95 and 499, inclusive, and our choice of $d$ determines the four-tuple $(a,b,c,d)$. We therefore have $499-95+1 = 405$ possibilities in this case.

If $r=3$, then $d-a = 34$, $b = a+3$, and $c=d-3$. Thus $d$ can be any integer between 35 and 499, inclusive, and our choice of $d$ determines the four-tuple $(a,b,c,d)$, as before. We therefore have $499-35+1 = 465$ possibilities in this case.

Since there are 405 possibilities in the first case and 465 possibilities in the second case, in total there are $405 + 465 = \boxed{870}$ four-tuples.

Solution 6

Assume $d = x+m, a = x-m, c = x+n$, and $b = x-n$. This clearly satisfies the condition that $a+d = b+c$ since ($2x = 2x$) . Now plug this into $bc-ad = 93$. You get $(x+n)(x-n) - (x+m)(x-m) = 93 \Rightarrow m^2 - n^2 = 93 \Rightarrow (m-n)(m+n) = 93$

Since $m>n$ (as given by the condition that $a<b<c<d$), $m+n>m-n$ and $m$ and $n$ are integers, there are two cases we have to consider since $93 = 3\cdot 31$. We first have to consider $m-n = 1, m+n = 93$, and then consider $m-n=3, m+n = 31$.

In the first case, we get $m=47, n=46$ and in the second case we get $m=17, n=14$. Now plug these values (in separate cases) back into $a,b,c,d$. Since the only restriction is that all numbers have to be greater than $0$ or less than $500$, we can write two inequalities. Either $x+47 < 500, x-47 > 0$, or $x+17 < 500, x-17 > 0$ (using the inequalities given by $d$ and $a$, and since $b$ and $c$ are squeezed in between $d$ and $a$, we only have to consider these two inequalities).

This gives us either $47 < x < 453$ or $17 < x < 483$, and using simple counting, there are $405$ values for $x$ in the first case and $465$ values for $x$ in the second case, and hence our answer is $405+465 = \boxed{870}$

See also

1993 AIME (Problems • Answer Key • Resources)
Preceded by
Problem 3 		Followed by
Problem 5
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=1993_AIME_Problems/Problem_4&oldid=207907"