Difference between revisions of "1996 AIME Problems/Problem 3"
(→Solution FASTER) |
(→Solution 2 (Generating Functions)) |
||
(One intermediate revision by the same user not shown) | |||
Line 2: | Line 2: | ||
Find the smallest positive [[integer]] <math>n</math> for which the expansion of <math>(xy-3x+7y-21)^n</math>, after like terms have been collected, has at least 1996 terms. | Find the smallest positive [[integer]] <math>n</math> for which the expansion of <math>(xy-3x+7y-21)^n</math>, after like terms have been collected, has at least 1996 terms. | ||
− | == Solution == | + | == Solution 1== |
Using [[Simon's Favorite Factoring Trick]], we rewrite as <math>[(x+7)(y-3)]^n = (x+7)^n(y-3)^n</math>. Both [[binomial expansion]]s will contain <math>n+1</math> non-like terms; their product will contain <math>(n+1)^2</math> terms, as each term will have an unique power of <math>x</math> or <math>y</math> and so none of the terms will need to be collected. Hence <math>(n+1)^2 \ge 1996</math>, the smallest square after <math>1996</math> is <math>2025 = 45^2</math>, so our answer is <math>45 - 1 = \boxed{044}</math>. | Using [[Simon's Favorite Factoring Trick]], we rewrite as <math>[(x+7)(y-3)]^n = (x+7)^n(y-3)^n</math>. Both [[binomial expansion]]s will contain <math>n+1</math> non-like terms; their product will contain <math>(n+1)^2</math> terms, as each term will have an unique power of <math>x</math> or <math>y</math> and so none of the terms will need to be collected. Hence <math>(n+1)^2 \ge 1996</math>, the smallest square after <math>1996</math> is <math>2025 = 45^2</math>, so our answer is <math>45 - 1 = \boxed{044}</math>. | ||
Alternatively, when <math>n = k</math>, the exponents of <math>x</math> or <math>y</math> in <math>x^i y^i</math> can be any integer between <math>0</math> and <math>k</math> inclusive. Thus, when <math>n=1</math>, there are <math>(2)(2)</math> terms and, when <math>n = k</math>, there are <math>(k+1)^2</math> terms. Therefore, we need to find the smallest perfect square that is greater than <math>1996</math>. From trial and error, we get <math>44^2 = 1936</math> and <math>45^2 = 2025</math>. Thus, <math>k = 45\rightarrow n = \boxed{044}</math>. | Alternatively, when <math>n = k</math>, the exponents of <math>x</math> or <math>y</math> in <math>x^i y^i</math> can be any integer between <math>0</math> and <math>k</math> inclusive. Thus, when <math>n=1</math>, there are <math>(2)(2)</math> terms and, when <math>n = k</math>, there are <math>(k+1)^2</math> terms. Therefore, we need to find the smallest perfect square that is greater than <math>1996</math>. From trial and error, we get <math>44^2 = 1936</math> and <math>45^2 = 2025</math>. Thus, <math>k = 45\rightarrow n = \boxed{044}</math>. | ||
+ | |||
+ | == 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 <math>(xy+x+y+1)^n</math> (we do this to simplify the problem). | ||
+ | |||
+ | If we expand the exponent the expression becomes <math>\underbrace{(xy+x+y+1)\cdot(xy+x+y+1)\cdots(xy+x+y+1)}_{n\;times}</math>. | ||
+ | |||
+ | This is equivalent to starting off with a <math>x^0y^0</math> terms and choosing between <math>4</math> options <math>n</math> different times: | ||
+ | |||
+ | <math>\bullet</math> Adding nothing to either exponent (choosing <math>1</math>). | ||
+ | |||
+ | <math>\bullet</math> Adding <math>1</math> to the <math>x</math> exponent (choosing <math>x</math>). | ||
+ | |||
+ | <math>\bullet</math> Adding <math>1</math> to the <math>y</math> exponent (choosing <math>y</math>). | ||
+ | |||
+ | <math>\bullet</math> Adding <math>1</math> to the <math>x</math> exponent and adding <math>1</math> to the <math>y</math> exponent (choosing <math>xy</math>). | ||
+ | |||
+ | Doing this <math>n</math> times, you can see that you end up with a term in the form <math>k\cdot x^i\cdot y^j</math> where <math>k</math> is some coefficient (which we don't care about) and <math>0\le i,j\le n</math> and <math>i,j \in \mathbb{N}</math>. | ||
+ | |||
+ | Repeating this for all possible combinations of choices yields <math>n+1</math> options for each of <math>i</math> and <math>j</math> which means there are a total of <math>(n+1)^2</math> possible terms in the form <math>x^i\cdot y^j</math>. Therefore <math>(xy+x+y+1)^n</math> has <math>(n+1)^2</math> terms. | ||
+ | |||
+ | <math>(n+1)^2 \ge 1996</math> which yields <math>n=44</math>. <math>\boxed{044}</math> | ||
+ | |||
+ | ~coolishu | ||
== See also == | == See also == |
Latest revision as of 04:29, 27 November 2023
Problem
Find the smallest positive integer for which the expansion of
, after like terms have been collected, has at least 1996 terms.
Solution 1
Using Simon's Favorite Factoring Trick, we rewrite as . Both binomial expansions will contain
non-like terms; their product will contain
terms, as each term will have an unique power of
or
and so none of the terms will need to be collected. Hence
, the smallest square after
is
, so our answer is
.
Alternatively, when , the exponents of
or
in
can be any integer between
and
inclusive. Thus, when
, there are
terms and, when
, there are
terms. Therefore, we need to find the smallest perfect square that is greater than
. From trial and error, we get
and
. Thus,
.
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 (we do this to simplify the problem).
If we expand the exponent the expression becomes .
This is equivalent to starting off with a terms and choosing between
options
different times:
Adding nothing to either exponent (choosing
).
Adding
to the
exponent (choosing
).
Adding
to the
exponent (choosing
).
Adding
to the
exponent and adding
to the
exponent (choosing
).
Doing this times, you can see that you end up with a term in the form
where
is some coefficient (which we don't care about) and
and
.
Repeating this for all possible combinations of choices yields options for each of
and
which means there are a total of
possible terms in the form
. Therefore
has
terms.
which yields
.
~coolishu
See also
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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.