1996 AIME Problems/Problem 3

Problem

Find the smallest positive integer $n$ for which the expansion of $(xy-3x+7y-21)^n$ , after like terms have been collected, has at least 1996 terms.

Solution 1

Using Simon's Favorite Factoring Trick, we rewrite as $[(x+7)(y-3)]^n = (x+7)^n(y-3)^n$ . Both binomial expansions will contain $n+1$ non-like terms; their product will contain $(n+1)^2$ terms, as each term will have an unique power of $x$ or $y$ and so none of the terms will need to be collected. Hence $(n+1)^2 \ge 1996$ , the smallest square after $1996$ is $2025 = 45^2$ , so our answer is $45 - 1 = \boxed{044}$ .

Alternatively, when $n = k$ , the exponents of $x$ or $y$ in $x^i y^i$ can be any integer between $0$ and $k$ inclusive. Thus, when $n=1$ , there are $(2)(2)$ terms and, when $n = k$ , there are $(k+1)^2$ terms. Therefore, we need to find the smallest perfect square that is greater than $1996$ . From trial and error, we get $44^2 = 1936$ and $45^2 = 2025$ . Thus, $k = 45\rightarrow n = \boxed{044}$ .

Solution 2 (Generating Functions)

Notice that the coefficients in the problem statement have no effect on how many unique terms there will be in the expansion. Therefore this problem is synonymous with finding the amount of terms in the expansion of $(xy+x+y+1)^n$ (we do this to simplify the problem).

If we expand the exponent the expression becomes $\underbrace{(xy+x+y+1)\cdot(xy+x+y+1)\cdots(xy+x+y+1)}_{n\;times}$ .

This is equivalent to starting off with a $x^0y^0$ terms and choosing between $4$ options $n$ different times:

$\bullet$ Adding nothing to either exponent (choosing $1$ ).

$\bullet$ Adding $1$ to the $x$ exponent (choosing $x$ ).

$\bullet$ Adding $1$ to the $y$ exponent (choosing $y$ ).

$\bullet$ Adding $1$ to the $x$ exponent and adding $1$ to the $y$ exponent (choosing $xy$ ).

Doing this $n$ times, you can see that you end up with a term in the form $k\cdot x^i\cdot y^j$ where $k$ is some coefficient (which we don't care about) and $0\le i,j\le n$ and $i,j \in \mathbb{N}$ .

Repeating this for all possible combinations of choices yields $n+1$ options for each of $i$ and $j$ which means there are a total of $(n+1)^2$ possible terms in the form $x^i\cdot y^j$ . Therefore $(xy+x+y+1)^n$ has $(n+1)^2$ terms.

$(n+1)^2 \ge 1996$ which yields $n=44$ . $\boxed{044}$

~coolishu

1996 AIME (Problems • Answer Key • Resources)
Preceded by Problem 2	Followed by Problem 4
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

Page

Toolbox

Search

1996 AIME Problems/Problem 3

Contents

Problem

Solution 1

Solution 2 (Generating Functions)

See also