Difference between revisions of "2008 AIME I Problems/Problem 9"
m (→Solution) |
Jeffersonj (talk | contribs) |
||
(17 intermediate revisions by 6 users not shown) | |||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
− | Ten identical crates each of dimensions <math>3 | + | Ten identical crates each of dimensions <math>3\mathrm{ft}\times 4\mathrm{ft}\times 6\mathrm{ft}</math>. The first crate is placed flat on the floor. Each of the remaining nine crates is placed, in turn, flat on top of the previous crate, and the orientation of each crate is chosen at random. Let <math>\frac {m}{n}</math> be the probability that the stack of crates is exactly <math>41\mathrm{ft}</math> tall, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m</math>. |
== Solution == | == Solution == | ||
Line 10: | Line 10: | ||
Subtracting 3 times the second from the first gives <math>b + 3c = 11</math>, or <math>(b,c) = (2,3),(5,2),(8,1),(11,0)</math>. The last doesn't work, obviously. This gives the three solutions <math>(a,b,c) = (5,2,3),(3,5,2),(1,8,1)</math>. In terms of choosing which goes where, the first two solutions are analogous. | Subtracting 3 times the second from the first gives <math>b + 3c = 11</math>, or <math>(b,c) = (2,3),(5,2),(8,1),(11,0)</math>. The last doesn't work, obviously. This gives the three solutions <math>(a,b,c) = (5,2,3),(3,5,2),(1,8,1)</math>. In terms of choosing which goes where, the first two solutions are analogous. | ||
− | For <math>(5,2,3),(3,5,2)</math>, we see that there are <math>2\cdot\dfrac{10!}{5!2!3!} = 10\cdot9\cdot8\cdot7</math> ways to stack the crates. For <math>(1,8,1)</math>, there are <math> | + | For <math>(5,2,3),(3,5,2)</math>, we see that there are <math>2\cdot\dfrac{10!}{5!2!3!} = 10\cdot9\cdot8\cdot7</math> ways to stack the crates. For <math>(1,8,1)</math>, there are <math>\dfrac{10!}{8!1!1!} = 90</math>. Also, there are <math>3^{10}</math> total ways to stack the crates to any height. |
Thus, our probability is <math>\dfrac{10\cdot9\cdot8\cdot7 + 90}{3^{10}} = \dfrac{10\cdot8\cdot7 + 10}{3^{8}} = \dfrac{570}{3^8} = \dfrac{190}{3^{7}}</math>. Our answer is the numerator, <math>\boxed{190}</math>. | Thus, our probability is <math>\dfrac{10\cdot9\cdot8\cdot7 + 90}{3^{10}} = \dfrac{10\cdot8\cdot7 + 10}{3^{8}} = \dfrac{570}{3^8} = \dfrac{190}{3^{7}}</math>. Our answer is the numerator, <math>\boxed{190}</math>. | ||
+ | |||
+ | ==1 Min Solution== | ||
+ | It would be helpful for this solution to be reformatted. To start with, let us observe the three numbers. Note that <math>3</math> and <math>6</math> are both divisible by <math>3</math>, so the number of <math>4</math>-crates must be congruent to <math>41\bmod{3}</math>, which is also congruent to <math>2\bmod{3}</math>. Our solutions for the number of <math>4</math>-crates will repeat mod <math>3</math>, so if <math>x</math> is a solution, so is <math>x+3</math>. By inspection, we have that <math>2</math> is solution, and so are <math>5</math> and <math>8</math>. Each solution splits into its own case.We must solve the equation <math>41-4z=6x+3y</math>, simultaneously with <math>x+y=10-z</math>. Note that we already know the possible values of <math>z</math>. Solving these (it's AIME <math>9</math>, you should be able to do this and if anyone feels like they want to write a rundown of this please go ahead), we get the solution sets <math>\{8,1,1\},\{5,2,3\},</math> and <math>\{2,3,5\}</math>. We can count the number of possible arrangements for each solution by taking <math>\dbinom{10}{z}</math> and then multiplying by <math>\dbinom{10-z}{x}</math> (the solution sets, for the sake of consistency, are in the form <math>z,x,y</math>). Summing the results for all the solutions gives us <math>5130</math>. Finally, to calculate the probability we must determine our denominator. Since we have <math>3</math> ways to arrange each block, our denominator is <math>3^{10}</math>. <math>\frac{5130}{3^{10}}=\frac{190}{3^7}</math>. The answer is <math>m=\boxed{190}</math>. | ||
+ | |||
+ | ==Solution 2 (a more direct approach)== | ||
+ | Let's make two observations. We are trying to find the number of ways we can add <math>3\text{s}, 4\text{s}</math>, and <math>6\text{s}</math> to get <math>41</math>, and the total number of (non-distinct) sums possible is <math>3^{10}</math>. | ||
+ | Then we just use casework to easily and directly solve for the number of ways to get <math>41</math>. To begin, the minimum sum is produced with <math>10</math> threes, so WLOG we can solve for the number of ways to get <math>11</math> with <math>0\text{s}, 1\text{s}</math>, and <math>3\text{s}</math>. | ||
+ | |||
+ | Case I: <math>0</math> zeroes, <math>0</math> threes, <math>11</math> ones | ||
+ | Impossible, because there are only ten available spots. | ||
+ | |||
+ | Case II: <math>1</math> zero, <math>1</math> three, <math>8</math> ones | ||
+ | This is just <math>\frac{10!}{8!}</math>, so there are <math>90</math> possibilities. | ||
+ | |||
+ | Case III: <math>3</math> zeroes, <math>2</math> threes, <math>5</math> ones | ||
+ | This is just <math>\frac{10!}{3!2!5!}</math>. This gives <math>2520</math> possibilities. | ||
+ | |||
+ | Case IV: 5 zeroes, 3 threes, and 2 ones. | ||
+ | This is the same as case <math>3</math>, so also <math>2520</math> possibilities. | ||
+ | |||
+ | <math>90+2520+2520=5130</math> | ||
+ | |||
+ | <math>5130</math> has three powers of <math>3</math>, so <math>5130</math> divided by <math>27</math> is <math>\boxed{190}</math>. | ||
+ | |||
+ | -jackshi2006 | ||
+ | |||
+ | ==Solution 3 (Generating Functions)== | ||
+ | Note we are placing 10 crates where each "height" is 3, 4, 6 and we want all the heights to sum to 41. | ||
+ | We can model this as the generating function <cmath>\left(x^3+x^4+x^6\right)^{10}</cmath> where we want the coefficient of <math>x^{41}.</math> | ||
+ | First off, factor this to get <cmath>{x^3}^{10}\left(1+x+x^3\right)^{10}</cmath> and then see that we want the coefficient of <math>x^{11}</math> in <math>\left(1+x+x^3\right)^{10}.</math> | ||
+ | From multinomial theorem, this expansion is <cmath>\sum_{a+b+c=10}\binom{10}{a,b,c}1^ax^bx^{3c}</cmath> | ||
+ | If we want the coefficient of <math>x^{11}</math> then we need <math>b + 3c = 11.</math> with <math>b + c \le 10</math>(from the multinomial expansion). | ||
+ | This has the solutions <math>(b, c) = \{8, 1\}, \{5, 2\}, \{2, 3\}.</math> Note that the denominator of the answer is just <math>3^{10}</math> since there are 3 ways to orientate every crate and there are 10 creates. Thus, our answer is | ||
+ | <cmath>\frac{\binom{10}{8,1,1} + \binom{10}{5,2,3} + \binom{10}{2,3,5}}{3^{10}} = \frac{190}{3^7} \rightarrow \boxed{190}</cmath> | ||
+ | |||
+ | ==Video Solution (Very fast)== | ||
+ | https://www.youtube.com/watch?v=qeSY_ISSX6M&t=33s | ||
+ | |||
+ | ~fidgetboss_4000 | ||
== See also == | == See also == | ||
{{AIME box|year=2008|n=I|num-b=8|num-a=10}} | {{AIME box|year=2008|n=I|num-b=8|num-a=10}} | ||
− | + | [[Category:Intermediate Combinatorics Problems]] | |
+ | [[Category:Intermediate Number Theory Problems]] | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 15:39, 8 August 2022
Contents
Problem
Ten identical crates each of dimensions . The first crate is placed flat on the floor. Each of the remaining nine crates is placed, in turn, flat on top of the previous crate, and the orientation of each crate is chosen at random. Let
be the probability that the stack of crates is exactly
tall, where
and
are relatively prime positive integers. Find
.
Solution
Only the heights matter, and each crate is either 3, 4, or 6 feet tall with equal probability. We have the following:
Subtracting 3 times the second from the first gives , or
. The last doesn't work, obviously. This gives the three solutions
. In terms of choosing which goes where, the first two solutions are analogous.
For , we see that there are
ways to stack the crates. For
, there are
. Also, there are
total ways to stack the crates to any height.
Thus, our probability is . Our answer is the numerator,
.
1 Min Solution
It would be helpful for this solution to be reformatted. To start with, let us observe the three numbers. Note that and
are both divisible by
, so the number of
-crates must be congruent to
, which is also congruent to
. Our solutions for the number of
-crates will repeat mod
, so if
is a solution, so is
. By inspection, we have that
is solution, and so are
and
. Each solution splits into its own case.We must solve the equation
, simultaneously with
. Note that we already know the possible values of
. Solving these (it's AIME
, you should be able to do this and if anyone feels like they want to write a rundown of this please go ahead), we get the solution sets
and
. We can count the number of possible arrangements for each solution by taking
and then multiplying by
(the solution sets, for the sake of consistency, are in the form
). Summing the results for all the solutions gives us
. Finally, to calculate the probability we must determine our denominator. Since we have
ways to arrange each block, our denominator is
.
. The answer is
.
Solution 2 (a more direct approach)
Let's make two observations. We are trying to find the number of ways we can add , and
to get
, and the total number of (non-distinct) sums possible is
.
Then we just use casework to easily and directly solve for the number of ways to get
. To begin, the minimum sum is produced with
threes, so WLOG we can solve for the number of ways to get
with
, and
.
Case I: zeroes,
threes,
ones
Impossible, because there are only ten available spots.
Case II: zero,
three,
ones
This is just
, so there are
possibilities.
Case III: zeroes,
threes,
ones
This is just
. This gives
possibilities.
Case IV: 5 zeroes, 3 threes, and 2 ones.
This is the same as case , so also
possibilities.
has three powers of
, so
divided by
is
.
-jackshi2006
Solution 3 (Generating Functions)
Note we are placing 10 crates where each "height" is 3, 4, 6 and we want all the heights to sum to 41.
We can model this as the generating function where we want the coefficient of
First off, factor this to get
and then see that we want the coefficient of
in
From multinomial theorem, this expansion is
If we want the coefficient of
then we need
with
(from the multinomial expansion).
This has the solutions
Note that the denominator of the answer is just
since there are 3 ways to orientate every crate and there are 10 creates. Thus, our answer is
Video Solution (Very fast)
https://www.youtube.com/watch?v=qeSY_ISSX6M&t=33s
~fidgetboss_4000
See also
2008 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 8 |
Followed by Problem 10 | |
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.