2019 AIME II Problems/Problem 4

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)

this is a test i will delete this:

Three forgetful friends decide to meet at a bar between 1pm and 2pm, but none of them remember at what exact time. If all three friends independently and randomly arrive at the bar between 1pm and 2pm and each one stays for $n$ minutes, what is the probability that all three friends will be present at the bar at the same time?

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

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