Difference between revisions of "2019 AIME II Problems/Problem 4"

Revision as of 01:02, 9 August 2019

Problem 4

A standard six-sided fair die is rolled four times. The probability that the product of all four numbers rolled is a perfect square is $\tfrac{m}{n}$ , where $m$ and $n$ are relatively prime positive integers. Find $m+n$ .

Solution

Notice that, other than the number 5, the remaining numbers 1, 2, 3, 4, 6 are only divisible by 2 and/or 3. We can do some cases on the number of 5's rolled (note that there are $6^4 = 1296$ outcomes).

Case 1 (easy): Four 5's are rolled. This has probability $\frac{1}{6^4}$ of occurring.

Case 2: Two 5's are rolled.

Case 3: No 5's are rolled.

To find the number of outcomes for the latter two cases, we will use recursion. Consider a 5-sided die with faces numbered 1, 2, 3, 4, 6. For $n \ge 1$ , let $a_n$ equal the number of outcomes after rolling the die $n$ times, with the property that the product is a square. Thus, $a_1 = 2$ as 1 and 4 are the only possibilities.

To find $a_{n+1}$ given $a_n$ (where $n \ge 1$ ), we observe that if the first $n$ rolls multiply to a perfect square, then the last roll must be 1 or 4. This gives $2a_n$ outcomes. Otherwise, the first $n$ rolls do not multiply to a perfect square ( $5^n - a_n$ outcomes). In this case, we claim that the last roll is uniquely determined (either 2, 3, or 6). If the product of the first $n$ rolls is $2^x 3^y$ where $x$ and $y$ are not both even, then we observe that if $x$ and $y$ are both odd, then the last roll must be 6; if only $x$ is odd, the last roll must be 2, and if only $y$ is odd, the last roll must be 3. Thus, we have $5^n - a_n$ outcomes in this case, and $a_{n+1} = 2a_n + (5^n - a_n) = 5^n + a_n$ .

Computing $a_2$ , $a_3$ , $a_4$ gives $a_2 = 7$ , $a_3 = 32$ , and $a_4 = 157$ . Thus for Case 3, there are 157 outcomes. For case 2, we multiply by $\binom{4}{2} = 6$ to distribute the two 5's among four rolls. Thus the probability is

$\frac{1 + 6 \cdot 7 + 157}{6^4} = \frac{200}{6^4} = \frac{25}{162} \implies m+n = \boxed{187}$

-scrabbler94

Solution 2

We can solve this without finding the amount of cases. Notice when we roll a 1 or a 4, it does not affect whether or not the product is a square number. We have a 1/3 chance of rolling either a 1 or 4. We have a 2/3 chance of rolling a 2,3,5 or 6. Lets call rolling 1 or 4 rolling a dud.

Probability of rolling 4 duds: $\left(\frac{1}{3}\right)^4$

Probability of rolling 3 duds: $4 * \left(\frac{1}{3}\right)^3 * \frac{2}{3}$

Probability of rolling 2 duds: $6 * \left(\frac{1}{3}\right)^2 * \left(\frac{2}{3}\right)^2$

Probability of rolling 1 dud: $4 * \frac{1}{3} * \left(\frac{2}{3}\right)^3$

Probability of rolling 0 duds: $\left(\frac{2}{3}\right)^4$

Now we will find the probability of a square product given we have rolled each amount of duds

Probability of getting a square product given 4 duds: 1

Probability of getting a square product given 3 duds: 0 (you will have 1 non-dud and that's never going to be square)

Probability of getting a square product given 2 duds: $\frac{1}{4}$ (as long as our two non-duds are the same, our product will be square)

Probability of getting a square product given 1 duds: $\frac{3!}{4^3}$ = $\frac{3}{32}$ (the only way to have a square product is rolling a 2,3 and 6. There are 3! ways of doing that and a total of $4^3$ ways to roll 3 non-duds).

Probability of getting a square product given 0 duds: $\frac{40}{4^4}$ = $\frac{5}{32}$ (We can have any two non-duds twice. For example, 2,2,5,5. There are $\binom{4}{2} = 6$ ways of choosing which two non-duds to use and $\binom{4}{2} = 6$ ways of choosing how to arrange those 4 numbers. That gives us 6*6=36 combinations. We can also have 2,2,2,2 or 3,3,3,3 or 5,5,5,5 or 6,6,6,6. This gives us a total of 40 combinations).

We multiply each probability of rolling k duds with the probability of getting a square product given k duds and then sum all the values. $\left(\frac{1}{3}\right)^4 * 1 + 4 * \left(\frac{1}{3}\right)^3 * \frac{2}{3} * 0 + 6 * \left(\frac{1}{3}\right)^2 * \left(\frac{2}{3}\right)^2 * \frac{1}{4} + 4 * \frac{1}{3} * \left(\frac{2}{3}\right)^3 * \frac{3}{32} + \left(\frac{2}{3}\right)^4 * \frac{5}{32} = \frac{25}{162}.$

$25+162$ = $\boxed{187}$

-dnaidu (silverlizard)

Solution 3

Note that rolling a 1/4 will not affect whether or not the product is a perfect square. This means that in order for the product to be a perfect square, all non 1/4 numbers rolled must come in pairs, with the only exception being the triplet 2,3, 6. Now we can do casework:

If there are four 1/4's, then there are $2^4=16$ combinations. If there are three 1/4's, then there are 0 combinations, because the fourth number isn't a square. If there are two 1/4's, there are $2^2=4$ ways to choose the two 1/4's, 4 ways to choose the remaining pair of numbers, and $\frac{4!}{2!2!}=6$ ways to arrange, so there are $4\cdot 4\cdot 6=96$ combinations for this case. If there is one 1/4, then there are 2 ways to choose whether it is a 1 or 4, and the remaining three numbers must be 2, 3, and 6, so there are $4!$ ways to order, meaning there are $2\cdot 4!=48$ combinations for this case. Our final case is if there are no 1/4's, in which case we must have two pairs. If the two pairs are of different numbers, then there $\binom{4}{2}$ to choose the numbers and $\frac{4!}{2!2!}=6$ ways to arrange them, so $6\cdot 6=36$ . If all four numbers are the same there are $4$ combinations, so there are $4+36=40$ combinations for this case.

Hence there are $16+0+96+48+40=200$ combinations where the product of the dice is a perfect square, and there are $6^4=1296$ total combinations, so the desired probability is $\frac{200}{1296}=\frac{25}{162}$ , yielding an answer os $25+162=\boxed{187}$ .

-Stormersyle

Solution 4(Casework)

Another way to solve this problem is to do casework on all the perfect squares from $1^2$ to $36^2$ , and how many ways they can be ordered $1^2$ - $1,1,1,1$ - $1$ way. $2^2$ - $4,1,1,1$ or $2,2,1,1$ - $\binom{4}{2}+4=10$ ways. $3^2$ - $3,3,1,1$ - $\binom{4}{2}=6$ ways. $4^2$ - $4,4,1,1$ , $2,2,2,2$ , or $2,2,4,1$ - $\binom{4}{2}+1+12=19$ ways. $5^2$ - $5,5,1,1$ - $\binom{4}{2}=6$ ways. $6^2$ - $6,6,1,1$ , $1,2,3,6$ , $2,3,2,3$ , $3,3,4,1$ - $2*\binom{4}{2}+4!+12=48$ ways. $7^2$ - Since there is a prime greater than 6 in its prime factorization there are $0$ ways. $8^2$ - $4,4,4,1$ or $2,4,2,4$ - $\binom{4}{2}+4=10$ ways. $9^2$ - $3,3,3,3$ - $1$ way. $10^2$ - $2,2,5,5$ or $1,4,5,5$ - $6+12=18$ ways. $11^2$ - $0$ ways for the same reason as $7^2$ . $12^2$ - $6,6,2,2$ , $4,4,3,3$ , $2,3,4,6$ , or $1,4,6,6$ - $2*\binom{4}{2}+4!+12=48$ ways. $13^2$ - $0$ ways. $14^2$ - $0$ ways. $15^2$ - $3,3,5,5$ - $\binom{4}{2}=6$ ways. $16^2$ - $4,4,4,4$ - $1$ way. $17^2$ - $0$ ways. $18^2$ - $3,3,6,6$ - $\binom{4}{2}=6$ ways. $19^2$ - $0$ ways. $20^2$ - $4,4,5,5$ - $\binom{4}{2}=6$ ways. $21^2$ - $0$ ways. $22^2$ - $0$ ways. $23^2$ - $0$ ways. $24^2$ - $4,4,6,6$ - $\binom{4}{2}=6$ ways. $25^2$ - $5,5,5,5$ - $1$ way. $26^2$ - $0$ ways. $27^2$ - $0$ ways. $28^2$ - $0$ ways. $29^2$ - $0$ ways. $30^2$ - $5,5,6,6$ - $\binom{4}{2}$ ways. $31^2$ - $0$ ways. $32^2$ - $0$ ways. $33^2$ - $0$ ways. $34^2$ - $0$ ways. $35^2$ - $0$ ways. $36^2$ - $6,6,6,6$ - $1$ way.

There are $6^4=1296$ ways that the dice can land. Summing up the ways, it is easy to see that there are $200$ ways. This results in a probability of $\frac{200}{1296}=\frac{25}{162}\implies\boxed{187}$ -superninja2000

@@ Line 53: / Line 53: @@
 -dnaidu (silverlizard)
-<math>a \# b = ab-3 \left(a+b\right) + 12</math>.  Calculate <math>n\#\left(n-1\right)\#\left(n-2\right)...\#3\#2\#1</math>
 ==Solution 3==

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

Page

Toolbox

Search