1996 AIME Problems/Problem 3

Revision as of 03:29, 27 November 2023 by Coolishu (talk | contribs) (Solution 2 (Generating Functions))
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)


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


See also

1996 AIME (ProblemsAnswer KeyResources)
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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png