Difference between revisions of "1993 AIME Problems/Problem 4"

Revision as of 17:58, 27 March 2020

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 tems 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 four-tuples is $405 + 465 = \giant{\boxed{870}}$ (Error compiling LaTeX. Unknown error_msg).

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 = (1 + m)(1 + 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.

$(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)$

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

@@ Line 12: / Line 12: @@
 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 four-tuples is <math>405 + 465 = \huge{\boxed{870}}</math>.
+So the total number of such four-tuples is <math>405 + 465 = \giant{\boxed{870}}</math>.
 === Solution 2 ===

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

Page

Toolbox

Search