Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2023 AMC 12B Problems/Problem 23"

(→‎Solution 2 (Informal))
Line 4: Line 4:
 
<math>\textbf{(A)}~11\qquad\textbf{(B)}~6\qquad\textbf{(C)}~8\qquad\textbf{(D)}~10\qquad\textbf{(E)}~9</math>
 
<math>\textbf{(A)}~11\qquad\textbf{(B)}~6\qquad\textbf{(C)}~8\qquad\textbf{(D)}~10\qquad\textbf{(E)}~9</math>
  
−
==Solution1==
+
 
 +
==Solution 1 (In Progress)==
 +
 
 +
We start by trying to prove a function of <math>n</math>, and then we can apply the function and equate it to <math>936</math> to find the value of <math>n</math>.
 +
 
 +
It is helpful to think of this problem in the format <math>(1+2+3+4+5+6) \cdot (1+2+3+4+5+6) \dots</math>. Note that if we represent the scenario in this manner, we can think of picking a <math>1</math> for one factor and then a <math>5</math> for another factor to form their product - this is similar thinking to when we have the factorized form of a polynomial. Unfortunately this is not quite accurate to the problem because we can reach the same product in many ways: for example for <math>n=2</math>, <math>4</math> can be reached by picking <math>1</math> and <math>4</math> or <math>2</math> and <math>2</math>. However, this form gives us insights that will be useful later in the problem.
 +
 
 +
Note that there are only <math>3</math> primes in the set <math>\{1,2,3,4,5,6\}</math>: <math>2,3,</math> and <math>5</math>. Thus if we're forming the product of possible values of a dice roll, the product has to be written in the form <math>2^h \cdot 3^i \cdot 5^j</math> (the choice of variables will become clear later), for integer nonnegative values <math>h,i,j</math>. So now the problem boils down to how many distinct triplets <math>(h,i,j)</math> can be formed by taking the product of <math>n</math> dice values.
 +
 
 +
We start our work on representing <math>j</math>: the powers of <math>5</math>, because it is the simplest in this scenario because there is only one factor of <math>5</math> in the set. Because of this, having <math>j</math> fives in our prime factorization of the product is equivalent to picking <math>j</math> factors from the polynomial <math>(1+\dots + 6) \cdots</math> and choosing each factor to be a <math>5</math>. Now that we've selected <math>j</math> factors, there are <math>n-j</math> factors remaining to choose our powers of <math>3</math> and <math>2</math>.
 +
 
 +
Suppose our prime factorization of this product contains <math>i</math> powers of <math>3</math>. These powers of <math>3</math> can either come from a <math>3</math> factor or a <math>6</math> factor, but since both <math>3</math> and <math>6</math> contain only one power of <math>3</math>, this means that a product with <math>i</math> powers of <math>3</math> corresponds directly to picking <math>i</math> factors from the polynomial, each of which is either <math>3</math> or <math>6</math> (but this distinction doesn't matter when we consider only the powers of <math>3</math>.
 +
 
 +
Now we can reframe the problem again. Our method will be as follows: Suppose we choose an arbitrary pair <math>(i,j)</math> that match the requirements, corresponding to the number of <math>3</math>'s and the number of <math>5</math>'s our product will have. Then how many different <math>h</math> values for the powers of <math>2</math> are possible?
 +
 
 +
In the <math>i+j</math> factors we have already chosen, we obviously can't have any factors of <math>2</math> in the <math>j</math> factors with <math>5</math>. However, we can have a factor of <math>2</math> pairing with factors of <math>3</math>, if we choose a <math>6</math>. The maximal possible power of <math>2</math> in these <math>i</math> factors is thus <math>2^i</math>, which occurs when we pick every factor to be <math>6</math>.
 +
 
 +
We now have <math>n-i-j</math> factors remaining, and we want to allocate these to solely powers of <math>2</math>. For each of these factors, we can choose either a <math>1,2,</math> or <math>4</math>. Therefore the maximal power of <math>2</math> achieved in these factors is when we pick <math>4</math> for all of them, which is equivalent to <math>2^{2\cdot (n-i-j)}</math>.
 +
 
 +
Now if we multiply this across the total <math>n</math> factors (or <math>n</math> dice) we have a total of <math>2^{2n-2i-2j} \cdot 2^i = 2^{2n-i-2j}</math>, which is the maximal power of <math>2</math> attainable in the product for a pair <math>(i,j)</math>. Now note that every power of <math>2</math> below this power is attainable: we can simply just take away a power of <math>2</math> from an existing factor by dividing by <math>2</math>. Therefore the powers of <math>2</math>, and thus the <math>h</math> value ranges from <math>h=0</math> to <math>h=2n-i-2j</math>, so there are a total of <math>2n+1-i-2j</math> distinct values for <math>h</math> for a given pair <math>(i,j)</math>.
 +
 
 +
Now to find the total number of distinct triplets, we must sum this across all possible <math>i</math>s and <math>j</math>s. Lets take note of our restrictions on <math>i,j</math>: the only restriction is that <math>i+j \leq n</math>, since we're picking factors from <math>n</math> dice.
 +
 
 +
 
 +
 
 +
 
 +
~KingRavi
 +
 
 +
 
 +
 
 +
==Solution 2==
  
 
The product can be written as  
 
The product can be written as  
Line 60: Line 90:
 
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
 
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
  
−
==Solution 2 (Cheese)==
+
==Solution 3 (Cheese)==
  
 
The product can be written as
 
The product can be written as

Revision as of 01:05, 17 November 2023

Problem

When $n$ standard six-sided dice are rolled, the product of the numbers rolled can be any of $936$ possible values. What is $n$?

$\textbf{(A)}~11\qquad\textbf{(B)}~6\qquad\textbf{(C)}~8\qquad\textbf{(D)}~10\qquad\textbf{(E)}~9$


Solution 1 (In Progress)

We start by trying to prove a function of $n$, and then we can apply the function and equate it to $936$ to find the value of $n$.

It is helpful to think of this problem in the format $(1+2+3+4+5+6) \cdot (1+2+3+4+5+6) \dots$. Note that if we represent the scenario in this manner, we can think of picking a $1$ for one factor and then a $5$ for another factor to form their product - this is similar thinking to when we have the factorized form of a polynomial. Unfortunately this is not quite accurate to the problem because we can reach the same product in many ways: for example for $n=2$, $4$ can be reached by picking $1$ and $4$ or $2$ and $2$. However, this form gives us insights that will be useful later in the problem.

Note that there are only $3$ primes in the set $\{1,2,3,4,5,6\}$: $2,3,$ and $5$. Thus if we're forming the product of possible values of a dice roll, the product has to be written in the form $2^h \cdot 3^i \cdot 5^j$ (the choice of variables will become clear later), for integer nonnegative values $h,i,j$. So now the problem boils down to how many distinct triplets $(h,i,j)$ can be formed by taking the product of $n$ dice values.

We start our work on representing $j$: the powers of $5$, because it is the simplest in this scenario because there is only one factor of $5$ in the set. Because of this, having $j$ fives in our prime factorization of the product is equivalent to picking $j$ factors from the polynomial $(1+\dots + 6) \cdots$ and choosing each factor to be a $5$. Now that we've selected $j$ factors, there are $n-j$ factors remaining to choose our powers of $3$ and $2$.

Suppose our prime factorization of this product contains $i$ powers of $3$. These powers of $3$ can either come from a $3$ factor or a $6$ factor, but since both $3$ and $6$ contain only one power of $3$, this means that a product with $i$ powers of $3$ corresponds directly to picking $i$ factors from the polynomial, each of which is either $3$ or $6$ (but this distinction doesn't matter when we consider only the powers of $3$.

Now we can reframe the problem again. Our method will be as follows: Suppose we choose an arbitrary pair $(i,j)$ that match the requirements, corresponding to the number of $3$'s and the number of $5$'s our product will have. Then how many different $h$ values for the powers of $2$ are possible?

In the $i+j$ factors we have already chosen, we obviously can't have any factors of $2$ in the $j$ factors with $5$. However, we can have a factor of $2$ pairing with factors of $3$, if we choose a $6$. The maximal possible power of $2$ in these $i$ factors is thus $2^i$, which occurs when we pick every factor to be $6$.

We now have $n-i-j$ factors remaining, and we want to allocate these to solely powers of $2$. For each of these factors, we can choose either a $1,2,$ or $4$. Therefore the maximal power of $2$ achieved in these factors is when we pick $4$ for all of them, which is equivalent to $2^{2\cdot (n-i-j)}$.

Now if we multiply this across the total $n$ factors (or $n$ dice) we have a total of $2^{2n-2i-2j} \cdot 2^i = 2^{2n-i-2j}$, which is the maximal power of $2$ attainable in the product for a pair $(i,j)$. Now note that every power of $2$ below this power is attainable: we can simply just take away a power of $2$ from an existing factor by dividing by $2$. Therefore the powers of $2$, and thus the $h$ value ranges from $h=0$ to $h=2n-i-2j$, so there are a total of $2n+1-i-2j$ distinct values for $h$ for a given pair $(i,j)$.

Now to find the total number of distinct triplets, we must sum this across all possible $i$s and $j$s. Lets take note of our restrictions on $i,j$: the only restriction is that $i+j \leq n$, since we're picking factors from $n$ dice.



~KingRavi


Solution 2

The product can be written as \begin{align*} 2^a 3^b 4^c 5^d 6^e & = 2^{a + 2c + e} 3^{b + e} 5^d . \end{align*}

Therefore, we need to find the number of ordered tuples $\left( a + 2c + e, b+e, d \right)$ where $a$, $b$, $c$, $d$, $e$ are non-negative integers satisfying $a+b+c+d+e \leq n$. We denote this number as $f(n)$.

Denote by $g \left( k \right)$ the number of ordered tuples $\left( a + 2c + e, b+e \right)$ where $\left( a, b, c, e \right) \in \Delta_k$ with $\Delta_k \triangleq \left\{ (a,b,c,e) \in \Bbb Z_+^4: a+b+c+e \leq k \right\}$.

Thus, \begin{align*} f \left( n \right) & = \sum_{d = 0}^n g \left( n - d \right) \\ & = \sum_{k = 0}^n g \left( k \right) . \end{align*}

Next, we compute $g \left( k \right)$.

Denote $i = b + e$. Thus, for each given $i$, the range of $a + 2c + e$ is from 0 to $2 k - i$. Thus, the number of $\left( a + 2c + e, b + e \right)$ is \begin{align*} g \left( k \right) & = \sum_{i=0}^k \left( 2 k - i + 1 \right) \\ & = \frac{1}{2} \left( k + 1 \right) \left( 3 k + 2 \right) . \end{align*}

Therefore, \begin{align*} f \left( n \right) & = \sum_{k = 0}^n g \left( k \right) \\ & = \sum_{k=0}^n \frac{1}{2} \left( k + 1 \right) \left( 3 k + 2 \right) \\ & = \frac{3}{2} \sum_{k=0}^n \left( k + 1 \right)^2 - \frac{1}{2} \sum_{k=0}^n \left( k + 1 \right) \\ & = \frac{3}{2} \cdot \frac{1}{6} \left( n+1 \right) \left( n+2 \right) \left( 2n + 3 \right) - \frac{1}{2} \cdot \frac{1}{2} \left( n + 1 \right) \left( n + 2 \right) \\ & = \frac{1}{2} \left( n + 1 \right)^2 \left( n + 2 \right) . \end{align*}

By solving $f \left( n \right) = 936$, we get $n = \boxed{\textbf{(A) 11}}$.

~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)

Solution 3 (Cheese)

The product can be written as \begin{align*} 2^x 3^y 5^z \end{align*}

Letting $n=1$, we get $(x,y,z)=(0,0,0),(0,0,1),(0,1,0),(1,0,0),(1,1,0),(2,0,0)$, 6 possible values. But if the only restriction of the product if that $2x\le n,y\le n,z\le n$, we can get $(2+1)(1+1)(1+1)=12$ possible values. We calculate the ratio \[r = \frac{\text{possible values of real situation}}{\text{possible values of ideal situation}} = \frac{6}{12}=0.5.\]

Letting $n=2$, we get $(x,y,z)=(0,0,0),(0,0,1),(0,0,2),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1),(1,2,0),$
$(2,0,0),(2,0,1),(2,1,0),(2,2,0),(3,0,0),(3,1,0),(4,0,0)$, 17 possible values. The number of possibilities in the ideal situation is $5*3*3=45$, making $r = 17/45 \approx 0.378$.

Now we can predict the trend of $r$: as $n$ increases, $r$ decreases. Letting $n=3$, you get possible values of ideal situation=$7*4*4=112$. $n=4$, the number=$9*5*5=225$.
$n=5$, the number=$11*6*6=396$.
$n=6$, the number=$13*7*7=637,637<936$ so 6 is not the answer.
$n=7$, the number=$15*8*8=960$.
$n=8$, the number=$17*9*9=1377$,but $1377*0.378$≈$521$ still much smaller than 936.
$n=9$, the number=$19*10*10=1900$,but $1900*0.378$≈$718$ still smaller than 936.
$n=10$, the number=$21*11*11=2541$, $2541*0.378$≈$960$ is a little bigger 936, but the quotient of (possible values of real situation)/(possible values of ideal situation) is much smaller than 0.378 now, so 10 is probably not the answer,so the answer is $\boxed{\textbf{(A) 11}}$.

Check calculation: $n=11$,the number=$23*12*12=3312$,$3312*0.378$≈$1252$ is much bigger than 936.

~Troublemaker

Video Solution 1 by OmegaLearn

https://youtu.be/FZG1j95owTo


See Also

2023 AMC 12B (Problems • Answer Key • Resources)
Preceded by
Problem 22 		Followed by
Problem 24
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 Problems and Solutions

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2023_AMC_12B_Problems/Problem_23&oldid=204308"